Let's deal with an array again, the most important data structure of computer science. You will be given an array. Now you have some operations to do. There will be three types of operations:

• Type 1: Insert a number after a given index
• Type 2: Change the value of an index.
• Type 3: You will get a number and two indices i and j where i <= j.

Now you will have to answer how many time the number appears in the array starting from i to j.

Input

Each file contains one test case.

The first line contains and integer N, the number of initial array elements (1 <= N <= 100000) and Q, the number of Queries (1 <= Q <= 100000). Second line contains N integers each in the range from 1 to 100000. Each of the next Q lines contains an operation. The operations will appear as the formats below:

• 1 x y, where 1 <= x <= length of the array, which means you have to insert number y after the index x.
• 2 x y, For this operation, you have to change the value of index x to value y.
• 3 i j x, Here, you have to find how many times x appears in the array from i to j. Here x will always be present in the array and 1 <= i <= j <= length the array.

Output

For each operation of 3rd type, output the required answer in separated line.

Example

Input:
5 3
42 18468 6335 26501 19170
2 4 29359
2 5 5706
3 2 5 5706

Output:
1