Little Sub and Sequence

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


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.


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.


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


CHEN, Jingbang