← 返回题目列表

Codeforces · 878/D

D. 魔法育种

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

尼基塔和萨莎玩一个电脑游戏,你必须在其中培育一些神奇的生物。最初,他们有 k 个生物,编号从 1 到 k。生物有n种不同的特征。

萨莎有一个咒语,可以从两个给定的生物中创造出一个新的生物。它的每个特性将等于所使用的生物的相应特性的最大值。尼基塔也有类似的法术,不过在他的法术中,新生物的每一个特性都等于已用生物对应特性的最小值。新生物获得最小的未使用数字。

他们使用法术并对新生物的一些特征感兴趣。帮助他们找出这些特征。

输入

第一行包含整数 n、k 和 q (1 ≤ n ≤ 105, 1 ≤ k ≤ 12, 1 ≤ q ≤ 105) — 特征、生物和查询的数量。

接下来的 k 行描述了原始生物。第 i 行包含 n 个数字 ai1, ai2, ..., ain (1 ≤ aij ≤ 109) - 第 i 个生物的特征。

接下来的 q 行中的每一行都包含一个查询。这些行的第 i 行包含数字 ti、xi 和 yi (1 ≤ ti ≤ 3)。它们表示一个查询:

- ti = 1 表示 Sasha 对生物 xi 和 yi 使用了他的咒语。
- ti = 2 意味着尼基塔对生物 xi 和 yi 使用了他的咒语。
- ti = 3 表示他们想知道第 xi 个生物的第 yi 个特征。在这种情况下,1 ≤ yi ≤ n。

保证所有生物的编号都是有效的,这意味着它们是在涉及它们的任何查询之前创建的。

输出

对于 ti = 3 的每个查询,输出相应的特征。

示例

输入 #1

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

输出 #1

2
1

输入 #2

5 3 8
1 2 3 4 5
5 1 2 3 4
4 5 1 2 3
1 1 2
1 2 3
2 4 5
3 6 1
3 6 2
3 6 3
3 6 4
3 6 5

输出 #2

5
2
2
3
4

注意

在第一个样本中,Sasha 制作了一个数字为 3 且特征为 (2, 2) 的生物。尼基塔创造了一个数字为 4 且特性为 (1, 1) 的生物。之后他们找出生物 3 的第一个特征和生物 4 的第二个特征。