O-matriangle
A square matrix N by N is filled with zeros. The top left field of matrix has a coordinate of (1,1) and the bottom right has a coordinate of (N,N).
You are given a list of commands that can either increase, decrease or multiply a field by some integer amount.
Image: matrix
Periodically you are also asked which triangle part of the matrix (see the figure) has the highest sum of its elements.
InputThe first row contains two numbers N (the matrix dimension) and P (the number of commands). 1 <= N <= 100, 1<= P <= 250000.
Each of the next P rows contain a single command: PUT, ADD, SUB or MUL followed by three numbers separated with single space: R, [
Each of the next P rows contain a single command: PUT, ADD, SUB or MUL followed by three numbers separated with single space: R, [
] and V representing ROW, COLUMN and the VALUE for the command. Another possible command is QUERRY (with no arguments). The limits are: 1 <= R, C <= N, 0 <= V <= 10000, and no value will exceed 2^32. There will be at least one QUERRY command in the input.OutputFor every QUERRY command, in a separate row output the number of the triangle part of matrix with the greatest sum of its values. If there are two or more parts with same sums, write all of them in an increasing order, without empty spaces between.
Input:
[c]
5 11
SUB 2 5 2
QUERRY
ADD 1 2 1
MUL 5 3 3
ADD 3 1 4
QUERRY
ADD 1 2 7
SUB 3 4 8
ADD 3 5 25
PUT 3 1 1
QUERRY
[c]
5 11
SUB 2 5 2
QUERRY
ADD 1 2 1
MUL 5 3 3
ADD 3 1 4
QUERRY
ADD 1 2 7
SUB 3 4 8
ADD 3 5 25
PUT 3 1 1
QUERRY
Output:
34
4
1
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.