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;
namespace Flandre_Scarlet
{
    #define N 200005
    #define int long long
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.st(u),v=G.to(i);~i;i=G.nx(i),v=G.to(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define all(a) a.begin(),a.end()
    #define iter(a,p) (a.begin()+p)
    #define PUT(a,n) F(i,0,n) printf("%lld ",a[i]); puts("");
    int I() {char c=getchar(); int x=0; int f=1; while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar(); while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return ((f==1)?x:-x);}
    template <typename T> void Rd(T& arg){arg=I();}
    template <typename T,typename...Types> void Rd(T& arg,Types&...args){arg=I(); Rd(args...);}
    void RA(int *p,int n) {F(i,1,n) *p=I(),++p;}
    int n,q;
    int p[N],a[N],b[N];
    void Input()
    {
        Rd(n,q);
        RA(p+1,n); RA(a+1,n); RA(b+1,n);
    }
    int st[N],top;
    int fa[N],dep[N]; int jp[N][22];
    int LCA(int u,int v)
    {
        if (dep[u]<dep[v]) swap(u,v);
        D(i,20,0) if (dep[jp[u][i]]>=dep[v]) u=jp[u][i];
        if (u==v) return u;
        D(i,20,0) if (jp[u][i]!=jp[v][i]) u=jp[u][i],v=jp[v][i];
        return fa[u];
    }
    int c[N]; int dis[N];
    int pathlen(int u,int v) {return dis[u]+dis[v]-2ll*dis[LCA(u,v)];}
    set<int> s; set<int> ::iterator it;
    int cursum=0;
    int vis[N]; bool visx[N];
    void add(int x)
    {
        s.insert(x); it=s.find(x); --it;
        int pre=*it;
        ++it; ++it;
        if (it==s.end()) it=s.begin();
        int nex=*it;
        cursum-=pathlen(pre,nex); cursum+=pathlen(pre,x)+pathlen(x,nex);
    }
    void del(int x)
    {
        it=s.find(x); --it; 
        int pre=*it;
        ++it; ++it;
        if (it==s.end()) it=s.begin();
        int nex=*it;
        cursum-=pathlen(pre,x)+pathlen(x,nex); cursum+=pathlen(pre,nex); 
        s.erase(x);
    }
    void Sakuya()
    {
        F(i,1,n)
        {
            while(top and p[st[top]]<p[i]) --top;
            fa[i]=st[top];
            st[++top]=i;
        }
        dep[0]=0; F(i,1,n) dep[i]=dep[fa[i]]+1;
        F(i,1,n) jp[i][0]=fa[i]; F(i,1,20) F(j,1,n) jp[j][i]=jp[jp[j][i-1]][i-1];

        F(i,1,n) c[i]+=a[i]-b[i],c[fa[i]]+=b[i];
        D(i,n,0)
        {
            dis[i]+=c[i];
            if (dis[i]<0ll and i)
            {
                dis[fa[i]]+=dis[i];
                dis[i]=0;
            }
        }
        F(i,1,n) dis[i]+=dis[fa[i]];

        vis[0]=1; s.insert(0);
        F(i,1,q)
        {
            int x=I();
            if (!visx[x]) // add
            {
                visx[x]=1;
                if (!vis[fa[x]]) add(fa[x]);
                ++vis[fa[x]];
            }
            else // del
            {
                visx[x]=0;
                if (vis[fa[x]]==1) del(fa[x]);
                --vis[fa[x]];
            }
            printf("%lld\n",cursum/2+dis[0]);
        }
    }
    void IsMyWife()
    {
        Input();
        Sakuya();
    }
}
#undef int //long long
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();
    return 0;
}