CF1495F.Squares

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,\dots,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 \gt i, p_j \gt 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.

地面上从左到右画有 $n$ 个方格。第 $i$ 个方格上写有三个整数 $p_i, a_i, b_i$。序列 $p_1, p_2, \dots, p_n$ 构成一个排列。

每轮游戏你都从最左侧的方格 $1$ 出发，向右跳跃。若当前位于第 $i$ 个方格，则可执行以下两种操作之一：

1. 跳至第 $i+1$ 个方格，并支付代价 $a_i$；若 $i = n$，则可直接结束本轮，并支付代价 $a_i$。
2. 跳至第 $j$ 个方格，并支付代价 $b_i$，其中 $j$ 是满足 $j > i$ 且 $p_j > p_i$ 的最小下标（即最靠左的满足条件的方格）；若不存在这样的 $j$，则可直接结束本轮，并支付代价 $b_i$。

游戏共进行 $q$ 轮。为增加难度，你需要维护一个方格集合 $S$（初始为空集）。在每轮中，你必须经过集合 $S$ 中的所有方格（也可经过其他方格）。第 $i$ 轮的方格集合 $S$ 是通过对第 $i-1$ 轮的集合 $S$ 添加或删除一个方格得到的。

对每一轮，请计算结束该轮所需的最小总代价。

The first line contains two integers $n$, $q$ ($1\le n,q\le 2 \cdot 10^5$) — the number of squares and the number of rounds.

The second line contains $n$ distinct integers $p_1,p_2,\dots,p_n$ ($1\le p_i\le n$). It is guaranteed that the sequence $p_1,p_2,\dots,p_n$ forms a permutation.

The third line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($-10^9\le a_i\le 10^9$).

The fourth line contains $n$ integers $b_1,b_2,\dots,b_n$ ($-10^9\le b_i\le 10^9$).

Then $q$ lines follow, $i$-th of them contains a single integer $x_i$ ($1\le x_i\le n$). If $x_i$ was in the set $S$ on the $(i-1)$-th round you should remove it, otherwise, you should add it.

第一行包含两个整数 $n$、$q$（$1\le n,q\le 2 \cdot 10^5$）—— 分别表示方格的数量和轮数。

第二行包含 $n$ 个互不相同的整数 $p_1,p_2,\dots,p_n$（$1\le p_i\le n$）。保证序列 $p_1,p_2,\dots,p_n$ 构成一个排列。

第三行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$-10^9\le a_i\le 10^9$）。

第四行包含 $n$ 个整数 $b_1,b_2,\dots,b_n$（$-10^9\le b_i\le 10^9$）。

接下来是 $q$ 行，其中第 $i$ 行包含一个整数 $x_i$（$1\le x_i\le n$）。若 $x_i$ 在第 $(i-1)$ 轮时属于集合 $S$，则应将其移除；否则，应将其加入。

Print $q$ lines, each of them should contain a single integer — the minimum cost you should pay to end the corresponding round.

输出 $q$ 行，每行应包含一个整数——即完成对应轮次所需的最小花费。

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.

In the first round of the first test, the set that you must pass through is ${1}$. The path you can use is $1\to 3\to 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\to 2\to 3\to T$ and its cost is $8$.

我们将字符 $T$ 视为一轮的终点。那么，我们可以为第一个和第二个测试分别绘制两张图。

在第一个测试的第一轮中，你必须经过的点集为 $\{1\}$。你可以采用的路径是 $1\to 3\to T$，其代价为 $6$。

在第一个测试的第二轮中，你必须经过的点集为 $\{1,2\}$。你可以采用的路径是 $1\to 2\to 3\to T$，其代价为 $8$。