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>

const int N = 200010;
const int BIT = 18;
using ll = long long;

std::vector <int> e[N];
int p[N], a[N], b[N], fa[N], father[N][BIT];
ll fa_value[N][BIT];
ll w[N], dp[N], diff[N];
int dep[N], dfn[N], dfncnt;
bool vis[N];

void dfs(int u){
    dfn[u] = ++ dfncnt;
    dp[u] = w[u];
    for (auto v : e[u]){
        dep[v] = dep[u] + 1;
        dfs(v);
        dp[u] += dp[v];
    }
    dp[u] = std::min(0ll, dp[u]);
}

void dfs1(int u, int fat){
    father[u][0] = fat;
    fa_value[u][0] = diff[u];
    for (int i = 1; i < BIT; ++ i){
        if (father[u][i - 1] == -1){
            father[u][i] = -1;
            fa_value[u][i] = fa_value[u][i - 1];
            continue;
        }
        father[u][i] = father[father[u][i - 1]][i - 1];
        fa_value[u][i] = fa_value[u][i - 1] + fa_value[father[u][i - 1]][i - 1];
    }
    for (auto v : e[u]){
        dfs1(v, u);
    }
}

int lca(int u, int v){
    if (dep[u] < dep[v]){
        std::swap(u, v);
    }
    for (int i = 0; i < BIT; ++ i){
        if ((dep[u] - dep[v]) >> i & 1){
            u = father[u][i];
        }
    }
    if (u == v) return u;
    for (int i = BIT - 1; i >= 0; -- i){
        if (father[u][i] != father[v][i]){
            u = father[u][i], v = father[v][i];
        }
    }
    return father[u][0];
}

struct Compare{
    bool operator () (const int &p1, const int &p2)const{
        return dfn[p1] < dfn[p2];
    }
};

int main(){
    int n, q;
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++ i){
        scanf("%d", &p[i]);
    }
    for (int i = 1; i <= n; ++ i){
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; ++ i){
        scanf("%d", &b[i]);
    }
    std::vector <int> stack;
    p[0] = n + 1;
    for (int i = 0; i <= n; ++ i){
        while (!stack.empty() && p[stack.back()] < p[i]){
            stack.pop_back();
        }
        if (i){
            e[stack.back()].emplace_back(i);
            fa[i] = stack.back();
        }
        stack.emplace_back(i);
    }
    for (int i = 0; i <= n; ++ i){
        w[i] = a[i] - b[i];
        for (auto u : e[i]){
            w[i] += b[u];
        }
    }
    dfs(0);
    for (int i = 0; i <= n; ++ i){
        diff[i] = -dp[i] + w[i];
        for (auto u : e[i]){
            diff[i] += dp[u];
        }
    }
    dfs1(0, -1);
    ll cur = dp[0] + diff[0];
    std::map <int, int, Compare> map;
    map[0] = 1;
    while (q --){
        int node;
        scanf("%d", &node);
        int coe = vis[node] ? -1 : 1;
        if (!vis[node]){
            vis[node] = true;
            node = fa[node];
            map[node] += 1;
            if (map[node] >= 2){
                printf("%lld\n", cur);
                continue;
            }
        }
        else{
            vis[node] = false;
            node = fa[node];
            map[node] -= 1;
            if (map[node] >= 1){
                printf("%lld\n", cur);
                continue;
            }
            map.erase(node);
        }
        auto u = map.upper_bound(node);
        int x = u == map.end() ? -1 : u -> first;
        u = map.lower_bound(node);
        int y = u == map.begin() ? -1 : std::prev(u) -> first;
        if (x != -1){
            x = lca(x, node);
        }
        if (y != -1){
            y = lca(y, node);
        }
        if (x == -1 && y == -1){
            cur = dp[0] + diff[0];
            printf("%lld\n", cur);
            continue;
        }
        if (x == -1 || (y != -1 && dep[x] < dep[y])){
            x = y;
        }
        if (x == node){
            printf("%lld\n", cur);
            continue;
        }
        int dep_diff = dep[node] - dep[x];
        for (int i = 0; i < BIT; ++ i){
            if (dep_diff >> i & 1){
                cur += coe * fa_value[node][i];
                node = father[node][i];
            }
        }
        printf("%lld\n", cur);
    }
    return 0;
}