Problem Description

We have a grid paper with $ N $ rows and $ N $ columns.

We define the cell located $ X $ cells down and $ Y $ cells to the right from the top-left cell as cell $ (X, Y) $. Thus, the top-left cell is cell $ (0, 0) $ and the bottom-right cell is cell $ (N-1, N-1) $.

Initially, all cells contain the integer $ 0 $.

We will perform $ Q $ query operations on this grid paper. There are three types of query operations as follows:

• 1 A B C: Add $ C $ to all integers written in cells $ (X, Y) $ where $A \leq X + Y \leq B$. It is guaranteed that $0 \leq A \leq B \leq 2N-2$ and $-10^5 \leq C \leq 10^5$.
• 2 A B C: Add $ C $ to all integers written in cells $ (X, Y) $ where $A \leq X - Y \leq B$. It is guaranteed that $1-N \leq A \leq B \leq N-1$ and $-10^5 \leq C \leq 10^5$.
• 3 A B C D: Find the maximum value $ M $ and the number of cells containing $ M $ within the range where $A \leq X \leq B$ and $C \leq Y \leq D$. It is guaranteed that $0 \leq A \leq B \leq N-1$ and $0 \leq C \leq D \leq N-1$.

Write a program to process these queries sequentially.

Input Format

The input is given from the standard input in the following format:

$ N $ $ Q $ $ Query_1 $ $ Query_2 $ : $ Query_Q $

• The first line contains the size of the grid paper $N (1 \leq N \leq 5,000)$ and the number of queries $Q (1 \leq Q \leq 5,000)$ separated by a space.
• The next $ Q $ lines contain the $ i $th query on the $ i $th line. The format of the queries is as described in the problem statement.
• At least one query of the third type is given.

Output Format

The number of lines in the output is equal to the number of third-type queries. On the $ i $th line, output the answer to the $ i $th third-type query. If the maximum value within the range is $ M $ and the count of cells containing $ M $ is $ C $, output $ M, C $ separated by a space. End each line with a newline.

Sample Input and Output

Sample Input #1

4 4
1 1 4 2
3 0 1 2 3
2 -2 1 3
3 0 3 1 3

Sample Output #1

2 4
5 7

Sample Input #2

50 20
2 5 40 6
1 69 94 5
3 8 39 31 32
2 -29 -21 -10
2 20 43 3
2 -37 36 -10
2 -18 45 5
2 30 39 -2
3 0 1 19 33
3 27 47 0 43
3 0 1 28 39
1 90 97 0
2 -46 31 7
1 81 81 4
1 11 54 3
3 10 29 26 30
1 39 45 3
1 70 97 -4
3 24 46 14 34
3 1 18 48 48

Sample Output #2

11 5
-5 1
14 8
0 3
5 82
16 2
10 5

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the dataset where $1 \leq N \leq 50$, you get $ 10 $ points.
• If you solve the dataset where $1 \leq N \leq 500$, you get an additional $ 20 $ points, totaling $ 30 $ points.
• If you solve the dataset where $1 \leq N \leq 5,000$, you get an additional $ 70 $ points, totaling $ 100 $ points.

Sample Explanation 1

After processing the first query, the grid paper looks like this. The range for the second query is as follows. Thus, the maximum value is $ 2 $ and there are $ 4 $ cells with this value. After processing the third query, the grid paper looks like this. The range for the fourth query is as follows. Thus, the maximum value is $ 5 $ and there are $ 7 $ cells with this value.

见题面 Input 部分

见题面 Output 部分