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:
/*Lucky_Glass*/
#include <set>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

inline int rin(int &r) {
	int b = 1, c = getchar(); r = 0;
	while( c < '0' || '9' < c ) b = c == '-' ? -1 : b, c = getchar();
	while( '0' <= c && c <= '9' ) r = (r * 10) + (c ^ '0'), c = getchar();
	return r *= b;
}
const int N = 2e5 + 10;
typedef long long llong;

struct Node {
	int nxt[2];
	llong lzy;
	inline int& operator [] (int i) {return nxt[i];}
};
struct SegTree {
	int rt[N], ncnt;
	Node nod[N * 40];
	void update(int u, llong ad) {
		nod[u].lzy += ad;
	}
	void pushDown(int u) {
		if( nod[u].lzy ) {
			int p = ++ncnt, q = ++ncnt;
			nod[p] = nod[nod[u][0]], nod[q] = nod[nod[u][1]];
			update(p, nod[u].lzy);
			update(q, nod[u].lzy);
			nod[u][0] = p, nod[u][1] = q;
			nod[u].lzy = 0;
		}
	}
	void modify(int &u, int v, int le, int ri, int ql, int qr, int ad) {
		u = ++ncnt, nod[u] = nod[v];
		if( ql <= le && ri <= qr ) {
			update(u, ad);
			return;
		}
		pushDown(u);
		int mi = (le + ri) >> 1;
		if( ql <= mi ) modify(nod[u][0], nod[v][0], le, mi, ql, qr, ad);
		if( mi < qr ) modify(nod[u][1], nod[v][1], mi + 1, ri, ql, qr, ad);
	}
	void dModify(int u, int le, int ri, int ql, int qr, llong ad) {
		if( ql <= le && ri <= qr ) {
			update(u, ad);
			return;
		}
		pushDown(u);
		int mi = (le + ri) >> 1;
		if( ql <= mi ) dModify(nod[u][0], le, mi, ql, qr, ad);
		if( mi < qr ) dModify(nod[u][1], mi + 1, ri, ql, qr, ad);
	}
	llong query(int u, int le, int ri, int pos) {
		if( !u ) return 0ll;
		if( le == ri ) return nod[u].lzy;
		int mi = (le + ri) >> 1;
		if( pos <= mi ) return query(nod[u][0], le, mi, pos) + nod[u].lzy;
		else return query(nod[u][1], mi + 1, ri, pos) + nod[u].lzy;
	}
	void debug(int u, int le, int ri, int ql, int qr, llong dow) {
		if( ql <= le && ri <= qr && le == ri ) {
			printf("%lld ", dow + nod[u].lzy);
			return;
		}
		int mi = (le + ri) >> 1;
		if( ql <= mi ) debug(nod[u][0], le, mi, ql, qr, dow + nod[u].lzy);
		if( mi < qr ) debug(nod[u][1], mi + 1, ri, ql, qr, dow + nod[u].lzy);
	}
	inline int& operator [](int i) {return rt[i];}
} se;

int n, m, nstk;
int arp[N], ara[N], arb[N], stk[N];
vector<int> lnk[N];
set<int> fix;

llong dist(int s, int t) {return se.query(se[t], 1, n, s);}
int main() {
	rin(n), rin(m);
	for(int i = 1; i <= n; i++) rin(arp[i]);
	for(int i = 1; i <= n; i++) rin(ara[i]);
	for(int i = 1; i <= n; i++) rin(arb[i]);
	arp[n + 1] = n + 1, stk[nstk = 1] = n + 1;
	for(int i = n; i; i--) {
		while( nstk && arp[stk[nstk]] < arp[i] ) nstk--;
		lnk[stk[nstk]].push_back(i);
		stk[++nstk] = i;
	}
	se[1] = ++se.ncnt;
	for(int i = 2; i <= n + 1; i++) {
		// printf("done %d\n", i);
		se.modify(se[i], se[i - 1], 1, n, 1, i - 1, ara[i - 1]);
		for(int j = 0, _j = (int)lnk[i].size(); j < _j; j++) {
			int k = lnk[i][j];
			llong tmp = se.query(se[i], 1, n, k);
			// printf(" %d -> %d: %lld -> %d\n", k, i, tmp, arb[k]);
			if( tmp > arb[k] ) se.dModify(se[i], 1, n, 1, k, arb[k] - tmp);
		}
		// se.debug(se[i], 1, n, 1, i - 1, 0), printf("\n");
	}
	llong ans = dist(1, n + 1);
	fix.insert(1), fix.insert(n + 1);
	for(int i = 1, s; i <= m; i++) {
		rin(s);
		if( s == 1 ) {
			printf("%lld\n", ans);
			continue;
		}
		if( fix.count(s) ) {
			set<int>::iterator it = fix.find(s);
			int pl = *(--it); it++;
			int pr = *(++it); it--;
			ans = ans - dist(pl, s) - dist(s, pr) + dist(pl, pr);
			fix.erase(it);
		}
		else {
			fix.insert(s);
			set<int>::iterator it = fix.find(s);
			int pl = *(--it); it++;
			int pr = *(++it); it--;
			ans = ans + dist(pl, s) + dist(s, pr) - dist(pl, pr);
		}
		printf("%lld\n", ans);
	}
	return 0;
}