Problem: There are n squares drawn from left to right on the floor. The i-th square has three integers p_i,a_i,b_i, written on it. The sequence p_1,p_2,...,p_n forms a permutation.

Each round you will start from the leftmost square 1 and jump to the right. If you are now on the i-th square, you can do one of the following two operations:

  1. Jump to the i+1-th square and pay the cost a_i. If i=n, then you can end the round and pay the cost a_i. 
  2. Jump to the j-th square and pay the cost b_i, where j is the leftmost square that satisfies j > i, p_j > p_i. If there is no such j then you can end the round and pay the cost b_i. 



There are q rounds in the game. To make the game more difficult, you need to maintain a square set S (initially it is empty). You must pass through these squares during the round (other squares can also be passed through). The square set S for the i-th round is obtained by adding or removing a square from the square set for the (i-1)-th round. 

For each round find the minimum cost you should pay to end it.

Input

The first line contains two integers n, q (1≤ n,q≤ 2 ⋅ 10^5) — the number of squares and the number of rounds.

The second line contains n distinct integers p_1,p_2,...,p_n (1≤ p_i≤ n). It is guaranteed that the sequence p_1,p_2,...,p_n forms a permutation.

The third line contains n integers a_1,a_2,…,a_n (-10^9≤ a_i≤ 10^9).

The fourth line contains n integers b_1,b_2,...,b_n (-10^9≤ b_i≤ 10^9).

Then q lines follow, i-th of them contains a single integer x_i (1≤ x_i≤ n). If x_i was in the set S on the (i-1)-th round you should remove it, otherwise, you should add it.

Output

Print q lines, each of them should contain a single integer — the minimum cost you should pay to end the corresponding round.

Examples

Input


3 2
2 1 3
10 -5 4
3 -2 3
1
2


Output


6
8


Input


5 4
2 1 5 3 4
6 -5 3 -10 -1
0 3 2 7 2
1
2
3
2


Output


-8
-7
-7
-8

Note

Let's consider the character T as the end of a round. Then we can draw two graphs for the first and the second test.

<image> <image>

In the first round of the first test, the set that you must pass through is \{1\}. The path you can use is 1→ 3→ T and its cost is 6.

In the second round of the first test, the set that you must pass through is \{1,2\}. The path you can use is 1→ 2→ 3→ T and its cost is 8.

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
int n,q,tot;
int p[200009],st[200009];
int sa[200009],sb[200009];
int f[200009][19],dep[200009];
int vis[200009],rep[200009];
int dfn[200009];
ll dp[200009],psm[200009];
int anc[200009];
vector<int> g[200009];
void dfs1(int x,int fa)
{
	dfn[x]=++tot;
	dep[x]=dep[fa]+1;
	f[x][0]=fa;
	for(int i=1;i<=18;i++)
		f[x][i]=f[f[x][i-1]][i-1];
	dp[x]=sa[x]-sb[x];
	for(int v:g[x])
	{
		dfs1(v,x);
		dp[x]+=min(0LL,dp[v]);
		dp[x]+=sb[v];
	}
}
void dfs2(int x)
{
	if(x==0)
		psm[x]=dp[x];
	for(int v:g[x])
	{
		psm[v]=psm[x]+max(0LL,dp[v]);
		dfs2(v);
	}
}
int getkf(int x,int k)
{
	for(int i=0;i<=18;i++)
		if(k>>i&1)
			x=f[x][i];
	return x;
}
int getlca(int a,int b)
{
	if(dep[a]<dep[b])
		swap(a,b);
	a=getkf(a,dep[a]-dep[b]);
	if(a==b)
		return a;
	for(int i=18;i>=0;i--)
		if(f[a][i]!=f[b][i])
			a=f[a][i],b=f[b][i];
	return f[a][0];
}
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
		scanf("%d",p+i);
	for(int i=1;i<=n;i++)
		scanf("%d",sa+i);
	for(int i=1;i<=n;i++)
		scanf("%d",sb+i);
	int tp=0;
	for(int i=1;i<=n;i++)
	{
		while(tp&&p[i]>=p[st[tp]])
			tp--;
		// printf("i:%d fa:%d\n",i,st[tp]);
		g[st[tp]].push_back(i);
		st[++tp]=i;
	}
	dfs1(0,0);
	dfs2(0);
	set<pii> s;
	s.insert(pii(dfn[0],0));
	rep[0]=1;
	ll ans=dp[0];
	// for(int i=1;i<=n;i++)
		// printf("i:%d dfn:%d\n",i,dfn[i]);
	// printf("ans:%lld\n",ans);
	// printf("2: 5: %d\n",getlca(2,5));
	// for(int i=1;i<=n;i++)
	// 	printf("i:%d psm:%lld\n",i,psm[i]);
	for(int i=1;i<=q;i++)
	{
		int a;
		scanf("%d",&a);
		int fa=f[a][0];
		if(!vis[a])
		{
			vis[a]=1;
			if(!rep[fa])
			{
				assert(!s.count(pii(dfn[fa],fa)));
				auto it=s.lower_bound(pii(dfn[fa],fa));
				it--;
				int lca=getlca(fa,it->se);
				it++;
				if(it!=s.end())
				{
					int nlca=getlca(fa,it->se);
					if(dep[nlca]>dep[lca])
						lca=nlca;
				}
				// printf("a:%d b:%d lca:%d\n",fa,it->se,lca);
				// int sn=getkf(fa,dep[fa]-dep[lca]-1);
				ans+=psm[fa]-psm[lca];
				if(!s.count(pii(dfn[lca],lca)))
				{
					assert(rep[lca]==0);
					rep[lca]=1;
					auto ti=s.upper_bound(pii(dfn[lca],lca));
					anc[lca]=anc[ti->se];
					anc[ti->se]=lca;
					s.insert(pii(dfn[lca],lca));
				}
				if(fa!=lca)
				{
					rep[lca]++;
					anc[fa]=lca;
					s.insert(pii(dfn[fa],fa));
				}
			}
			rep[fa]++;
		}
		else
		{
			vis[a]=0;
			rep[fa]--;
			assert(s.count(pii(dfn[fa],fa)));
			while(!rep[fa])
			{
				int lca=anc[fa];
				// printf("a:%d b:%d lca:%d\n",fa,it->se,lca);
				// int sn=getkf(fa,dep[fa]-dep[lca]-1);
				ans-=psm[fa]-psm[lca];
				s.erase(pii(dfn[fa],fa));
				rep[anc[fa]]--;
				fa=anc[fa];
			}
		}
		// for(int i=0;i<=n;i++)
		// 	printf("i:%d rep:%d\n",i,rep[i]);
		printf("%lld\n",ans);
	}
	return 0;
}