{"raw_statement":[{"iden":"statement","content":"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.\n\nSasha 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.\n\nThey use their spells and are interested in some characteristics of their new creatures. Help them find out these characteristics."},{"iden":"input","content":"The first line contains integers _n_, _k_ and _q_ (1 ≤ _n_ ≤ 105, 1 ≤ _k_ ≤ 12, 1 ≤ _q_ ≤ 105) — number of characteristics, creatures and queries.\n\nNext _k_ lines describe original creatures. The line _i_ contains _n_ numbers _a__i_1, _a__i_2, ..., _a__in_ (1 ≤ _a__ij_ ≤ 109) — characteristics of the _i_\\-th creature.\n\nEach 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:\n\n*   _t__i_ = 1 means that Sasha used his spell to the creatures _x__i_ and _y__i_.\n*   _t__i_ = 2 means that Nikita used his spell to the creatures _x__i_ and _y__i_.\n*   _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_.\n\nIt's guaranteed that all creatures' numbers are valid, that means that they are created before any of the queries involving them."},{"iden":"output","content":"For each query with _t__i_ = 3 output the corresponding characteristic."},{"iden":"examples","content":"Input\n\n2 2 4\n1 2\n2 1\n1 1 2\n2 1 2\n3 3 1\n3 4 2\n\nOutput\n\n2\n1\n\nInput\n\n5 3 8\n1 2 3 4 5\n5 1 2 3 4\n4 5 1 2 3\n1 1 2\n1 2 3\n2 4 5\n3 6 1\n3 6 2\n3 6 3\n3 6 4\n3 6 5\n\nOutput\n\n5\n2\n2\n3\n4"},{"iden":"note","content":"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."}],"translated_statement":[{"iden":"statement","content":"Nikita 和 Sasha 玩一个电脑游戏，需要培育一些魔法生物。最初，他们有 #cf_span[k] 个生物，编号从 #cf_span[1] 到 #cf_span[k]。生物具有 #cf_span[n] 种不同的特性。\n\nSasha 有一个法术，可以由两个给定的生物创造一个新的生物。新生物的每个特性等于所用两个生物对应特性的最大值。Nikita 也有一个类似的法术，但他的法术中，新生物的每个特性等于所用两个生物对应特性的最小值。新生物获得最小的未使用编号。\n\n他们使用各自的法术，并对新生物的某些特性感兴趣。请帮助他们找出这些特性。\n\n第一行包含整数 #cf_span[n]、#cf_span[k] 和 #cf_span[q]（#cf_span[1 ≤ n ≤ 105]，#cf_span[1 ≤ k ≤ 12]，#cf_span[1 ≤ q ≤ 105]）——特性数量、生物数量和查询数量。\n\n接下来的 #cf_span[k] 行描述原始生物。第 #cf_span[i] 行包含 #cf_span[n] 个数字 #cf_span[ai1, ai2, ..., ain]（#cf_span[1 ≤ aij ≤ 109]）——第 #cf_span[i] 个生物的特性。\n\n接下来的 #cf_span[q] 行每行包含一个查询。第 #cf_span[i] 行包含数字 #cf_span[ti]、#cf_span[xi] 和 #cf_span[yi]（#cf_span[1 ≤ ti ≤ 3]），表示一个查询：\n\n保证所有生物的编号均有效，即它们在涉及它们的任何查询之前已被创建。\n\n对于每个 #cf_span[ti = 3] 的查询，请输出对应的特性。\n\n在第一个样例中，Sasha 创建了一个编号为 #cf_span[3]、特性为 #cf_span[(2, 2)] 的生物。Nikita 创建了一个编号为 #cf_span[4]、特性为 #cf_span[(1, 1)] 的生物。之后，他们查询了生物 #cf_span[3] 的第一个特性以及生物 #cf_span[4] 的第二个特性。"},{"iden":"input","content":"第一行包含整数 #cf_span[n]、#cf_span[k] 和 #cf_span[q]（#cf_span[1 ≤ n ≤ 105]，#cf_span[1 ≤ k ≤ 12]，#cf_span[1 ≤ q ≤ 105]）——特性数量、生物数量和查询数量。接下来的 #cf_span[k] 行描述原始生物。第 #cf_span[i] 行包含 #cf_span[n] 个数字 #cf_span[ai1, ai2, ..., ain]（#cf_span[1 ≤ aij ≤ 109]）——第 #cf_span[i] 个生物的特性。接下来的 #cf_span[q] 行每行包含一个查询。第 #cf_span[i] 行包含数字 #cf_span[ti]、#cf_span[xi] 和 #cf_span[yi]（#cf_span[1 ≤ ti ≤ 3]），表示一个查询：\n\n#cf_span[ti = 1] 表示 Sasha 使用了他的法术作用于生物 #cf_span[xi] 和 #cf_span[yi]。\n#cf_span[ti = 2] 表示 Nikita 使用了他的法术作用于生物 #cf_span[xi] 和 #cf_span[yi]。\n#cf_span[ti = 3] 表示他们想查询第 #cf_span[xi] 个生物的第 #cf_span[yi] 个特性。此时 #cf_span[1 ≤ yi ≤ n]。\n\n保证所有生物的编号均有效，即它们在涉及它们的任何查询之前已被创建。"},{"iden":"output","content":"对于每个 #cf_span[ti = 3] 的查询，请输出对应的特性。"},{"iden":"examples","content":"输入\n2 2 4\n1 2\n2 1\n1 1 2\n2 1 2\n3 3 1\n3 4 2\n输出\n2\n1\n\n输入\n5 3 8\n1 2 3 4 5\n5 1 2 3 4\n4 5 1 2 3\n1 1 2\n1 2 3\n2 4 5\n3 6 1\n3 6 2\n3 6 3\n3 6 4\n3 6 5\n输出\n5\n2\n2\n3\n4"},{"iden":"note","content":"在第一个样例中，Sasha 创建了一个编号为 #cf_span[3]、特性为 #cf_span[(2, 2)] 的生物。Nikita 创建了一个编号为 #cf_span[4]、特性为 #cf_span[(1, 1)] 的生物。之后，他们查询了生物 #cf_span[3] 的第一个特性以及生物 #cf_span[4] 的第二个特性。"}],"sample_group":[],"show_order":[],"formal_statement":"**Parameters**\n*   $n, k, q \\in \\mathbb{N}$: Number of characteristics, initial creatures, and queries, respectively.\n    *   $1 \\le n \\le 10^5$\n    *   $1 \\le k \\le 12$\n    *   $1 \\le q \\le 10^5$\n*   $\\mathcal{V}_0 = (\\mathbf{v}_1, \\dots, \\mathbf{v}_k)$: Initial sequence of vectors, where $\\mathbf{v}_i \\in \\mathbb{Z}^n$.\n    *   $\\forall i \\in \\{1, \\dots, k\\}, \\forall j \\in \\{1, \\dots, n\\}: 1 \\le \\mathbf{v}_{i,j} \\le 10^9$.\n*   $Q = ((t_1, x_1, y_1), \\dots, (t_q, x_q, y_q))$: Sequence of queries.\n\n**State Definitions**\nLet $\\mathcal{V}_r$ denote the sequence of vectors after processing $r$ queries.\nLet $L_r = |\\mathcal{V}_r|$ denote the number of vectors in the sequence after $r$ queries.\n*   Base Case: $L_0 = k$.\n\n**Process**\nFor each query $r$ from $1$ to $q$, let $(t_r, x_r, y_r)$ be the query parameters.\n\n1.  **If $t_r = 1$ (Sasha's Spell):**\n    *   A new vector $\\mathbf{v}_{new}$ is appended to the sequence.\n    *   $L_r = L_{r-1} + 1$.\n    *   For all $j \\in \\{1, \\dots, n\\}$:\n        $$ \\mathbf{v}_{L_r, j} = \\max(\\mathbf{v}_{x_r, j}, \\mathbf{v}_{y_r, j}) $$\n\n2.  **If $t_r = 2$ (Nikita's Spell):**\n    *   A new vector $\\mathbf{v}_{new}$ is appended to the sequence.\n    *   $L_r = L_{r-1} + 1$.\n    *   For all $j \\in \\{1, \\dots, n\\}$:\n        $$ \\mathbf{v}_{L_r, j} = \\min(\\mathbf{v}_{x_r, j}, \\mathbf{v}_{y_r, j}) $$\n\n3.  **If $t_r = 3$ (Query):**\n    *   The sequence remains unchanged: $\\mathcal{V}_r = \\mathcal{V}_{r-1}$ and $L_r = L_{r-1}$.\n    *   **Output:** The $y_r$-th component of the $x_r$-th vector:\n        $$ \\text{Result} = \\mathbf{v}_{x_r, y_r} $$\n\n**Constraint Guarantees**\n*   For $t_r \\in \\{1, 2\\}$: $1 \\le x_r, y_r \\le L_{r-1}$.\n*   For $t_r = 3$: $1 \\le x_r \\le L_{r-1}$ and $1 \\le y_r \\le n$.","simple_statement":null,"has_page_source":false}