## DMOPC '20 Contest 1 P6 - Victor Identifies Software

View as PDF

Points: 25 (partial)
Time limit: 3.0s
Memory limit: 512M

Author:
Problem type

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 programs for him to identify. Obviously, he initially assumes they are all gacha games, and declares he will need minutes to test if the th game is a gacha game. Sometimes, 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 messages:

• 1 l r: Victor declares that the th programs are all gacha games.
• 2 l r: Victor declares that the th programs are all math software.
• 3 l r x: Victor re-evaluates the time he needs to test the th program: he sets .
• 4 l r: Victor will test the th programs, in that order. If he believes the th game to be a gacha, he will test it for minutes. Otherwise, he will take a break.
• 5 l r: Victor will test the th programs, in that order. If he believes the th game to be math software, he will test it for 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

##### Subtask 2 [20%]

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

##### Subtask 3 [20%]

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

#### Input Specification

The first line of input will contain two space-separated integers: and .
The second line of input will contain space-separated integers: .
The next 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