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 and selects a sequence of integers all in the range . Then, Bob computes a sequence in the following way: and where mod is the modulo operation and is the number of figurines displayed on day that have a number higher or equal to . The result of Bob's computation is .
More formally, if we note the subset of corresponding to figurines displayed on the shelf on day , we have:
is the empty set;
is obtained from by inserting and removing some elements.
Each element 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:
Bob asks you to verify his computation. For that he gives you the numbers he used during its computation (the 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 . You should tell him the number that you found at the end of the computation.
The input is composed of lines.
The first line contains the integer .
Lines to describe the figurines added and removed. Line contains space-separated or , , to indicate that is added or removed on day . This line may be empty. A line may contain both and , in that order.
Lines to describe the sequence . Line contains the integer .
The output should contain a single line with a single integer which is .
The output is since
first, since and ;
then, since and ;
and finally, since and .