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,...,n−1 and selects a sequence of n integers d0,...,dn−1 all in the range [0;n]. Then, Bob computes a sequence x0,...,xn in the following way: x0=0 and xi+1=(xi+yi) mod n where mod is the modulo operation and yi is the number of figurines displayed on day di that have a number higher or equal to xi. The result of Bob's computation is xn.
More formally, if we note S(i) the subset of {0,...,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 j (0≤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:
x0=0
for i∈[0;n−1]
xi+1=(xi+#{y∈S(di) such that y≥xi}) mod n
output xn
Bob asks you to verify his computation. For that he gives you the numbers he used during its computation (the d0,...,dn−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 (i≤k<j). You should tell him the number that you found at the end of the computation.
The input is composed of 2⋅n+1 lines.
The first line contains the integer n (1≤n≤105).
Lines 2 to n+1 describe the figurines added and removed. Line i+1 contains space-separated +j or −j, 0≤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 2⋅n+1 describe the sequence d0,...,dn−1. Line n+2+i contains the integer di (0≤di≤n).
The output should contain a single line with a single integer which is xn.
The output is 2 since
first, x=2 since S(1)={0,2} and #{y∈S(1) such that y>0}=2;
then, x=0 since S(2)={1,2} and #{y∈S(2) such that y>2}=1;
and finally, x=2 since S(2)={1,2} and #{y∈S(2) such that y>0}=2.