DMOPC '19 Contest 4 P6 - little_prince's Specialty Tea House

View as PDF

Points: 25 (partial)
Time limit: 2.5s
Memory limit: 256M

Author:
Problem type

little_prince is opening a specialty tea house! One of his famous dishes is taiyaki, which is typically cooked in small fish-shaped molds. little_prince has such molds lined up in a row. He knows that the batter inside the -th taiyaki still needs to cook for more seconds to be done. As running a specialty tea house is a lot of work, he wants you to help him answer queries, each of which is one of the following types:

• 1 x which means to print the amount of time the -th taiyaki still needs to be cooked.

• 2 x y t which means that little_prince considers cooking the pans for seconds. If it would cause one of the taiyaki to overcook (overcooking means that , where ), he ignores this instruction. Otherwise, he cooks each taiyaki in the range for seconds.

• 3 x y t which means that little_prince deems that the taiyaki in pans are not up to standard. He pours new batter into the pans starting from left to right at a rate of one pan per second while the pans are heating. This means that the cook times of the pans becomes for as the earlier pans get cooked a little when little_prince is pouring in the batter for the later pans. It is guaranteed that .

• 4 x y which means that little_prince reduces the cook times of each taiyaki in pans to the floor of the square root of its original cook time. That is for .

Constraints

There are no type 3 or type 4 operations.

There are no type 3 operations.

Input Specification

The first line contains two integers, and .
The second line contains integers, , the initial cook times.
The next lines each contain a query, in the format as described above.

Output Specification

Output one integer on a separate line for each type 1 query.

Sample Input

5 8
1 3 1 7 6
2 3 5 3
4 1 3
1 3
3 2 4 4
1 3
4 1 5
2 1 4 1
1 3

Sample Output

1
3
0

Explanation for Sample Output

The first operation cannot be completed as it would cause the third taiyaki to overcook. Therefore, the array is 1 3 1 7 6.
After the second operation, the array is 1 1 1 7 6.
After the fourth operation, the array is 1 2 3 4 6.
After the sixth operation, the array is 1 1 1 2 2.
After the seventh operation, the array is 0 0 0 1 2.