Background

The Double Ninth Festival is coming, and our best Yae Sakura has the best “yingying blade” in the whole village.

Problem Description

Under the influence of Higokumaru’s power, Yae Village becomes a Yae Street of length $n$, and Higokumaru can bring Yae Sakura to appear at any position on the street. Yae Sakura can move freely on the street to obtain the “yingyingying” energy at some position, in order to upgrade her “yingying blade”.

Problem setter: March_H

At each moment, the following $3$ types of events may happen:

$1$ $x$ $val$ means that a Higokumaru carrying $val$ points of “yingyingying” energy appears at position $x$, and it will devour the “yingyingying” energy at that position, making the energy at that position become $val - a_i$, where $a_i$ is the amount of “yingyingying” energy at that position at the moment right before Higokumaru appears.

$2$ $l$ $r$ means that Higokumaru will bring Yae Sakura to appear at any position within $[l, r]$. In order to upgrade her “yingying blade” as fast as possible, Yae Sakura will obtain the maximum “yingyingying” energy in this interval. Specially, in order to protect Yae Village, when there exists a Higokumaru between $l$ and $r$, Yae Sakura will prioritize using her “yingying blade” to deal with Higokumaru, and obtain $a_i$ points of “yingyingying” energy that the position where Higokumaru is located currently has.

$3$ $l$ $r$ $val$ means that Higokumaru will “yingyingying”, causing the “yingyingying” energy at every position in $[l, r]$ to increase by $val$ points (including the position where Higokumaru is located).

Input Format

The first line contains $2$ integers $n$ and $m$.

The second line contains $n$ integers, representing the initial “yingyingying” energy at each position on Yae Street.

The next $m$ lines each describe one of the $3$ events, with the input format as specified in the description.

Output Format

For each event of type $2$, output the amount of “yingyingying” energy obtained by Yae Sakura in that event, followed by a newline.

After all events end, if the energy accumulated in the “yingying blade” is less than $10000$, output $QAQ$.

If it is in $[10000, 10000000)$, output $Sakura$.

If neither condition is satisfied, output $ice$.

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

10
9
8
7
6
5
4
3
2
1
QAQ

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

10
QAQ

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

10000
8000
9000
Sakura

Hint

For all testdata:

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

$n$ and $m$ $\leqslant$ $100000$.

Note that whether Yae Sakura obtains the “yingyingying” energy at a position or defeats the Higokumaru at a position, the “yingyingying” value at that position should be cleared to $0$ instead of keeping the original value.

For event $2$, the problem guarantees that at most $1$ Higokumaru appears in each event. If there are multiple maximum values, when comparing each time, choose the rightmost one (the default behavior of std).

Translated by ChatGPT 5