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.
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define SZ(x) ((int)x.size()-1)
#define ms(a,b) memset(a,b,sizeof a)
#define F(i,a,b) for (int i=(a);i<=(b);++i)
#define DF(i,a,b) for (int i=(a);i>=(b);--i)
#pragma GCC optimize(2)
#pragma GCC target("avx")
using namespace std;
inline int read(){
	char ch=getchar(); int w=1,c=0;
	for(;!isdigit(ch);ch=getchar()) if (ch=='-') w=-1;
	for(;isdigit(ch);ch=getchar()) c=(c<<1)+(c<<3)+(ch^48);
	return w*c;
}
const int M=2e5+10;
int s[M],tp,n,q,p[M];
int a[M],b[M];
LL c[M];
bool vis[M];
vector<int> v[M];
int lg[M],dep[M],f[M][20];
void dfs(int x,int fa){
	f[x][0]=fa;
	if (fa==-1) dep[x]=1;
	else dep[x]=dep[fa]+1;
	F(i,1,lg[dep[x]]) f[x][i]=f[f[x][i-1]][i-1];
	LL ss=0;
	for (auto y:v[x]){
		dfs(y,x);
		ss+=b[y];
		if (c[y]<0) c[x]+=c[y],c[y]=0;
	}
	c[x]+=a[x]-b[x]+ss;
}
int lca(int x,int y){
	if (dep[x]<dep[y]) swap(x,y);
	int del=dep[x]-dep[y];
	F(i,0,lg[del]) if (del>>i&1) x=f[x][i];
	if (x==y) return x;
	DF(i,lg[dep[x]],0){
		if (f[x][i]^f[y][i]) x=f[x][i],y=f[y][i];
	}
	return f[x][0];
}
LL dis(int x,int y){
//	cout<<x<<" "<<y<<" lca : "<<lca(x,y)<<" "<<c[x]+c[y]-c[lca(x,y)]*2<<"   nmd\n";
	return c[x]+c[y]-c[lca(x,y)]*2;
}
void init(){
	F(i,2,n) lg[i]=lg[i>>1]+1;
	dfs(0,-1);
	F(i,1,n) c[i]+=c[f[i][0]];
}
LL ans;
set<int> sl;
set<int>::iterator it;
void ins(int x){
	int pre,suf;
	it=sl.lower_bound(x);
	if (it==sl.end()){
		pre=*(--it);
		suf=*sl.begin();
	}
	else{
		suf=*it; it--; pre=*it;
	}
	sl.insert(x);
	ans+=dis(x,pre)+dis(x,suf)-dis(pre,suf);
}
void del(int x){
	int pre,suf;
	sl.erase(x);
	it=sl.lower_bound(x);
	if (it==sl.end()){
		pre=*(--it);
		suf=*sl.begin();
	}
	else{
		suf=*it; it--; pre=*it;
	}
	ans-=dis(x,pre)+dis(x,suf)-dis(pre,suf);
}
int num[M];
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read(); q=read();
	F(i,1,n){
		p[i]=read();
		while (tp && p[s[tp]]<p[i]) tp--;
		v[s[tp]].pb(i);	
//		cout<<s[tp]<<" -> "<<i<<"  edge \n";
		s[++tp]=i;
	}
	F(i,1,n) a[i]=read();
	F(i,1,n) b[i]=read();
	init();
	sl.insert(0);
	F(i,1,q){
		int x=read();
		if (vis[x]){
			if (f[x][0]){
				vis[x]^=1;
				if (!(--num[f[x][0]])){
					del(f[x][0]);
				}
			}
			
		}
		else{
			if (f[x][0]){
				vis[x]^=1;
				if (!(num[f[x][0]]++)){
					ins(f[x][0]);
				}
			}
		}
		cout<<ans/2+c[0]<<"\n";
	}
	return 0;
}


