Angie is maintaining some coins!

She begins with an array of ~N~ coins, and then assigns each coin with a number ~a_i~. Next, she will perform ~Q~ operations of one of the following types on the coins.

• I i x: Insert a coin with value ~x~ directly after coin ~i~. If ~i=0~ then the coin is inserted at the beginning
• D j: Delete coin ~j~
• C l r x: Output how many coins between coin ~l~ and ~r~ (inclusive) have a value of ~x~

Because the amount of coins can grow very large, she has decided to enlist your help to keep track of the coins. Can you help her do it?

Important Note: The test cases are Online Enforced. That means all numbers in the input will be encrypted with the formula ~v \oplus lastAns~, where ~v~ is the original number in the query, ~\oplus~ is the Bitwise XOR operation, and ~lastAns~ is the answer to the last C operation given (or ~0~ if none have been answered yet).

Constraints

For all subtasks:

~1 \le a_i, x \le 10^6~

~0 \le i \le |a|~

~1 \le j \le |a|~

~1 \le l \le r \le |a|~

~|a|~ is the length of the coin array at the time of the query.

Subtask 1 [5%]

~1 \le N, Q \le 100~

Subtask 2 [20%]

All elements in the initial array and all inserted elements are distinct.

~1 \le N, Q \le 3 \times 10^5~

Subtask 3 [75%]

~1 \le N, Q \le 3 \times 10^5~

Input Specification

The first line of input will contain the space separated integers ~N~ and ~Q~.

The second line will contain ~N~ space separated integers: ~a_1, a_2, \dots, a_N~.

The final ~Q~ lines will contain operations in the format described above.

Output Specification

Output the answer for each C query on its own line.

Sample Input

10 10
5 1 6 1 5 1 2 2 7 8
C 2 5 1
D 0
C 0 6 3
I 1 4
I 11 11
C 0 2 4
C 8 9 8
I 2 7
C 0 7 7
C 3 14 0

Sample Input (Not Encrypted)

For your convenience, here is a version of the sample input that is NOT encrypted. Remember, all of the real test files will be encrypted (like the input above).

10 10
5 1 6 1 5 1 2 2 7 8
C 2 5 1
D 2
C 2 4 1
I 0 5
I 10 10
C 1 3 5
C 10 11 10
I 3 6
C 1 6 6
C 1 12 2

Sample Output

2
1
2
1
2
2

Sample Explanation

This is what the array begins as: 5 1 6 1 5 1 2 2 7 8

The first query asks for this range: 5 [1 6 1 5] 1 2 2 7 8

The second query changes the array to this: 5 6 1 5 1 2 2 7 8

The third query asks for this range: 5 [6 1 5] 1 2 2 7 8

The fourth query changes the array to this: 5 5 6 1 5 1 2 2 7 8

The fifth query changes the array to this: 5 5 6 1 5 1 2 2 7 8 10

The sixth query asks for this range: [5 5 6] 1 5 1 2 2 7 8 10

The seventh query asks for this range: 5 5 6 1 5 1 2 2 7 [8 10]

The eighth query changes the array to this: 5 5 6 6 1 5 1 2 2 7 8 10

The ninth query asks for this range: [5 5 6 6 1 5] 1 2 2 7 8 10

The tenth and final query asks for the entire array.