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<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<set>
#define maxn 200005
#define ll long long
using namespace std;

int n,q,i,j,k,p[maxn],que[maxn],tot,d[maxn];
ll a[maxn],b[maxn];
set<int> S;
set<int> ::iterator it,it1;


struct arr{int x,y,i;} A[maxn*3];
int cmp(arr a,arr b){return a.x>b.x;}
ll ans[maxn*3],t[maxn*4],tag[maxn*4];

void downtag(int x,int l,int r){
	t[x]+=tag[x];
	if (l<r) tag[x<<1]+=tag[x],tag[x<<1^1]+=tag[x];
	tag[x]=0;
}
void add(int x,int l,int r,int L,int R,ll d){
	if (tag[x]) downtag(x,l,r);
	if (l>R||r<L) return;
	if (L<=l&&r<=R){tag[x]+=d,downtag(x,l,r);return;}
	int mid=(l+r)>>1;
	add(x<<1,l,mid,L,R,d),add(x<<1^1,mid+1,r,L,R,d);
	t[x]=min(t[x<<1],t[x<<1^1]);
}
ll find(int x,int l,int r,int p){
	if (tag[x]) downtag(x,l,r);
	if (l==r) return t[x];
	int mid=(l+r)>>1;
	if (p<=mid) return find(x<<1,l,mid,p); 
	else return find(x<<1^1,mid+1,r,p);
}

int main(){
	scanf("%d%d",&n,&q),p[n+1]=n+1;
	for(i=1;i<=n;i++) scanf("%d",&p[i]);
	for(i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(i=1;i<=n;i++) scanf("%lld",&b[i]);
	S.insert(1),S.insert(n+1);
	for(i=1;i<=q;i++){
		scanf("%d",&que[i]); int x=que[i];
		if (x!=1){
			it=S.lower_bound(x);
			if ((*it)!=x){
				it1=it,it1--;
				tot++,A[tot].x=x,A[tot].y=*it,A[tot].i=tot;
				tot++,A[tot].x=*it1,A[tot].y=x,A[tot].i=tot;
				tot++,A[tot].x=*it1,A[tot].y=*it,A[tot].i=tot;
				S.insert(x);
			} else {
				S.erase(x),it=S.lower_bound(x);
				it1=it,it1--;
				tot++,A[tot].x=x,A[tot].y=*it,A[tot].i=tot;
				tot++,A[tot].x=*it1,A[tot].y=x,A[tot].i=tot;
				tot++,A[tot].x=*it1,A[tot].y=*it,A[tot].i=tot;
			}
		}
	}
	sort(A+1,A+1+tot,cmp);
	d[1]=n+1; int w=1,now=1;
	for(i=n;i>=1;i--){
		while (p[d[w]]<p[i]) w--;
		ll v=find(1,1,n+1,d[w]);
		add(1,1,n+1,i+1,n+1,a[i]);
		if (b[i]<v+a[i])
			add(1,1,n+1,d[w],n+1,b[i]-v-a[i]);
		while (now<=tot&&A[now].x==i){
			ans[A[now].i]=find(1,1,n+1,A[now].y);
			now++;
		}
		d[++w]=i;
	}
	S.clear(),S.insert(1),S.insert(n+1);
	ll sum=find(1,1,n+1,n+1); now=0;
	for(i=1;i<=q;i++){
		int x=que[i];
		if (x!=1){
			ll v1=ans[++now],v2=ans[++now],v3=ans[++now];
			it=S.lower_bound(x);
			if ((*it)!=x) {
				S.insert(x); 
				sum+=v1+v2-v3;
			} else {
				S.erase(x);
				sum+=v3-v1-v2;
			}
		}
		printf("%lld\n",sum);
	}

}