Problem Statement

縦に $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$ を満たすことが保証される。

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

Input

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

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$点となる。

Output

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