Jack is scrambling to finish his data homework! He needs to survey his ~N~ classmates on how much they like chocomint for his summative assignment, and then put that data through his specialized model he dubs, Matroicutree. Matroicutree works by modelling Jack's classmates as an array ~a~, where each classmate ~i~ has an opinion of ~a[i]~. Jack updates the model by looking at certain ranges ~a[l \dots r]~ of his classmates to see how many of them have exactly an opinion of ~c~ (this ~c~ is generated automatically by Matroicutree).

However, Jack's classmates are very fickle and often like to change their minds. In each opinion change, classmate ~i~ can have their opinion (~a[i]~) increase by ~1~ or decrease by ~1~. Jack needs to incorporate these new changes into his final model. Help Jack finish his data homework on time!

Input Specification

Each classmate initially has an opinion of ~0~.

The first line consists of two integers, ~N~ and ~Q~. ~N~ denotes the number of classmates and ~Q~ the number of queries Jack needs to ask you in order to get his algorithm to successfully work.

Each query is one of the following:

• 1 x Increment classmate ~x~'s opinion of chocomint by ~1~.
• 2 x Decrement classmate ~x~'s opinion of chocomint by ~1~.
• 3 l r c Output how many classmates from the ~l~-th index to the ~r~-th index have exactly an opinion ~c~ of chocomint.

Output Specification

For each type ~3~ query that Jack asks you, output the answer on its own line.

Constraints

For all subtasks:

~1 \le N, Q \le 500\,000~

~1 \le l \le r \le N~

~1 \le x \le N~

~-500\,000 \le c \le 500\,000~

Subtask 1 [10%]

~1 \le N, Q \le 5\,000~

Subtask 2 [90%]

No additional constraints.

Sample Input

10 10
1 5
3 4 5 0
1 10
3 9 10 -1
2 8
3 8 10 -1
3 1 10 0
3 6 10 -2
1 5
3 4 9 2

Sample Output

1
0
1
7
0
1

Explanation of Sample Output

Initially, all opinions of chocomint are ~0~. After query 1, classmate ~5~'s opinion of chocomint increases by ~1~. For query 2, classmate ~4~ still has an opinion of ~0~, but classmate ~5~ now has an opinion of ~1~, so there is exactly ~1~ person in the range ~[4,5]~ who has an opinion of ~0~.