T661244 [SWERC 2020] Figurines

:::align{center}  ::: Bob has a lot of mini figurines. He likes to display some of them on a shelf above his computer screen and he likes to regularly change which figurines appear. This ever-changing decoration is really enjoyable. Bob takes care of never adding the same mini figurine more than once. Bob has only $N$ mini figurines and after $N$ days he arrives at the point where each of the $N$ figurines have been added and then removed from the shelf (which is thus empty). Bob has a very good memory. He is able to remember which mini figurines were displayed on each of the past days. So Bob wants to run a little mental exercise to test its memory and computation ability. For this purpose, Bob numbers his figurines with the numbers $0, \dots, N-1$ and selects a sequence of $N$ integers $d_0 \dots d_{N-1}$ all in the range $[0;N]$. Then, Bob computes a sequence $x_0,\dots, x_N$ in the following way: $x_0=0$ and $x_{i+1}=(x_i+y_i)\text{ mod } N$ where $\text{mod}$ is the modulo operation and $y_i$ is the number of figurines displayed on day $d_i$ that have a number higher or equal to $x_i$. The result of Bob's computation is $x_N$. More formally, if we note $S(i)$ the subset of $\{0,\dots,N-1\}$ corresponding to figurines displayed on the shelf on day $i$, we have: - $S(0)$ is the empty set; - $S(i)$ is obtained from $S(i-1)$ by inserting and removing some elements. Each element $0 \le j < N$ is inserted and removed exactly once and thus, the last set $S(N)$ is also the empty set. The computation that Bob performs corresponds to the following program: $$ \begin{array}{l} x_0 \leftarrow 0 \\ \text{for } i \in [0;N-1] \\ \;\;\;\;\;\;\; x_{i+1} \leftarrow (x_i + \#\{y \in S(d_i) ~\text{ such that } ~ y \ge x_i\}) \mod N \\ \text{output } x_N \end{array} $$ Bob asks you to verify his computation. For that he gives you the numbers he used during its computation (the $d_0, \dots, d_{N-1}$) as well as the log of which figurines he added or removed every day. Note that a mini figurine added on day $i$ and removed on day $j$ is present on a day $k$ when $i\leq k < j$. You should tell him the number that you found at the end of the computation.

The input is composed of $2N+1$ lines. - The first line contains the integer $N$. - Lines $2$ to $N+1$ describe the figurines added and removed. Line $i+1$ contains space-separated $+j$ or $-j$, with $0 \le j < N$, to indicate that $j$ is added or removed on day $i$. This line may be empty. A line may contain both $+j$ and $-j$, in that order. - Lines $N+2$ to $2N+1$ describe the sequence $d_0,\dots, d_{N-1}$. Line $N+2+i$ contains the integer $d_i$ with $0 \le d_i \le N$. **Limits** - $1 \le N \le 100\,000$

The output should contain a single line with a single integer which is $x_N$.

**Sample Explanation** The output is $2$ since - first, $x \leftarrow 2$ since $S(1) = \{ 0, 2 \}$ and $\#\{y \in S(1) ~\text{such that}~ y \ge 0\} = 2$; - then, $x \leftarrow 0$ since $S(2) = \{ 1, 2 \}$ and $\#\{y \in S(2) ~\text{such that}~ y \ge 2\} = 1$; - and finally, $x \leftarrow 2$ since $S(2) = \{ 1, 2 \}$ and $\#\{y \in S(2) ~\text{such that}~ y \ge 0\} = 2$.