Given a non-negative integer $a = 0$, perform a series of $q$ queries of the following types:
- `1 x`: Set $a$ to $a \text{ 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 \le q \le 3 \times 10^5$.
- $0 \le x < 2 ^ {30}$.
### Example
Input:
```
5
2
1 5
3
2
3
```
Output:
```
2
1
```
**Bonus: Find a way to handle each query with a time complexity of $\text{O}(1)$.**
