Time Limit: 2 s
Memory Limit: 256 MB

Submission：227
AC：40
Score：97.49

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.

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.

For each query, output the answer in one line.

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