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 pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
#define G getchar()
int read()
{
	int x=0; bool flg=false; char ch=G;
	for (;!isdigit(ch);ch=G) if (ch=='-') flg=true;
	for (;isdigit(ch);ch=G) x=(x<<3)+(x<<1)+(ch^48);
	return flg?-x:x;
}
#undef G
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
//typedef pair<int,int> P;
/*const int mod=;
inline int upd(const int &x){return x+(x>>31&mod);}
inline void add(int &x,const int &y){x=upd(x+y-mod);}
inline void iadd(int &x,const int &y){x=upd(x-y);}
int qpow(int x,int y){
	int res=1;
	for (;y;y>>=1,x=1LL*x*x%mod)
		if (y&1) res=1LL*res*x%mod;
	return res;
}*/
#define rep(i,l,r) for (int i(l);i<=int(r);i++)
#define per(i,l,r) for (int i(r);i>=int(l);i--)

int n,q;
int p[200010],a[200010],b[200010];
vector<int> e[200010];

int fat[200010],dep[200010],son[200010],siz[200010];
int top[200010],id[200010],dfn[200010];
ll w[200010],dp[200010];

void dfs1(int x,int f,int d){
	fat[x]=f; dep[x]=d; siz[x]=1;
	ll S=0;
	for (const int &y: e[x]){
		dfs1(y,x,d+1);
		siz[x]+=siz[y];
		if (siz[y]>siz[son[x]]) son[x]=y;
		S+=dp[y];
	}
	if (e[x].empty()) /*w[x]=*/dp[x]=min(a[x],b[x]);
	else w[x]=(a[x])-(min(0LL+a[x],b[x]-S)),dp[x]=min(a[x]+S,0LL+b[x]);
	//printf("node %d: dp %lld w %lld S %lld\n",x,dp[x],w[x],S);
}

void dfs2(int x,int t){
	top[x]=t; dfn[++*dfn]=x; id[x]=++*id;
	if (siz[x]==1) return;
	w[son[x]]+=w[x]; dfs2(son[x],t);
	for (const int &y: e[x]){
		if (y==son[x]) continue;
		w[y]+=w[x]; dfs2(y,y);
	}
}

int getlca(int x,int y){
	while (top[x]^top[y])
		if (dep[top[y]]<dep[top[x]]) x=fat[top[x]];
		else y=fat[top[y]];
	return dep[x]<dep[y]?x:y;
}

void solve(){
	n=read(),q=read();
	rep(i,1,n) p[i]=read();
	rep(i,1,n) a[i]=read();
	rep(i,1,n) b[i]=read();
	
	static int stk[200010],top;
	stk[0]=n+1; //p[0]=1e9;
	rep(i,1,n){
		while (top&&p[stk[top]]<p[i]) --top;
		//printf("%d -> %d\n",stk[top],i);
		e[stk[top]].pb(i);
		stk[++top]=i;
	}
	
	dfs1(n+1,0,1); dfs2(n+1,n+1);
	
	ll W=0;
	for (const int &y: e[n+1]) W+=dp[y];
	set<int> st;
	st.insert(1);
	
	static int mrk[200010]; mrk[n+1]=1;
	static bool inq[200010];
	
	while (q--){
		int y=read(); inq[y]^=1;
		int x=fat[y];
		if (inq[y]) ++mrk[x];
		else --mrk[x];
		if (!inq[y]&&!mrk[x]){
			const auto it=st.find(id[x]);
			assert(it!=st.end());
			auto s=it;
			int l=n+1;
			if ((++s)!=st.end()){
				const int t=getlca(x,dfn[*s]);
				if (dep[t]>dep[l]) l=t;
			}
			s=it;
			if (s!=st.begin()){
				const int t=getlca(x,dfn[*--s]);
				if (dep[t]>dep[l]) l=t;
			}
			W-=w[x]-w[l];
			//printf("unchange %d -> %d\n",l,x);
			st.erase(it);
		}
		else if (inq[y]&&mrk[x]==1){
			//printf("test x %d\n",x);
			const auto it=st.insert(id[x]).fi;
			auto s=it;
			int l=n+1;
			if ((++s)!=st.end()){
				const int t=getlca(x,dfn[*s]);
				//printf("get t %d s %d\n",t,*s);
				if (dep[t]>dep[l]) l=t;
			}
			s=it;
			if (s!=st.begin()){
				const int t=getlca(x,dfn[*--s]);
				//printf("get t %d s %d\n",t,*s);
				if (dep[t]>dep[l]) l=t;
			}
			W+=w[x]-w[l];
			//printf("change %d -> %d\n",l,x);
			st.insert(it,id[x]);
		}
		printf("%lld\n",W);
	}
}
int main()
{
	for (int T=1;T--;) solve();
	return 0;
}