Problem Background

The Double Ninth Festival is here, and our best Yachiyo has the village's best YingYing sword...

Problem Description

Under the influence of Hiyori's power, Yachiyo Village has turned into a street of length $n$, and Hiyori can appear with Yachiyo at any location on the street. Yachiyo will roam the street at random to gather YingYing energy at certain locations to upgrade her YingYing sword.

Author: March_H

At each moment, one of the following three events occurs:

$1$ $x$ $val$ indicates that a Hiyori doll carrying $val$ points of YingYing energy appears at location $x$, and the Hiyori doll will devour the YingYing energy at that location, reducing it to $val - a_i$ points, where $a_i$ is the YingYing energy present at that location before the Hiyori doll appeared.

$2$ $l$ $r$ means that Hiyori will appear with Yachiyo at any point in the interval [$l$, $r$]. To upgrade her YingYing sword as quickly as possible, Yachiyo will gather the maximum YingYing energy in this interval. Specifically, to protect the village, if there is a Hiyori doll within the interval $l$, $r$, Yachiyo will prioritize using her YingYing sword against the Hiyori doll and gain the $a_i$ points of YingYing energy it possesses.

$3$ $l$ $r$ $val$ Hiyori will chant, causing the YingYing energy at every location in the interval [$l$, $r$] to increase by $val$ points (including the Hiyori doll).

Input Format

The first line contains two numbers $n$ and $m$.

The second line contains $n$ numbers, representing the initial YingYing energy at each location on the street.

The next $m$ lines each describe one of the three events, formatted as described in the problem statement.

Output Format

For each event $2$, you should output the YingYing energy Yachiyo gains in that event and then newline.

When all events are finished, if the accumulated energy of the YingYing sword is less than $10000$, you should output $QAQ$.

If it is between $[10000, 10000000)$, you should output $Sakura$.

If neither condition is met, output $ice$.

Sample Input and Output

Input Sample #1

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

Output Sample #1

10
9
8
7
6
5
4
3
2
1
QAQ

Input Sample #2

10 11
0 0 0 0 0 0 0 0 0 0
3 1 10 1
3 2 10 1
3 3 10 1
3 4 10 1
3 5 10 1
3 6 10 1
3 7 10 1
3 8 10 1
3 9 10 1
3 10 10 1
2 1 10

Output Sample #2

10
QAQ

Input Sample #3

10 13
0 0 0 0 0 0 0 0 0 0
1 10 10000
1 9 9000
1 8 8000
1 7 7000
1 6 6000
1 5 5000
1 4 4000
1 3 3000
1 2 2000
1 1 1000
2 10 10
2 8 8
2 8 10

Output Sample #3

10000
8000
9000
Sakura

Notes

For all data:

The final answer will be within the range $[0, 2^{31}-1]$.

$n$, $m$ $\leqslant$ $100000$.

It is worth noting that whether Yachiyo gains the YingYing energy from a location or defeats a Hiyori doll at a location, the YingYing value at that location should be cleared to zero rather than retaining its original value.

For event $2$, the problem guarantees that at most one Hiyori doll appears in each event. If there are multiple maximum values, choose the one on the right (default behavior of the standard solution).

见题面 Input 部分

见题面 Output 部分