题目描述

题目译自 Ukrainian Olympiads in Informatics 2021 Stage 4 Day1 T2. Ти k-ий?

科扎克·武斯有三个秘密数组 $a, b, c$，它们由正整数组成。它们的长度分别记为 $|a|, |b|, |c|$，且长度不一定相同。已知每个数组都是有序的，即每个数组中的元素不小于前一个元素。

你希望获取关于这些数组的一些信息，具体来说，是想知道在三个数组合并并排序后的第 $k$ 个元素的值。也就是说，如果将这三个数组合并成一个长度为 $|a| + |b| + |c|$ 的大数组，并对其进行排序，你需要找出这个数组中的第 $k$ 个元素。

科扎克·武斯拒绝直接向你展示这些数组的内容。但他同意了一个折中的方式：你可以查询特定数组中的特定位置的值。你可以选择某个数组及其中的某个位置，然后科扎克·武斯会告诉你该位置上的元素值。请注意，你可以多次进行这种操作，且不一定针对同一个数组。由于科扎克是个非常忙碌的人，他只允许你向他提出不超过 $Q$ 个问题。

你的目标是找出三个数组合并后的第 $k$ 大元素。

输入格式

第一行包含五个整数 $|a|, |b|,|c|, k, g$ $(0 \leq |a|, |b|, |c| \leq 10^{6}, 1 \leq k \leq |a| + |b| + |c|)$。

已保证所有隐藏的数字都在 $[1, 10^{9}]$ 范围内。

数字 $g$ $(0 \leq g \leq 9)$ 表示子任务编号（参见数据范围与提示）。

交互方式

程序启动时，首先读取五个整数 $|a|, |b|, |c|, k, g$。

要进行一次查询，输出格式为 1 r m。其中，$r$ 表示数组的编号：如果 $r=1$，则操作针对数组 $a$；如果 $r=2$，则针对数组 $b$；如果 $r=3$，则针对数组 $c$。而 $m$ 表示该数组中的位置编号。例如，若对数组 $a$ 进行操作，查询第一个元素时 $m=1$，查询最后一个元素时 $m=|a|$。

例如，查询 1 3 10 表示获取数组 $c$ 中的第 $10$ 个元素。

在输出查询后，务必输出换行符并清空输出缓冲区，否则可能会导致「超时」判定。清空缓冲区的方法如下：

• 在 C++ 中使用 $\texttt{fflush(stdout)}$ 或 $\texttt{cout.flush()}$；
• 在 Java 中使用 $\texttt{System.out.flush()}$；
• 在 Pascal 中使用 $\texttt{flush(output)}$；
• 在 Python 中使用 $\texttt{stdout.flush()}$；
• 其他语言请参考相关文档。

请注意，如果你的查询无效（例如超过查询次数限制或查询不符合约束条件），交互器将输出 -1 并终止运行。如果读取到 -1，请立即终止程序，以获得「答案错误」判定，而不是其他未定义的判定结果。

当你找到答案 $x$ 时，输出 2 x。

3 3 3 2 0

2

5

5

2

6

6

6

7

10

1 1 1

1 1 2

1 1 3

1 2 1

1 2 2

1 2 3

1 3 1

1 3 2

1 3 3

2 2

在样例中，程序通过一系列查询获取了三个数组的部分或全部元素值，最终确定并输出了合并数组的第 $k$ 大元素为 $2$。

数据范围与提示

设 $n = \max(|a|, |b|, |c|)$，$m = \max(a_i, b_j, c_t)$。

详细子任务附加限制及分值如下表所示：