D - ナナメクエリ Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

縦に 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