Figurines#10729
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 mini figurines and after days he arrives at the point where each of the 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, ..., n - 1 and selects a sequence of integers d_0, ..., d_{n-1} all in the range . Then, Bob computes a sequence x_0, . . . , x_n in the following way: x_0 = 0 and x_{i+1} = (x_i + y_i)~mod~n where 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 the subset of \{0, ..., n - 1\} corresponding to figurines displayed on the shelf on day , we have:
is the empty set;
is obtained from S(i - 1) by inserting and removing some elements.
Each element j~(0 \le j < n) is inserted and removed exactly once and thus, the last set is also the empty set. The computation that Bob performs corresponds to the following program:
~~~~~x_0 = 0
~~~~~for~i \in [0; n - 1]
~~~~~~~~~~x_{i+1} = (x_i + \#\{y \in S(d_i)~such~that~y \ge x_i\})~mod~n
~~~~~output~x_n
Bob asks you to verify his computation. For that he gives you the numbers he used during its computation (the d_0, ..., 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 and removed on day is present on a day k~(i \le k < j). You should tell him the number that you found at the end of the computation.
The input is composed of 2 \cdot n + 1 lines.
The first line contains the integer n~(1 \le n \le 10^5).
Lines to n + 1 describe the figurines added and removed. Line i + 1 contains space-separated or , 0 \le j < n, to indicate that is added or removed on day . This line may be empty. A line may contain both and , in that order.
Lines n + 2 to 2 \cdot n + 1 describe the sequence d_0, ..., d_{n-1}. Line n + 2 + i contains the integer d_i~(0 \le d_i \le n).
The output should contain a single line with a single integer which is x_n.
The output is since
first, x = 2 since S(1) = \{0, 2\} and \#\{y \in S(1)~such~that~y \ge 0\} = 2;
then, x = 0 since S(2) = \{1, 2\} and \#\{y \in S(2)~such~that~y \ge 2\} = 1;
and finally, x = 2 since S(2) = \{1, 2\} and \#\{y \in S(2)~such~that~y \ge 0\} = 2.
Example 1