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 <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define int long long
#define ull unsigned long long
#define fi first
#define se second
#define mpr make_pair
#define dingyi int mid = l + r >> 1, ls = p << 1, rs = p << 1 | 1
#define y0 y_csyakioi_0
#define y1 y_csyakioi_1
#define rep(i, x, y) for(int i = x; i <= y; ++i)
#define per(i, x, y) for(int i = x; i >= y; --i)
#define repg(i, u) for(int i = head[u]; i; i = e[i].nxt)
inline int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
	return x * f;
}
const int N = 200010;
int n, m, p[N], a[N], b[N], dis[N], dep[N], f[N][20], c[N], sta[N], len, cnt[N], ans;
set <int> st; set <int> ::iterator it; bool vis[N];
inline int lca(int x, int y){
	if(dep[x] < dep[y]) swap(x, y); per(i, 18, 0) if(dep[f[x][i]] >= dep[y]) x = f[x][i];
	if(x == y) return x; per(i, 18, 0) if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
	return f[x][0];
}
inline int pat(int x, int y){ return dis[x] + dis[y] - 2 * dis[lca(x, y)]; }
inline void Insert(int x){
	it = st.insert(x).fi; int y = *(--it); ++it; ++it;
	int z = ((it == st.end()) ? *st.begin() : *it);
	ans += pat(y, x) + pat(x, z) - pat(y, z);
}
inline void Delete(int x){
	it = st.find(x); int y = *(--it); ++it; ++it;
	int z = ((it == st.end()) ? *st.begin() : *it);
	ans -= pat(y, x) + pat(x, z) - pat(y, z);
	--it; st.erase(it);
} 
inline void mian(){
	n = read(); m = read();
	rep(i, 1, n){
		p[i] = read(); while(p[sta[len]] < p[i] && len) --len;
		dep[i] = dep[f[i][0] = sta[len]] + 1; sta[++len] = i;
		rep(j, 1, 18) f[i][j] = f[f[i][j - 1]][j - 1];
	}
	rep(i, 1, n) a[i] = read(), c[i] += a[i];
	rep(i, 1, n) b[i] = read(), c[i] -= b[i], c[f[i][0]] += b[i];
	per(i, n, 1) dis[f[i][0]]  += min(dis[i] += c[i], 0ll), dis[i] -= min(0ll, dis[i]);
	dis[0] += c[0]; rep(i, 1, n) dis[i] += dis[f[i][0]]; cnt[0] = 1; st.insert(0);
	while(m--){
		int x = read();
		if(vis[x]){
			vis[x] = 0;
			if(!(--cnt[f[x][0]])) Delete(f[x][0]);
		}
		else{
			vis[x] = 1;
			if(!(cnt[f[x][0]]++)) Insert(f[x][0]);
		}
		printf("%lld\n", ans / 2 + dis[0]);
	}
}
signed main(){ int qwq = 1; while(qwq--) mian(); return 0; }