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 <set>
#include <cmath>
#include <cstdio>
using namespace std;

#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )

typedef long long LL;
typedef set<int> :: iterator Iter;

const int MAXN = 2e5 + 5, MAXLOG = 20;

template<typename _T>
void read( _T &x )
{
	x = 0;char s = getchar();int f = 1;
	while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
	while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
	x *= f;
}

template<typename _T>
void write( _T x )
{
	if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
	if( 9 < x ){ write( x / 10 ); }
	putchar( x % 10 + '0' );
}

struct Edge
{
	int to, nxt;
}Graph[MAXN << 1];

set<int> s;

int buc[MAXN];
bool vis[MAXN];

int f[MAXN][MAXLOG];
LL su[MAXN], bst[MAXN];
int DFN[MAXN], dep[MAXN], seq[MAXN], head[MAXN];
int stk[MAXN], top;

int A[MAXN], B[MAXN], P[MAXN];
int N, Q, cnt, lg2, ID; LL ans = 0;

void AddEdge( const int from, const int to )
{
	Graph[++ cnt].to = to, Graph[cnt].nxt = head[from];
	head[from] = cnt;
}

void DFS( const int u, const int fa )
{
	seq[DFN[u] = ++ ID] = u;
	dep[u] = dep[fa] + 1, f[u][0] = fa;
	for( int i = head[u], v ; i ; i = Graph[i].nxt )
		if( ( v = Graph[i].to ) ^ fa )
		{
			DFS( v, u ), su[u] += B[v];
			if( bst[v] < 0 ) bst[u] += bst[v], bst[v] = 0;
		}
	bst[u] += A[u] - B[u] + su[u];
}

void Init()
{
	DFS( 0, 0 ), lg2 = log2( N );
	rep( j, 1, lg2 ) rep( i, 1, N ) 
		f[i][j] = f[f[i][j - 1]][j - 1];
	rep( i, 2, N ) bst[seq[i]] += bst[f[seq[i]][0]];
}

void Balance( int &u, const int stp )
{
	for( int i = 0 ; ( 1 << i ) <= stp ; i ++ )
		if( stp >> i & 1 ) u = f[u][i];
}

int LCA( int u, int v )
{
	if( dep[u] > dep[v] ) Balance( u, dep[u] - dep[v] );
	if( dep[v] > dep[u] ) Balance( v, dep[v] - dep[u] );
	if( u == v ) return u;
	per( i, lg2, 0 ) if( f[u][i] ^ f[v][i] ) u = f[u][i], v = f[v][i];
	return f[u][0];
}

LL Dist( const int u, const int v ) { return bst[u] + bst[v] - 2 * bst[LCA( u, v )]; }

void Insert( const int u )
{
	Iter it = ( s.insert( DFN[u] ), s.find( DFN[u] ) );
	int pre = 0, nxt = 0;
	if( it != s.begin() ) pre = seq[* -- it]; it ++;
	if( it != s.end() && ( ++ it ) != s.end() ) nxt = seq[* it];
	ans += Dist( u, pre ) + Dist( u, nxt ) - Dist( pre, nxt );
}

void Delete( const int u )
{
	set<int> :: iterator it = s.find( DFN[u] );
	int pre = 0, nxt = 0; 
	if( it != s.end() ) 
	{
		it ++;
		if( it != s.end() )
			nxt = seq[* it];
		it --;
	}
	if( it != s.begin() ) pre = seq[* -- it];
	ans -= Dist( u, pre ) + Dist( u, nxt ) - Dist( pre, nxt );
	s.erase( DFN[u] );
}

int main()
{
	read( N ), read( Q );
	rep( i, 1, N ) read( P[i] );
	rep( i, 1, N ) read( A[i] );
	rep( i, 1, N ) read( B[i] );
	for( int i = 1 ; i <= N ; i ++ )
	{
		while( top && P[stk[top]] <= P[i] ) top --;
		AddEdge( stk[top], i ), stk[++ top] = i;
	}
	Init();
	for( int cur ; Q -- ; )
	{
		read( cur );
		if( vis[cur] )
		{
			vis[cur] = false;
			if( ! ( -- buc[f[cur][0]] ) )
				Delete( f[cur][0] );
		}
		else
		{
			vis[cur] = true;
			if( ! ( buc[f[cur][0]] ++ ) )
				Insert( f[cur][0] );
		}
		write( ans / 2 + bst[0] ), putchar( '\n' );
	}
	return 0;
}