Initially, there is an array $A$ containing a single 0. Then, the following queries need to be executed:

• 1 x: Append x to the end of $A$.
• 2 x: Remove x from $A$. If $A$ contains two or more x's, remove only the first occurrence. It is guaranteed that $x$ is present in $A$ at the time of the query.
• 3: Output the sum of all elements in $A$.
• 4: Output the XOR of all elements in $A$.

Input

The first line contains an integer $M$, the number of queries. The next $M$ lines each contain one query.

Output

Whenever a query of type 3 or type 4 appears, output the answer, each on its own line.

Examples

Input 1

12
1 3
1 1
1 4
3
4
1 1
3
4
2 1
2 4
3
4

Output 1

8
6
9
7
4
2