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>
using namespace std;
const int maxn=2e5+5,maxm=2e5+5;
int head[maxn],nume;
struct edge { int v,w,c,next; } e[maxm];  // v顶点,w权值,c花费
inline void init_edge() { memset(head,-1,sizeof head); nume=0; } // !!!
inline void add_edge(int u,int v,int w=0,int c=0) {
    e[nume].v=v; e[nume].w=w; e[nume].c=c;
    e[nume].next=head[u]; head[u]=nume++;
}
int tot,name[maxn],num[maxn];
int dfs[maxn],cen[maxn],cnt;
long long a[maxn],b[maxn],c[maxn],easy[maxn],hard[maxn],sumc[maxn];
void Dfs(int u)
{
	dfs[u]=++cnt;
	hard[u]=a[u];
	for(int i=head[u];~i;i=e[i].next)
	{
		int v=e[i].v;
		cen[v]=cen[u]+1;
		Dfs(v);
		hard[u]+=easy[v];
//		printf("hard[%d]=%lld easy[%d]=%lld\n",u,hard[u],v,easy[v]);
	}
	easy[u]=min(hard[u],b[u]);
//	printf("%d %lld %lld\n",u,easy[u],hard[u]);
	c[u]=hard[u]-easy[u];
}
int f[maxn][25];
int lca(int x,int y)
{
	if(cen[x]<cen[y])
	{
		int k=cen[y]-cen[x],t=0;
		while(k)
		{
			if(k&1) y=f[y][t];
			t++;
			k>>=1;
		}
	}
	else
	{
		int k=cen[x]-cen[y],t=0;
		while(k)
		{
			if(k&1) x=f[x][t];
			t++;
			k>>=1;
		}
	}
	if(x==y)
		return x;
	for(int i=20;i>=0;i--)
	{
		if(f[x][i]!=f[y][i])
		{
			x=f[x][i];
			y=f[y][i];
		}
	}
	x=f[x][0];
	y=f[y][0];
	return x;
}
int in[maxn],g[maxn];
set<int> s;
set<int>::iterator it;
long long ans=0;
void add(int x)
{
	int a,b;
	if(in[x])
	{
		in[x]^=1;
		x=f[x][0];
		g[x]--;
		if(g[x]==0)
			s.erase(x);
		it=s.upper_bound(x);
		if(it!=s.end())
			a=lca(*it,x);
		else
			a=0;
		if(it!=s.begin())
		{
			it--;
			b=lca(*it,x);
		}
		else
			b=0;
		if(cen[a]<cen[b])
			a=b;
		ans+=sumc[a]-sumc[x];
	}
	else
	{
		in[x]^=1;
		x=f[x][0];
		it=s.upper_bound(x);
		if(it!=s.end())
			a=lca(*it,x);
		else
			a=0;
		if(it!=s.begin())
		{
			it--;
			b=lca(*it,x);
		}
		else
			b=0;
		if(cen[a]<cen[b])
			a=b;
		ans-=sumc[a]-sumc[x];
		if(g[x]==0)
			s.insert(x);
		g[x]++;
	}
}
int n,q,p[maxn];
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("%lld",&a[i]);
	for(int i=1;i<=n;i++)
		scanf("%lld",&b[i]);
	init_edge();
	tot++;
	name[tot]=0;
	num[tot]=n+1;
	for(int i=1;i<=n;i++)
	{
		while(p[i]>num[tot])
			tot--;
		add_edge(name[tot],i);
//		printf("%d %d\n",name[tot],i);
		f[i][0]=name[tot];
		tot++;
		name[tot]=i;
		num[tot]=p[i];
	}
	Dfs(0);
//	for(int i=1;i<=n;i++)
//		printf("%lld ",c[i]);
//	printf("\n");
	for(int i=1;i<=n;i++)
		sumc[i]=sumc[f[i][0]]+c[i];
	for(int i=1;i<=20;i++)
	{
		for(int j=1;j<=n;j++)
		{
			f[j][i]=f[f[j][i-1]][i-1];
		}
	}
	add(1);
//	add(n);
	while(q--)
	{
		int x;
		scanf("%d",&x);
		if(x!=1)
			add(x);
		printf("%lld\n",hard[0]+ans);
	}
}