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;
const uint64_t seed = std::chrono::system_clock::now().time_since_epoch().count();
mt19937_64 rnd(seed);
const int MOD = 998244353;

#ifdef VIPJML_LOCAL
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << "{";
    for (typename vector<T>::const_iterator vi = v.begin(); vi != v.end(); ++vi)
    {
        if (vi != v.begin())
            os << ", ";
        os << *vi;
    }
    os << "}";
    return os;
}
template <typename A, typename B>
ostream &operator<<(ostream &os, const vector<pair<A, B>> &v)
{
    os << "{";
    for (typename vector<pair<A, B>>::const_iterator vi = v.begin(); vi != v.end(); ++vi)
    {
        if (vi != v.begin())
            os << ", ";
        os << '(' << vi->first << " " << vi->second << ")";
    }
    os << "}";
    return os;
}

template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p)
{
    os << '(' << p.first << ", " << p.second << ')';
    return os;
}

void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T)
{
    cerr << ' ' << H;
    dbg_out(T...);
}
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
using LL = long long;

void solve(int caseNum)
{
    int n, q;
    cin >> n >> q;
    vector<int> a(n), b(n), p(n);
    for (int i = 0; i < n; i++)
        cin >> p[i];

    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> b[i];
    vector<int> nn(n, n);
    stack<int> ss;
    for (int i = 0; i < n; i++)
    {
        while (ss.size() != 0 && p[ss.top()] < p[i])
        {
            nn[ss.top()] = i;
            ss.pop();
        }
        ss.push(i);
    }
    ss = stack<int>();
    vector<int> pa(n, -1);
    for (int i = 0; i < n; i++)
    {
        while (ss.size() > 0 && nn[ss.top()] == i)
        {
            ss.pop();
        }
        if (!ss.empty())
        {
            pa[i] = ss.top();
        }
        ss.push(i);
    }
    dbg(p, nn, pa);
    vector<vector<int>> g(n);
    for (int i = 0; i < n; i++)
    {
        if (pa[i] != -1)
        {
            g[pa[i]].push_back(i);
        }
    }
    vector<LL> sum(n + 1, 0);
    for (int i = 0; i < n; i++)
        sum[i + 1] = sum[i] + a[i];
    vector<LL> w(n), w2(n), psum(n);
    vector<bool> vis(n, false);
    function<void(int)> dfs = [&](int c) {
        vis[c] = true;
        LL d = sum[nn[c]] - sum[c];
        LL dd2 = d - b[c];
        LL dd1 = 0;
        for (int ne : g[c])
        {
            dfs(ne);
            dd1 += w[ne];
        }
        w[c] = max(dd1, dd2);
        w2[c] = w[c] - dd1;
    };
    for (int i = 0; i < n; i++)
    {
        if (!vis[i])
        {
            dfs(i);
        }
    }

    fill(vis.begin(), vis.end(), false);
    vector<vector<int>> ppa(n, vector<int>(22, 0));
    vector<int> hh(n, -1);
    vector<int> height(n, 0);
    function<void(int, int, LL, int, int)> dfs2 = [&](int c, int par, LL ps, int tr, int hi) {
        vis[c] = true;
        hh[c] = tr;
        height[c] = hi;
        psum[c] = ps + w2[c];
        ppa[c][0] = par;
        for (int j = 1; j < 22; j++)
        {
            ppa[c][j] = ppa[ppa[c][j - 1]][j - 1];
        }
        for (int ne : g[c])
        {
            dfs2(ne, c, psum[c], tr, hi + 1);
        }
    };
    LL ans = sum.back();
    for (int i = 0; i < n; i++)
    {
        if (!vis[i])
        {
            dfs2(i, i, 0, i, 0);
            ans -= w[i];
        }
    }

    auto lca = [&](int p1, int p2) {
        if (height[p1] > height[p2])
        {
            swap(p1, p2);
        }
        int d = height[p2] - height[p1];
        for (int i = 0; d != 0; d >>= 1, i++)
        {
            if (d & 1)
                p2 = ppa[p2][i];
        }
        if (p1 == p2)
            return p1;
        for (int j = 21; j >= 0; j--)
        {
            if (ppa[p1][j] != ppa[p2][j])
            {
                p1 = ppa[p1][j];
                p2 = ppa[p2][j];
            }
        }
        return ppa[p1][0];
    };
    dbg(w, w2, psum);

    dbg(ans);
    set<int> sss;
    auto getV = [&](int v) {
        LL res = psum[v];
        auto it = sss.find(v);
        if (it != sss.begin())
        {
            int l = *prev(it);
            if (hh[v] == hh[l])
            {
                res = min(res, psum[v] - psum[lca(v, l)]);
            }
        }

        if (next(it) != sss.end())
        {
            int r = *next(it);
            if (hh[v] == hh[r])
                res = min(res, psum[v] - psum[lca(v, r)]);
        }

        return res;
    };
    vector<int> vcnt(n, 0);
    vector<int> flag(n, false);
    for (int i = 0; i < q; i++)
    {
        int av;
        cin >> av;
        av--;
        flag[av] = !flag[av];
        int v = pa[av];
        if (v != -1)
        {
            if (flag[av])
            {
                vcnt[v]++;
            }
            else
                vcnt[v]--;
            if (vcnt[v] == 0 && !flag[av])
            {
                LL d = getV(v);
                sss.erase(v);
                ans -= d;
            }
            else if (vcnt[v] == 1 && flag[av])
            {
                sss.insert(v);
                LL d = getV(v);
                ans += d;
            }
        }

        cout << ans << endl;
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.precision(10);
    int T = 1;
    //cin >> T;
    for (int i = 1; i <= T; i++)
    {
        solve(i);
    }
    cout.flush();
    return 0;
}