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 <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#else
	#define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}

const ll INF = (ll)1e18;
const int N = 200200;
const int LOG = 18;
vector<int> g[N];
int par[N][LOG];
ll costPar[N][LOG];
int h[N];
ll a[N], b[N];
int c[N];
int n, m, q;
int Q[N];
pair<pii, ll> allQ[3 * N];
int st[N];
int stSz;
ll pref[N];

void read() {
	scanf("%d%d", &n, &q);
	for (int i = 0; i < n; i++) {
		scanf("%d", &c[i]);
		c[i]--;
	}
	c[n] = n;
	for (int i = 0; i < n; i++)
		scanf("%lld", &a[i]);
	for (int i = 0; i < n; i++)
		scanf("%lld", &b[i]);
	set<int> setik;
	setik.insert(0);
	setik.insert(n);
	allQ[m++] = mp(mp(n, 0), 0);
	for (int i = 0; i < q; i++) {
		scanf("%d", &Q[i]);
		Q[i]--;
		if (Q[i] == 0) continue;
		if (setik.count(Q[i])) {
			setik.erase(Q[i]);
			auto it = setik.lower_bound(Q[i]);
			assert(it != setik.end());
			assert(it != setik.begin());
			int r = *it;
			it--;
			int l = *it;
			allQ[m++] = mp(mp(r, l), 0);
		} else {
			auto it = setik.lower_bound(Q[i]);
			assert(it != setik.end());
			assert(it != setik.begin());
			int r = *it;
			it--;
			int l = *it;
			allQ[m++] = mp(mp(Q[i], l), 0);
			allQ[m++] = mp(mp(r, Q[i]), 0);
			setik.insert(Q[i]);
		}
	}
	sort(allQ, allQ + m);
	m = unique(allQ, allQ + m) - allQ;
}

ll getCostUp(int v, int u) {
	eprintf("getCostUp %d %d\n", v, u);
	assert(h[u] <= h[v]);
	ll res = 0;
	for (int k = LOG - 1; k >= 0; k--) {
		if (h[v] < h[u] + (1 << k)) continue;
		res += costPar[v][k];
		v = par[v][k];
	}
	assert(v == u);
	return res;
}

void precalc() {
	for (int i = 0; i <= n; i++) {
		while(stSz > 0 && c[st[stSz - 1]] < c[i]) {
			stSz--;
			int v = st[stSz];
			eprintf("addEdge %d %d\n", v, i);
			par[v][0] = i;
			g[i].push_back(v);
		}
		st[stSz++] = i;
	}
	assert(stSz == 1);
	for (int k = 0; k < LOG; k++) {
		par[n][k] = n;
		costPar[n][k] = 0;
	}
	for (int v = n - 1; v >= 0; v--) {
		h[v] = h[par[v][0]] + 1;
		costPar[v][0] = min(b[v], a[v] + getCostUp(v + 1, par[v][0]));
		for (int k = 0; k < LOG - 1; k++) {
			par[v][k + 1] = par[par[v][k]][k];
			costPar[v][k + 1] = costPar[v][k] + costPar[par[v][k]][k];
		}
	}
	stSz = 0;
	int ptr = 0;
	for (int v = 0; v <= n; v++) {
		while(stSz > 0 && c[st[stSz - 1]] < c[v]) {
			stSz--;
		}
		if (stSz > 0) {
			pref[stSz] = pref[stSz - 1] + a[st[stSz - 1]] + getCostUp(st[stSz - 1] + 1, v);
		}
		st[stSz++] = v;
		while(ptr < m && allQ[ptr].first.first == v) {
			int u = allQ[ptr].first.second;
			int pos = lower_bound(st, st + stSz, u) - st;
			allQ[ptr].second = getCostUp(u, st[pos]) + pref[stSz - 1] - pref[pos];
			ptr++;
		}
	}
}

ll query(int l, int r) {
	int pos = lower_bound(allQ, allQ + m, mp(mp(r, l), -INF)) - allQ;
	assert(pos < m && allQ[pos].first == mp(r, l));
	return allQ[pos].second;
}

int main()
{
	startTime = clock();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	read();
	precalc();
	ll ans = query(0, n);
	set<int> setik;
	setik.insert(0);
	setik.insert(n);
	for (int i = 0; i < q; i++) {
		if (Q[i] != 0) {
			if (setik.count(Q[i])) {
				setik.erase(Q[i]);
				auto it = setik.lower_bound(Q[i]);
				assert(it != setik.end());
				assert(it != setik.begin());
				int r = *it;
				it--;
				int l = *it;
				ans -= query(l, Q[i]);
				ans -= query(Q[i], r);
				ans += query(l, r);
			} else {
				auto it = setik.lower_bound(Q[i]);
				assert(it != setik.end());
				assert(it != setik.begin());
				int r = *it;
				it--;
				int l = *it;
				ans += query(l, Q[i]);
				ans += query(Q[i], r);
				ans -= query(l, r);
				setik.insert(Q[i]);
			}
		}
		printf("%lld\n", ans);
	}


	return 0;
}