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:
/*input
3 2
2 1 3
10 -5 4
3 -2 3
1
2

*/

// umm, maybe? ...
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <tuple>
#include <cassert>

using namespace std;

const int MAXN = 200007, LOG = 18;
int N, Q, P[MAXN], nxt[MAXN], prv[MAXN], jumpDest[LOG][MAXN], backDest[LOG][MAXN];
int64_t jumpCost[LOG][MAXN], backCost[LOG][MAXN], A[MAXN], B[MAXN], curCost[MAXN], curTotal;
set<int> forced;

int64_t getJumpCost(int s, int t) {
	int64_t cost = 0;
	for (int j = LOG - 1; j >= 0; --j) {
		if (jumpDest[j][s] <= t) {
			cost += jumpCost[j][s];
			s = jumpDest[j][s];
		}
	}
	assert(s == t);
	return cost;
}

int64_t getCost(int s, int t) {
	int64_t cost = 0;
	for (int j = LOG - 1; j >= 0; --j) {
		if (jumpDest[j][s] <= t) {
			cost += jumpCost[j][s];
			s = jumpDest[j][s];
		}
		if (backDest[j][t] >= s) {
			cost += backCost[j][t];
			t = backDest[j][t];
		}
	}
	assert(s == t);
	return cost;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> Q;
	for (int i = 1; i <= N; ++i) cin >> P[i];
	for (int i = 1; i <= N; ++i) cin >> A[i];
	for (int i = 1; i <= N; ++i) cin >> B[i];

	P[0] = N + 1, P[N + 1] = N + 1;
	for (int j = 0; j < LOG; ++j) {
		jumpDest[j][N + 1] = N + 1;
		jumpCost[j][N + 1] = 0;

		backDest[j][0] = 0;
		backCost[j][0] = 0;
	}

	for (int i = N; i >= 1; --i) {
		for (nxt[i] = i + 1; P[nxt[i]] < P[i]; nxt[i] = nxt[nxt[i]]);

		if (P[i] < P[i + 1]) B[i] = min(B[i], A[i]);
		else B[i] = min(B[i], A[i] + getJumpCost(i + 1, nxt[i]));

		jumpDest[0][i] = nxt[i], jumpCost[0][i] = B[i];
		for (int j = 1; j < LOG; ++j) {
			int x = jumpDest[j - 1][i];
			jumpDest[j][i] = jumpDest[j - 1][x];
			jumpCost[j][i] = jumpCost[j - 1][i] + jumpCost[j - 1][x];
		}
	}

	for (int i = 1; i <= N; ++i) {
		for (prv[i] = i - 1; P[prv[i]] < P[i]; prv[i] = prv[prv[i]]);

		int64_t c;
		if (P[i] < P[i - 1]) c = A[i - 1];
		else c = A[prv[i]] + getJumpCost(prv[i] + 1, i);

		backDest[0][i] = prv[i], backCost[0][i] = c;
		for (int j = 1; j < LOG; ++j) {
			int x = backDest[j - 1][i];
			backDest[j][i] = backDest[j - 1][x];
			backCost[j][i] = backCost[j - 1][i] + backCost[j - 1][x];
		}
	}

	forced.insert(1);
	forced.insert(N + 1);
	curTotal = curCost[1] = getCost(1, N + 1);
	while (Q--) {
		int x;
		cin >> x;

		if (x != 1) {
			set<int>::iterator i;
			bool add;
			tie(i, add) = forced.insert(x);
			if (!add) {
				curTotal -= curCost[*i] + curCost[*prev(i)];
				curTotal += (curCost[*prev(i)] = getCost(*prev(i), *next(i)));
				forced.erase(i);
			} else {
				curTotal -= curCost[*prev(i)];
				curTotal += (curCost[*prev(i)] = getCost(*prev(i), *i));
				curTotal += (curCost[*i] = getCost(*i, *next(i)));
			}
		}
		cout << curTotal << '\n';
	}
}