Given a non-negative integer a=0, perform a series of q queries of the following types:
- 1x: Set a to a XOR x.
- 2: Turn off the most significant set bit of a. If a is already 0, ignore this query.
- 3: Count the number of set bits in a.
The most significant set bit is the highest-order bit that is set to 1. For example, for the number 36 in binary (100100)2, the most significant set bit is the fifth bit. After turning off this bit, the value becomes (100)2, which is 4 in decimal representation.
### Input
- The first line contains an integer q.
- The next q lines each contain a query in the specified format.
### Output
- Print the answer as an integer for each query of type 3.
### Constraints
- 1≤q≤3×105.
- 0≤x<230.
### Example
Input:
5215323
Output:
21
**Bonus: Find a way to handle each query with a time complexity of O(1).**