问题文
有一个 N 行 N 列的方格纸。
我们将方格纸左上角的格子称为 (0,0),下移 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,−105≤C≤105。
2 A B C
:将满足 A≤X−Y≤B 的格子 (X,Y) 上的数字加上 C。保证 1−N≤A≤B≤N−1,−105≤C≤105。
3 A B C D
:找出满足 A≤X≤B 且 C≤Y≤D 的所有格子中最大的数字 M,并统计在这个范围内数字等于 M 的格子的数量。保证 0≤A≤B≤N−1,0≤C≤D≤N−1。
请编写程序按顺序处理这些查询操作。
输入
输入从标准输入中读取,具体格式如下:
N Q
Query1
Query2
:
QueryQ
- 第 1 行包含两个用空格分隔的整数,表示方格纸的大小 N(1≤N≤5,000) 和查询操作的数量 Q(1≤Q≤5,000)。
- 接下来的 Q 行中,第 i 行表示第 i 个查询操作。查询的格式如问题文中所述。
- 保证至少有 1 个第 3 种查询。
部分分
本问题设置了部分分。
- 如果能正确处理满足 1≤N≤50 的数据集,将得到 10 分。
- 如果能正确处理满足 1≤N≤500 的数据集,将额外得到 20 分。总共可以得到 30 分。
- 如果能正确处理满足 1≤N≤5,000 的数据集,将额外得到 70 分。总共可以得到 100 分。
输出
输出行数与第 3 种查询的数量相等。第 i 行输出第 i 个第 3 种查询的答案。设范围内最大值为 M,范围内等于 M 的格子数量为 C,则按顺序输出 M 和 C,以空格分隔。最后换行。
输入示例1
输出示例1
处理完第 1 个查询后的方格纸如下所示:

第 2 个查询的范围如下所示:

因此最大值为 2,数量为 4。
处理完第 3 个查询后的方格纸如下所示:

第 4 个查询的范围如下所示:

因此最大值为 5,数量为 7。
输入示例2
输出示例2