You are given an initially empty **multiset** S, and you need to perform four types of queries on it:
- (1,x): Insert the integer x into S.
- (2,x): Remove one occurrence of x from S. It is guaranteed that x appears in S.
- (3,x): For each element p in S, perform the bitwise XOR operation with x (.i.e p to p⊕x).
- (4,k): Find the k-th smallest element of S when it is sorted in non-decreasing order. It is guaranteed that k≤|S|, where |S| denotes the size of the multiset.
Your task is to implement a solution that can efficiently perform these operations and find the answer for each query of type 4.
### Input
- The first line contains an integer q.
- The next q lines, each line contains 2 integers, a query.
### Output
- Print the answer for each query of type 4.
### Constraints
- 1≤q≤105.
- 1≤x≤105.
- 1≤k.
### Example
Input:
51121141542
Output:
5
