問題文

縦に $N$ 行、横に $N$ 列の方眼紙があります。

この方眼紙上の最も左上のマスから下に $X$ マス、右に $Y$ マス進んだところにあるマスをマス $(X, Y)$ と呼ぶことにします。 つまり、最も左上のマスはマス $(0, 0)$ 、右下のマスはマス $(N-1, N-1)$ になります。

初め、全てのマスには整数 $0$ が書き込まれています。

この方眼紙に $Q$ 回のクエリ操作を行うことを考えます。 クエリ操作は $3$ 種類あり以下のとおりです。

• 1 A B C : $A ≦ X+Y ≦ B$ となる全てのマス $(X, Y)$ にかかれている整数に $C$ を加える。$0 ≦ A ≦ B ≦ 2N-2, -10^5 ≦ C ≦ 10^5$ を満たすことが保証される。
• 2 A B C : $A ≦ X-Y ≦ B$ となる全てのマス $(X, Y)$ にかかれている整数に $C$ を加える。$1-N ≦ A ≦ B ≦ N-1, -10^5 ≦ C ≦ 10^5$ を満たすことが保証される。
• 3 A B C D : $A ≦ X ≦ B$ かつ $C ≦ Y ≦ D$ となる全てのマス $(X,Y)$ の中の最大値 $M$ と、その範囲の中に $M$ が書かれたマスがいくつあるか求める。$0 ≦ A ≦ B ≦ N-1, 0 ≦ C ≦ D ≦ N-1$ を満たすことが保証される。

このようなクエリを順番に処理するプログラムを書いてください。

---

入力

入力は以下の形式で標準入力から与えられる。

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

• $1$ 行目には方眼紙の大きさを表す整数 $N(1 ≦ N ≦ 5,000)$ とクエリの個数を表す整数 $Q(1 ≦ Q ≦ 5,000)$が空白区切りで与えられる。
• $2$ 行目からの $Q$ 行の内 $i$ 行目には $i$ 番目のクエリが与えられる。クエリの形式は問題文中で与えたとおりである。
• $3$ 種類目のクエリは $1$ 個以上与えられる。

部分点

この問題には部分点が設定されている。

• $1 ≦ N ≦ 50$を満たすデータセットに正解した場合は $10$ 点が与えられる。
• $1 ≦ N ≦ 500$を満たすデータセットに正解した場合はさらに $20$ 点が与えられる。合計で$30$点となる。
• $1 ≦ N ≦ 5,000$ を満たすデータセットに正解した場合はさらに $70$ 点が与えられる。合計で$100$点となる。

出力

出力の行数は $3$ 種類目のクエリの個数と等しくなる。 $i$ 行目には $i$ 番目の $3$ 種類目のクエリの答えを出力せよ。 範囲の中の最大値を $M$、その個数を $C$ とすると $M, C$ をこの順で空白区切りで出力せよ。 出力の末尾に改行を入れること。

---

入力例1の説明にミスがあったため、正しいものに差し替えました（21:51）

入力例1

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

出力例1

2 4
5 7

$1$ 番目のクエリを処理した後の方眼紙の様子は以下の様になります。

$2$ 番目のクエリの範囲は以下の様な範囲です。

よって最大値は $2$、 個数は $4$ 個になります。

$3$ 番目のクエリを処理した後の方眼紙の様子は以下の様になります。

$4$ 番目のクエリの範囲は以下の様な範囲です。

よって最大値は $5$、 個数は $7$ 個になります。

---

入力例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

出力例2

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

---