Appleby Contest '20 P2 - Playful Playdoughs

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 512M

Author:
Problem type

Plasmatic loves playing with playdoughs in his spare time. Currently, he has a collection of NN playdoughs, and the i^\text{th}i^\text{th} playdough weighs a_ia_i grams for each ii from 11 to NN. 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 QQ 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 xx grams then split the playdough into \lceil \frac{x}{2} \rceil\lceil \frac{x}{2} \rceil and \lfloor \frac{x}{2} \rfloor\lfloor \frac{x}{2} \rfloor.

  2. 2 y: Find the number of playdoughs that weigh exactly yy 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 1001 \le N \le 100

1 \le Q \le 5001 \le Q \le 500

1 \le a_i, y \le 1001 \le a_i, y \le 100

2 \le x \le 1002 \le x \le 100

Subtask 2 [85%]

1 \le N \le 10^51 \le N \le 10^5

1 \le Q \le 5 \cdot 10^51 \le Q \le 5 \cdot 10^5

1 \le a_i, y \le 10^51 \le a_i, y \le 10^5

2 \le x \le 10^52 \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 NN and QQ separated by a space.

The next line contains NN integers a_ia_i, the weight of each of his playdough originally.

The following QQ 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

There are no comments at the moment.