#arc047d. [arc047_d]ナナメクエリ

[arc047_d]ナナメクエリ

问题文

有一个 NNNN 列的方格纸。

我们将方格纸左上角的格子称为 (0,0)(0, 0),下移 XX 格,右移 YY 格后的格子称为 (X,Y)(X, Y)。即左上角的格子是 (0,0)(0, 0),右下角的格子是 (N1,N1)(N-1, N-1)

一开始,每个格子上都写着数字 00

现在我们要进行 QQ 次查询操作。查询操作有 33 种,如下所示:

  • 1 A B C:将满足 AX+YBA \leq X+Y \leq B 的格子 (X,Y)(X, Y) 上的数字加上 CC。保证 0AB2N20 \leq A \leq B \leq 2N-2105C105-10^5 \leq C \leq 10^5
  • 2 A B C:将满足 AXYBA \leq X-Y \leq B 的格子 (X,Y)(X, Y) 上的数字加上 CC。保证 1NABN11-N \leq A \leq B \leq N-1105C105-10^5 \leq C \leq 10^5
  • 3 A B C D:找出满足 AXBA \leq X \leq BCYDC \leq Y \leq D 的所有格子中最大的数字 MM,并统计在这个范围内数字等于 MM 的格子的数量。保证 0ABN10 \leq A \leq B \leq N-10CDN10 \leq C \leq D \leq N-1

请编写程序按顺序处理这些查询操作。


输入

输入从标准输入中读取,具体格式如下:

NN QQ Query1Query_1 Query2Query_2 : QueryQQuery_Q

  • 11 行包含两个用空格分隔的整数,表示方格纸的大小 N(1N5,000)N(1 \leq N \leq 5,000) 和查询操作的数量 Q(1Q5,000)Q(1 \leq Q \leq 5,000)
  • 接下来的 QQ 行中,第 ii 行表示第 ii 个查询操作。查询的格式如问题文中所述。
  • 保证至少有 11 个第 33 种查询。

部分分

本问题设置了部分分。

  • 如果能正确处理满足 1N501 \leq N \leq 50 的数据集,将得到 1010 分。
  • 如果能正确处理满足 1N5001 \leq N \leq 500 的数据集,将额外得到 2020 分。总共可以得到 3030 分。
  • 如果能正确处理满足 1N5,0001 \leq N \leq 5,000 的数据集,将额外得到 7070 分。总共可以得到 100100 分。

输出

输出行数与第 33 种查询的数量相等。第 ii 行输出第 ii 个第 33 种查询的答案。设范围内最大值为 MM,范围内等于 MM 的格子数量为 CC,则按顺序输出 MMCC,以空格分隔。最后换行。


输入示例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

处理完第 11 个查询后的方格纸如下所示:

22 个查询的范围如下所示:

因此最大值为 22,数量为 44

处理完第 33 个查询后的方格纸如下所示:

44 个查询的范围如下所示:

因此最大值为 55,数量为 77


输入示例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