HZNUOJ

Little Sub and Sequence

Tags:
Time Limit:  2 s      Memory Limit:   256 MB
Submission:227     AC:40     Score:97.49

Description

Little Sub has an integer sequence A.
He will use some bitwise operations like Or, And and Xor(Exclusive Or) to change the sequence. Little Sub wants you to calculate the Kth minimum integer in A[L]..A[R] after some operations.

Input


In the first line, it contains two integers n, q(1 ≤ n, q ≤ 50000), indicating the number of sequence integers and the number of operations.

In the second line, it contains n integers A[i], indicating the initial sequence.
The following q lines represents all operations. Each type of operations follows specific formats:

Or X : Change all A[i] to A[i] Or X.
And X : Change all A[i] to A[i] And X.
Xor X : Change all A[i] to A[i] Xor X.
Ask L R K: Ask the Kth minimum integer in A[L]..A[R].(1≤K≤R−L+1)
It is guaranteed that 0 ≤ A[i], X ≤ 2^31 − 1.


Output

For each query, output the answer in one line.

Samples

input
10 4 1 2 3 4 5 6 7 8 9 0 Xor 1 And 254 Ask 1 2 2 Ask 1 8 3
output
2 2

Author

CHEN, Jingbang