Plasmatic loves playing with playdoughs in his spare time. Currently, he has a collection of playdoughs, and the
playdough weighs
grams for each
from
to
. 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
operations that he wants you to do with his collection of playdoughs, and each operation can be one of the two:
1 x
: Find all playdoughs that weighs exactlygrams then split the playdough into
and
.
2 y
: Find the number of playdoughs that weigh exactlygrams.
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%]
Subtask 2 [85%]
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 and
separated by a space.
The next line contains integers
, the weight of each of his playdough originally.
The following 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
Comments