Plasmatic loves playing with playdoughs in his spare time. Currently, he has a collection of $N$ playdoughs, and the $i^{\text{th}}$ playdough weighs $a_i$ grams for each $i$ from $1$ to $N$. However, he is too busy practicing for IOI. As a result, he doesn't have much time to play with the playdoughs. Instead, he gives you $Q$ operations that he wants you to do with his collection of playdoughs, and each operation can be one of the two:

1. 1 x: Find all playdoughs that weighs exactly $x$ grams then split the playdough into $\lceil \frac{x}{2}\rceil$ and $\lfloor \frac{x}{2}\rfloor$.

2. 2 y: Find the number of playdoughs that weigh exactly $y$ grams.

As a good friend of him, you want to print the answers for all of the queries in the form of 2 y. Do not disappoint him!

Constraints

Subtask 1 [15%]

$1\le N\le 100$

$1\le Q\le 500$

$1\le a_i,y\le 100$

$2\le x\le 100$

Subtask 2 [85%]

$1\le N\le {10}^5$

$1\le Q\le 5\cdot {10}^5$

$1\le a_i,y\le {10}^5$

$2\le x\le {10}^5$

Note that a 64-bit integer is needed to get full points. In C++, this can be done with long long. In Java, this can be done with long. In Python, the standard int will suffice.

Input Specification

The first line contains two integers $N$ and $Q$ separated by a space.

The next line contains $N$ integers $a_i$, the weight of each of his playdough originally.

The following $Q$ lines each contains two space-separated integers, indicating a valid query.

Output Specification

Print the answer to each query of the second type, followed by a newline.

Sample Input

5 4
1 2 3 4 5
1 5
1 4
2 2
2 3

Sample Output

4
2