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 <bits/stdc++.h>
using namespace std;
#define pb push_back

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int randint(int L,int R){
    return uniform_int_distribution < int > (L,R)(rng);
}
#define int long long
void minn(int &a,int b){
if(b<a) a=b;
}
using ii = pair < int , int > ;
const int inf=0x3f3f3f3f,MAX=2e5+10;
using ll = long long;
//#define int long long
int ans=0;
int D[MAX],F[18][MAX];
int a[MAX],b[MAX],c[MAX];
int Sc[MAX],H[MAX];
int gcos(int u,int v){
    int x=u;
    for(int i=17;i>=0;i--)
        if(F[i][x]<=v) x=F[i][x];
    //cout<<x<<'\n';cout<<u<<' '<<x<<' '<<v<<' '<<Sc[u]-Sc[x]+H[v]-H[x]<<'\n';
    return Sc[u]-Sc[x]+H[v]-H[x];
}
bool aliv[MAX];
set < int > S;
void add(int x){
    auto it=S.upper_bound(x);
    int u=*prev(it),v=*it;
    ans+=gcos(u,x)+gcos(x,v)-gcos(u,v);
    //cout<<u<<' '<<x<<' '<<v<<'\n';
    aliv[x]=1;
    S.insert(x);
}
void pop(int x){
    S.erase(x);
    auto it=S.upper_bound(x);
    int u=*prev(it),v=*it;
    ans-=gcos(u,x)+gcos(x,v)-gcos(u,v);
    aliv[x]=0;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("bao.inp","r",stdin);
    //freopen("bao.inp","w",stdout);
    int n,Q;
    cin>>n>>Q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    for(int i=1;i<=n;i++){
        cin>>c[i];
    }
    int top=0;
    D[0]=n+1;
    a[n+1]=a[0]=inf;
    for(int i=n;i>0;i--){
        int temp=b[i];
        while(a[D[top]]<a[i])
            temp+=c[D[top--]];
        F[0][i]=D[top];
        minn(c[i],temp);
        Sc[i]=Sc[D[top]]+c[i];
        //cout<<i<<' '<<temp<<'\n';
        D[++top]=i;
    }
    top=0;
    for(int i=1;i<=n;i++){
        while(a[D[top]]<a[i]) top--;
        H[i]=H[D[top]]+Sc[D[top]+1]-Sc[i]+b[D[top]];
        D[++top]=i;
    }
    F[0][n+1]=n+2;
    F[0][n+2]=n+2;
    for(int i=1;i<18;i++){
        for(int j=1;j<=n+2;j++)
            F[i][j]=F[i-1][F[i-1][j]];
    }
    int x;
    S.insert(1);S.insert(n+1);
    ans=gcos(1,n+1);
    //cout<<c[1]<<c[3]<<'\n';
    //cout<<Sc[1]<<' '<<Sc[3]<<'\n';
    //cout<<ans<<'\n';
    //return 0;
    while(Q--){
        cin>>x;
        if(x!=1){
            if(aliv[x])
                pop(x);
            else add(x);
        }
        cout<<ans<<'\n';
    }
}