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:
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define INF 2147483647
#define infL (1LL<<60)
#define inf (1<<30)
#define inf9 (1000000000)
#define MOD 1000000007//998244353//1000000007
#define EPS 1e-9
#define Gr 9.8
#define PI acos(-1)
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REQ(i,n) for(int (i)=1;(i)<=(int)(n);(i)++)
#define lch (rt<<1)
#define rch (rt<<1|1)
#define readmp(n) for(int i=0,u,v;i<n;i++) {scanf("%d%d",&u,&v); mp[u].push_back(v); mp[v].push_back(u);}
typedef  long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef ll ValType;
template<typename  T> void maxtt(T& t1, T t2) {
    t1=max(t1,t2);
}
template<typename  T> void mintt(T& t1, T t2) {
    t1=min(t1,t2);
}
#define MAX (200135)

bool debug = 0;
int n,m,k;
int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};
string direc="RDLU";
const ll MOD2 = (ll)MOD * (ll)MOD;
ll ln, lk, lm;
void etp(bool f = 0) {
    puts(f ?"YES" : "NO");
    exit(0);
}
void addmod(int &x, int y, int mod = MOD){
    x+=y; if (x>=mod) x-=mod;
    if(x<0) x+=mod;
    assert(x>=0 && x<mod);
}
void et(int x=-1) {
    printf("%d\n", x); exit(0);
}
ll fastPow(ll x, ll y, int mod=MOD) {
    ll ans = 1;
    while(y>0) {
        if(y&1) ans = (x * ans)%mod;
        x = x*x%mod;
        y>>=1;
    }
    return ans;
}
ll gcd1(ll x, ll y) {
    return y?gcd1(y,x%y):x;
}




int p[MAX][20], nxt[MAX],a[MAX],b[MAX];
int d[MAX], P[MAX], cnt[MAX];
ll dis[MAX], S;
bool vis[MAX];
set<int> sp;
void initlca(){
    for(int j=1; (1<<j)<=n; j++)
        for(int i=1; i<=n; i++)
            p[i][j]=p[p[i][j-1]][j-1];
}
int lca(int a,int b) {
    if(d[a]>d[b])swap(a,b);
    int f=d[b]-d[a];
    for(int i=0; (1<<i)<=f; i++)
        if((1<<i)&f)b=p[b][i];
    if(a!=b) {
        for(int i=18; i>=0; i--)
            if(p[a][i]!=p[b][i]) {
                a=p[a][i]; b=p[b][i];
            }
        a=p[a][0];
    }
    return a;
}
void init() {
    vector<int> vp; vp.push_back(0);
    REQ(i,n) {
        while (vp.size()>1 && P[vp.back()] < P[i]) {
            vp.pop_back();
        }
        p[i][0]=vp.back();
        d[i]=d[p[i][0]]+1;
        vp.push_back(i);
    }
    initlca();
    vector<ll> c(n+5,0);
    REQ(i,n) {
        c[i]+=a[i]-b[i];
        c[p[i][0]]+=b[i];
    }
    for(int i=n;i;i--) {
        dis[i]+=c[i];
        dis[p[i][0]] += min(0LL, dis[i]);
        if(dis[i]<0) dis[i]=0;
    }
    dis[0]+=c[0];
    REQ(i,n) dis[i]+=dis[p[i][0]];
}
ll cal(int x, int y) {
    return dis[x]+dis[y]-dis[lca(x,y)]*2;
}
void add(int x) {
    auto it=sp.upper_bound(x);
    int r=0;
    if (it!=sp.end()) r=*it;
    it--;
    int l=*it;
    S += cal(l,x)+cal(x,r)-cal(l,r);
    sp.insert(x);
}
void del(int x) {
    auto it=sp.lower_bound(x);
    it--;
    int l=*it;
    it++;
    it++;
    int r=it==sp.end() ? 0 : *it;
    S -= cal(l,x)+cal(x,r)-cal(l,r);
    sp.erase(x);
}
void fmain(int tid) {
    scanf("%d%d", &n, &m);
    REQ(i,n) {
        scanf("%d", P+i);
    }
    REQ(i,n) scanf("%d", a+i);
    REQ(i,n) scanf("%d", b+i);
    init();
    cnt[0]=1; sp.insert(0);
    REQ(i,m) {
        int x; scanf("%d", &x);
        if (!vis[x]) {
            vis[x]=1;
            ++cnt[p[x][0]];
            if (cnt[p[x][0]]==1) add(p[x][0]);
        } else {
            vis[x]=0; --cnt[p[x][0]];
            if (cnt[p[x][0]]==0) del(p[x][0]);
        }
        printf("%lld\n",S/2+dis[0]);
    }
}
int main() {
    int t=1;
//    init();
//    scanf("%d", &t);
    REQ(i,t) {
        fmain(i);
    }
    return 0;
}