Magic Breeding

题意翻译

尼基塔和萨莎玩电脑游戏，你需要培养一些神奇生物。起初，他们有$k$个编号从 $1$ 到 $k$ 的生物。每个生物具有不同的特征。 萨莎有一个法术能从两个给定的生物中创造一个新生物。它的每个特征将等于所用生物的相应特征的最大值。尼基塔有一个类似的法术，但在他的法术中，新生物的每个特征都等于所用生物的相应特征的最小值。新生物获得最小的未使用数字。 他们使用他们的法术，并对他们的新生物的某些特征感兴趣。帮助他们找出这些特征。 第一行包含整数 $n$ ， $k$ 和 $q$ （$1 <= n <= 10 ^ 5$ , $1 <= k <= 12$ , $1 <= q <= 10 ^ 5$），表示特征，生物和查询的数量。 接下来的 $k$ 行描述原始生物。第 $i$ 行包含 $n$ 个数字 $a_{i,1},a_{i,2},...,a_{i,n}(1 <= a_{i,j} <= 10 ^ 9)$ 表示第 i 个生物的特征。 下面 $q$ 行中的每一行都包含一个查询。这些行的第 $i$ 个包含数字 $t_i,xi$ 和 $ yi $ $(1 <= t_i <= 3)$ 。它们表示查询。 $ t_i = 1 $ 意味着萨莎将他的咒语用于生物 $x_i$ 和 $y_i$ $ t_i = 2 $ 意味着尼基塔将他的咒语用于生物 $x_i$ 和 $y_i$ $ t_i = 3 $ 意味着他们想知道第 $x_i$ 个生物的第 $y$ 个特征。在这种情况下，$ 1 <= y_i <= n $ 保证所有生物的数字都有效，这意味着它们是在涉及它们的任何查询之前创建的。 输出格式： 对于每个 $ t_i = 3 $ 的查询，输出相应的特征。

题目描述

Nikita and Sasha play a computer game where you have to breed some magical creatures. Initially, they have $ k $ creatures numbered from $ 1 $ to $ k $ . Creatures have $ n $ different characteristics. Sasha has a spell that allows to create a new creature from two given creatures. Each of its characteristics will be equal to the maximum of the corresponding characteristics of used creatures. Nikita has a similar spell, but in his spell, each characteristic of the new creature is equal to the minimum of the corresponding characteristics of used creatures. A new creature gets the smallest unused number. They use their spells and are interested in some characteristics of their new creatures. Help them find out these characteristics.

输入输出格式

输入格式

The first line contains integers $ n $ , $ k $ and $ q $ ( $ 1<=n<=10^{5} $ , $ 1<=k<=12 $ , $ 1<=q<=10^{5} $ ) — number of characteristics, creatures and queries. Next $ k $ lines describe original creatures. The line $ i $ contains $ n $ numbers $ a_{i1},a_{i2},...,a_{in} $ ( $ 1<=a_{ij}<=10^{9} $ ) — characteristics of the $ i $ -th creature. Each of the next $ q $ lines contains a query. The $ i $ -th of these lines contains numbers $ t_{i} $ , $ x_{i} $ and $ y_{i} $ ( $ 1<=t_{i}<=3 $ ). They denote a query: - $ t_{i}=1 $ means that Sasha used his spell to the creatures $ x_{i} $ and $ y_{i} $ . - $ t_{i}=2 $ means that Nikita used his spell to the creatures $ x_{i} $ and $ y_{i} $ . - $ t_{i}=3 $ means that they want to know the $ y_{i} $ -th characteristic of the $ x_{i} $ -th creature. In this case $ 1<=y_{i}<=n $ . It's guaranteed that all creatures' numbers are valid, that means that they are created before any of the queries involving them.

输出格式

For each query with $ t_{i}=3 $ output the corresponding characteristic.

输入输出样例

输入样例 #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

说明

In the first sample, Sasha makes a creature with number $ 3 $ and characteristics $ (2,2) $ . Nikita makes a creature with number $ 4 $ and characteristics $ (1,1) $ . After that they find out the first characteristic for the creature $ 3 $ and the second characteristic for the creature $ 4 $ .