i mistook math software for a gacha game ~ Victor, 2020

Victor, just like everyone else, has trouble telling the difference between math software and gacha games. As his good friend, you decide to help him overcome this deficiency.

You email him ~N~ programs for him to identify. Obviously, he initially assumes they are all gacha games, and declares he will need ~a_i~ minutes to test if the ~i~th game is a gacha game. Sometimes, ~a_i~ will be negative. You aren't sure what this means, but unwilling to assume this is a typo, you dutifully note it down.

Victor then sends you ~Q~ messages:

• 1 l r: Victor declares that the ~l, l+1, \dots, r-1, r~th programs are all gacha games.
• 2 l r: Victor declares that the ~l, l+1, \dots, r-1, r~th programs are all math software.
• 3 l r x: Victor re-evaluates the time he needs to test the ~l, l+1, \dots, r-1, r~th program: he sets ~a_l = a_{l+1} = \dots = a_{r-1} = a_r = x~.
• 4 l r: Victor will test the ~l, l+1, \dots, r-1, r~th programs, in that order. If he believes the ~i~th game to be a gacha, he will test it for ~a_i~ minutes. Otherwise, he will take a break.
• 5 l r: Victor will test the ~l, l+1, \dots, r-1, r~th programs, in that order. If he believes the ~i~th game to be math software, he will test it for ~a_i~ minutes. Otherwise, he will take a break.

Concerned for Victor's wellbeing, every time he declares he will test some programs, you reply with the longest stretch of time he will spend testing programs without a break.

Note: for type 4 and 5 queries, output breaks galore if none of the programs in the range are gacha or math, respectively. Otherwise, output the longest non-empty stretch of time.

Constraints

For all subtasks:

~-10^5 \le a_i \le 10^5~

Subtask 1 [5%]

~1 \le N, Q \le 2\,000~

Subtask 2 [20%]

~1 \le N, Q \le 300\,000~

Victor will never change the amount of time required to test a program (i.e., no messages of type 3).

Subtask 3 [20%]

~1 \le N, Q \le 300\,000~

Victor will change the amount of time required to test exactly ~1~ program in each query (i.e., ~a=b~ for type 3 messages).

Subtask 4 [55%]

~1 \le N, Q \le 300\,000~

Input Specification

The first line of input will contain two space-separated integers: ~N~ and ~Q~.
The second line of input will contain ~N~ space-separated integers: ~a_1, \dots, a_N~.
The next ~Q~ lines will each contain one of Victor's messages.

Output Specification

For each message of the form 4 l r and 5 l r, output the longest stretch of time he will spend testing programs without a break.

Sample Input 1

5 8
5 2 -1 0 5
4 4 4
4 4 5
5 4 4
5 4 5
4 3 3
2 1 3
4 3 3
5 3 3

Sample Output 1

0
5
breaks galore
breaks galore
-1
breaks galore
-1

Sample Input 2

20 13
1 2 5 7 2 8 1 7 -2 3 3 -2 -1 -4 8 -9 10 -5 -2 0
4 8 11
2 9 10
4 8 11
4 17 19
3 12 15 9
5 2 8
1 13 13
2 17 20
4 3 18
5 20 20
4 17 18
3 16 19 -8
5 13 17

Sample Output 2

11
7
10
breaks galore
39
0
breaks galore
-8