Sequence and Queries 38

Interview

Time limit2sMemory limit256 MB

Summary
Maintain a sequence under append, delete-one-copy, and report running sum and XOR of all elements.
Level

Medium4 of 10

Topics
Hash map, Implementation, Math, Simulation
Solved
No attempts yet

Problem

There is an array A that initially contains a single 0. You must process the following queries on it.

  • 1 x: append x to the back of A.
  • 2 x: remove x from A. If A contains two or more copies of x, remove only the frontmost one. This query is only given when A contains x.
  • 3: print the sum of all elements in A.
  • 4: print the XOR of all elements in A.

Input

The first line gives the number of queries M. Each of the next M lines gives one query.

Output

For every query of type 3 or type 4, print the answer on its own line.

Constraints

  • 1 ≤ M ≤ 500 000
  • 1 ≤ x ≤ 1 000 000 000
  • At least one query of type 3 or type 4 is given.

Examples1

  1. Example 1

    Input
    12
1 3
1 1
1 4
3
4
1 1
3
4
2 1
2 4
3
4
    Expected output
    8
6
9
7
4
2