← 返回题目列表

AtCoder · code_festival_morning_hard_c

C. 寻宝 2

中文机器翻译题面 查看原题

問題文

太郎来到某广场寻找宝藏。

在这个广场上,有 n 书籍,垂直 m 线条以相等的间隔绘制。相邻线之间的距离是 1 。从上面 i 水平线从左起 第 j 条垂直线相交点的位置为(i, j),其中 k 类型 1 两件宝物 1 仅填充了一个。

太郎拥有最新的装备,所以他知道宝藏在哪里,埋藏着什么样的宝藏。于是,太郎就想找出这个广场的各个矩形区域里到底埋藏着什么样的宝藏。

然而,二郎有时会恶作剧,交换相邻宝藏的位置。这里,当我们说宝藏相邻时,是指每个宝藏埋点之间的距离完全相同。 1 。

代表因二郎的恶作剧而烦恼的太郎,对于每个给定的区域,请搜索当时该区域中最多数量的宝藏。


入力

输入按以下格式给出。

n m k
a_{1,1} a_{1,2} ... a_{1,m}
...
a_{n,1} a_{n,2} ... a_{n,m}
q
t_1 x_{11} y_{11} x_{21} y_{21}
...
t_q x_{1q} y_{1q} x_{2q} y_{2q}
  • 1 行包含一个整数,表示正方形中绘制的水平线的数量。 n (1 \leq n \leq 500),表示垂直线数的整数 m (1 \leq m \leq 500)和一个表示广场中埋藏的宝藏类型数量的整数。 k (1 \leq k \leq 100)。
  • 继续 n 行给出了广场中每个位置埋藏的宝藏类型。
  • a_{i,j} (1 \leq a_{i,j} \leq k) 位于正方形 (i, j) 代表该位置埋藏的宝藏类型。
  • n + 2 行包含一个表示查询数量的整数。 q (1 \leq q \leq 100{,}000)。
  • 继续 q 行提供每个查询的信息。
  • t_i (1 \leq t_i \leq 2) 是 表示第i 个查询类型。 当
  • t_i = 1 时, 表示第i 次查询是Jiro交换宝物的查询,并且(x_{1i}, y_{1i})和位于(x_{2i}, y_{2i})表示该位置的宝物将被兑换。 当
  • t_i = 1 时,(x_{1i}, y_{1i})和(x_{2i}, y_{2i}) 保证是相邻的。 表示第
  • t_i = 2 时, 表示第i 次查询是检查当前宝藏状态的查询,并且(x_{1i}, y_{1i})和(x_{2i}, y_{2i}) 是指调查与以对角线为顶点的正方形中所画的线平行的矩形内的宝藏情况。
  • t_i = 2 时, 表示第x_{1i} \leq x_{2i} 和 y_{1i} \leq y_{2i} 有保证。
  • 在每个查询中,1 \leq x_{1i}, x_{2i} \leq n 和 1 \leq y_{1i}, y_{2i} \leq m 有保证。

出力

每个 对于 t_i = 2 查询,找到每个查询所代表的矩形内包含的最多宝藏的类型和数量。 1 按行输出。

如果有超过一种类型的宝藏,请选择代表该宝藏类型的数字最大的一种。

在末尾使用换行符,并且不要包含不必要的字符或空行。


入力例1

3 3 3
1 1 1
2 2 2
3 3 3
5
2 1 1 2 3
1 2 2 3 2
2 1 1 2 3
1 1 3 2 3
2 2 2 3 3

出力例1

2 3
1 3
3 2

入力例2

2 4 5
1 2 3 3
2 5 1 1
4
2 1 1 1 1
1 1 3 1 2
1 2 3 1 3
2 2 1 2 4

出力例2

1 1
2 2