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 <stdio.h>
#include <sys/time.h>

#define N	200000
#define Q	200000
#define N_	(1 << 18)	/* N_ = pow2(ceil(log2(N + 1))) */

unsigned int X;

void srand_() {
	struct timeval tv;

	gettimeofday(&tv, NULL);
	X = tv.tv_sec ^ tv.tv_usec;
	if (X % 2 == 0)
		X++;
}

int rand_() {
	return (X *= 3) >> 1;
}

int zz[1 + Q + 2], ll[1 + Q + 2], rr[1 + Q + 2], kk[1 + Q + 2], u_, l_, r_;

int node(int k) {
	static int _ = 1;

	zz[_] = rand_();
	kk[_] = k;
	return _++;
}

void split(int u, int k) {
	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	if (kk[u] < k) {
		split(rr[u], k);
		rr[u] = l_, l_ = u;
	} else if (kk[u] > k) {
		split(ll[u], k);
		ll[u] = r_, r_ = u;
	} else {
		u_ = u, l_ = ll[u], r_ = rr[u];
		ll[u] = rr[u] = 0;
	}
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v);
		return u;
	} else {
		ll[v] = merge(u, ll[v]);
		return v;
	}
}

int first(int u) {
	return ll[u] == 0 ? u : first(ll[u]);
}

int last(int u) {
	return rr[u] == 0 ? u : last(rr[u]);
}

int ii[Q * 3], jj[Q * 3];

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (ii[hh[j]] == ii[h])
				j++;
			else if (ii[hh[j]] < ii[h]) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		sort(hh, l, i);
		l = k;
	}
}

long long st[N_ * 2]; int n_;

void update(int l, int r, long long x) {
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			st[l++] += x;
		if ((r & 1) == 0)
			st[r--] += x;
	}
}

long long query(int i) {
	long long x;

	x = 0;
	for (i += n_; i > 0; i >>= 1)
		x += st[i];
	return x;
}

int main() {
	static int pp[N + 1], qu[N + 1], tt[Q], hh[Q * 3];
	static long long aa[N + 1], bb[N], ans[Q];
	int n, q, q_, h, i, cnt;

	srand_();
	scanf("%d%d", &n, &q);
	for (i = 0; i < n; i++)
		scanf("%d", &pp[i]), pp[i]--;
	pp[n] = n;
	for (i = 1; i <= n; i++) {
		scanf("%lld", &aa[i]);
		aa[i] += aa[i - 1];
	}
	for (i = 0; i < n; i++)
		scanf("%lld", &bb[i]);
	u_ = merge(node(0), node(n));
	q_ = 0;
	for (h = 0; h < q; h++) {
		scanf("%d", &i), i--;
		if (i != 0) {
			int p, q;

			split(u_, i);
			p = kk[last(l_)], q = kk[first(r_)];
			if (u_ == 0)
				u_ = node(i), tt[h] = 1;
			else
				u_ = 0, tt[h] = 2;
			ii[h * 3 + 0] = p, jj[h * 3 + 0] = q, hh[q_++] = h * 3 + 0;
			ii[h * 3 + 1] = p, jj[h * 3 + 1] = i, hh[q_++] = h * 3 + 1;
			ii[h * 3 + 2] = i, jj[h * 3 + 2] = q, hh[q_++] = h * 3 + 2;
			u_ = merge(merge(l_, u_), r_);
		}
	}
	sort(hh, 0, q_);
	n_ = 1;
	while (n_ < n + 1)
		n_ <<= 1;
	cnt = 0;
	qu[cnt++] = n;
	for (i = n - 1, h = q_ - 1; i >= 0; i--) {
		int j;
		long long x;

		while (cnt && pp[qu[cnt - 1]] < pp[i])
			cnt--;
		j = qu[cnt - 1];
		qu[cnt++] = i;
		bb[i] = aa[j] - aa[i] - bb[i];
		if ((x = query(j)) < bb[i])
			update(j, n, bb[i] - x);
		while (h >= 0 && ii[hh[h]] == i) {
			ans[hh[h] / 3] -= query(jj[hh[h]]) * ((hh[h] % 3 == 0) == (tt[hh[h] / 3] == 2) ? 1 : -1);
			h--;
		}
	}
	ans[0] += aa[n] - query(n);
	for (h = 1; h < q; h++)
		ans[h] += ans[h - 1];
	for (h = 0; h < q; h++)
		printf("%lld\n", ans[h]);
	return 0;
}