K. Kuga-Buga
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Enzo, a caveman, recently developed an interest in collecting stones as a hobby. He has a collection called $$$A$$$ with $$$N$$$ stones lined up in various colors and identified each color with an integer (for example, he defined color number $$$1$$$ as the color green).

The special aspect of his collection is that, for a given number $$$x$$$, he is very particular about what he calls the "kuga-buga-$$$x$$$ value"; this value is the number of colors that appear with a frequency that is a multiple of $$$x$$$. For example, if he has $$$3$$$ yellow stones and $$$6$$$ blue stones, the kuga-buga-$$$3$$$ value is $$$2$$$, since he has two colors that appear a number of times that is a multiple of $$$3$$$.

Since he always wants to maintain the same number of stones but wants to keep the collection up to date, he frequently replaces stones he no longer likes with a new one of another color. He calls this update a type $$$1$$$ query.

From time to time, he wonders about the kuga-buga value for a given number $$$x$$$. He calls this question a type $$$2$$$ query.

With that, Enzo wants your help to answer these kuga-buga queries given the stone collection $$$A$$$ and the updates that occur over time.

Input

The first line of the input contains two integers $$$N$$$ $$$(1 \leq N \leq 3 \cdot 10^5)$$$ and $$$Q$$$ $$$(1 \leq Q \leq 10^5)$$$, the size of Enzo's collection and the number of queries, respectively.

The second line contains $$$N$$$ integers $$$A_i$$$ $$$(1 \leq A_i \leq 10^6)$$$; the $$$i$$$-th of these is the color of the stone at the $$$i$$$-th position of $$$A$$$.

The next $$$Q$$$ lines each contain a query.

A query can have one of two forms: "$$$1$$$ $$$i$$$ $$$y$$$" $$$(1 \leq i \leq N,\ 1 \leq y \leq 10^6)$$$ (replace the $$$i$$$-th stone with one of color $$$y$$$) or "$$$2$$$ $$$x$$$" $$$(1 \leq x \leq 10^6)$$$ (what is the kuga-buga-$$$x$$$ value?).

Output

For each query of type $$$2$$$, print the kuga-buga-$$$x$$$ value for the given value of $$$x$$$.

Examples
Input
6 4
1 1 1 2 2 3
2 1
2 2
1 6 2
2 3
Output
3
1
2
Input
4 4
1 1 1 1
2 1
2 2
1 3 2
2 1
Output
1
1
2