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:
/* Clearink */

#include <set>
#include <cstdio>

#define rep( i, l, r ) for ( int i = l, repEnd##i = r; i <= repEnd##i; ++i )
#define per( i, r, l ) for ( int i = r, repEnd##i = l; i >= repEnd##i; --i )

inline int rint() {
	int x = 0, f = 1, s = getchar();
	for ( ; s < '0' || '9' < s; s = getchar() ) f = s == '-' ? -f : f;
	for ( ; '0' <= s && s <= '9'; s = getchar() ) x = x * 10 + ( s ^ '0' );
	return x * f;
}

template<typename Tp>
inline void wint( Tp x ) {
	if ( x < 0 ) putchar( '-' ), x = -x;
	if ( 9 < x ) wint( x / 10 );
	putchar( x % 10 ^ '0' );
}

typedef long long LL;

const int MAXN = 2e5, MAXLG = 17;
int n, q, a[MAXN + 5], b[MAXN + 5], fa[MAXN + 5][MAXLG + 5];
int top, stk[MAXN + 5], p[MAXN + 5], dep[MAXN + 5];
LL ans, val[MAXN + 5], dlt[MAXN + 5], sum[MAXN + 5];
int cnt[MAXN + 5]; bool vis[MAXN + 5];
std::set<int> st;

inline void build() {
	rep ( i, 1, n ) {
		for ( ; top && p[stk[top]] < p[i]; --top );
		dep[i] = dep[fa[i][0] = stk[top]] + 1, stk[++top] = i;
		val[fa[i][0]] += b[i];
		if ( !fa[i][0] ) ans += b[i];
		for ( int j = 1; fa[i][j - 1];
			fa[i][j] = fa[fa[i][j - 1]][j - 1], ++j );
	}
}

inline int lca( int u, int v ) {
	if ( dep[u] < dep[v] ) u ^= v ^= u ^= v;
	for ( int i = 17; ~i; --i ) if ( dep[fa[u][i]] >= dep[v] ) u = fa[u][i];
	if ( u == v ) return u;
	for ( int i = 17; ~i; --i ) if ( fa[u][i] != fa[v][i] ) {
		u = fa[u][i], v = fa[v][i];
	}
	return fa[u][0];
}

inline void erase( const int u ) {
	auto it( st.find( u ) );
	int p = 0, q = 0;
	if ( it != st.begin() ) p = lca( *std::prev( it ), u );
	if ( ++it != st.end() ) q = lca( *it, u );
	st.erase( --it );
	if ( dep[p] < dep[q] ) p = q;
	ans -= sum[u] - sum[p];
}

inline void insert( const int u ) {
	auto it( st.insert( u ).first );
	int p = 0, q = 0;
	if ( it != st.begin() ) p = lca( *std::prev( it ), u );
	if ( ++it != st.end() ) q = lca( *it, u );
	if ( dep[p] < dep[q] ) p = q;
	ans += sum[u] - sum[p];
}

int main() {
	n = rint(), q = rint();
	rep ( i, 1, n ) p[i] = rint();
	rep ( i, 1, n ) val[i] += a[i] = rint();
	rep ( i, 1, n ) val[i] -= b[i] = rint();
	build();
	per ( i, n, 1 )	{
		dlt[i] += val[i];
		if ( dlt[i] < 0 ) dlt[fa[i][0]] += dlt[i];
	}
	dlt[0] += val[0], sum[0] = dlt[0];
	rep ( i, 1, n ) {
		if ( dlt[i] < 0 ) sum[i] = sum[fa[i][0]];
		else sum[i] = sum[fa[i][0]] + dlt[i];
	}
	st.insert( 0 ), cnt[0] = 1, ans = sum[0];
	for ( int s; q--; ) {
		s = rint();
		if ( vis[s] ) {
			vis[s] = false;
			if ( !--cnt[fa[s][0]] ) erase( fa[s][0] );
		} else {
			vis[s] = true;
			if ( !cnt[fa[s][0]]++ ) insert( fa[s][0] );
		}
		wint( ans ), putchar( '\n' );
	}
	return 0;
}