I. Array Tounsi
time limit per test
1 s
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$A$$$ of size $$$N$$$. You need to process $$$Q$$$ queries of two types:

  • Query: Given an integer $$$x$$$, return the number of elements in the array that are equal to $$$x$$$.

  • Update query: Given an integer $$$x$$$, for every index $$$i$$$ such that $$$A_i \gt x$$$, update the value as: $$$A_i = A_i - x$$$
Input
  • The first line contains two integers $$$N$$$ , $$$Q$$$ $$$(1 \le N \le 10^5)$$$ $$$(1 \le Q \le 10^5)$$$, the size of the array, the number of queries.
  • The second line contains $$$N$$$ integers $$$A_1, A_2, \dots, A_N$$$ $$$(1 \le A_i \le 10^6)$$$.
  • The next $$$Q$$$ lines each contain a query of one of the following types:
    • Type 1: 1 x $$$(1 \le x \le 10^6)$$$ — print the number of elements in the array equal to $$$x$$$.
    • Type 2: 2 x $$$(1 \le x \le 10^6)$$$ — for every index $$$i$$$ such that $$$A_i \gt x$$$, update the value as $$$A_i = A_i - x$$$.
Output

For each query of type 1, output a single integer representing the number of elements equal to $$$x$$$.

Example
Input
2 4
3 1
2 1
2 1
1 1
1 6
Output
2
0