## 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
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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

##### Subtask 2 [20% of points]

There are no type 3 or type 4 operations.

##### Subtask 3 [20% of points]

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 Input

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.