“Living on the edge!” 是一档全新的电视游戏节目，其主要受众是图论爱好者。在每一集中，主持人都会向参赛者提出一个新的问题。解决该问题的参赛者将赢得一次全包式的克罗地亚海岸之旅，包括对著名的杜布罗夫尼克城墙的导览（欧拉路径）作为大奖。

Tomislav 很幸运地被选中参加下一集的录制，并立即开始了准备工作。他在图书馆里度过了无数个夜晚，研读最晦涩的定理。一天晚上，他意外睡着了，并梦见了自己的参赛经历。醒来后，他清晰地记住了那个问题以及自己无法解决它的情景。问题如下：

游戏节目主持人画了两棵有根树，每棵树都包含 $N$ 个节点，节点编号从 $1$ 到 $N$。这两棵树分别标记为 $1$ 和 $2$。主持人说明这两棵树都是带权树，权重为正整数，但边的权重被刻意保密。之后，Tomislav 有机会选择任意一个节点标签的子集，只要该子集的大小恰好为 $K$。

在 Tomislav 选择好子集后，他可以提出最多 $Q$ 个形如 $(a, b)$ 的询问，其中 $a$ 和 $b$ 是节点标签。对于每个询问，主持人会回答一个有序四元组 $(d_1(l_1, a), d_1(l_1, b), d_2(l_2, a), d_2(l_2, b))$，其中 $d_t(x, y)$ 表示树 $t$ 中节点 $x$ 和 $y$ 之间的距离，而 $l_t$ 表示树 $t$ 中节点 $a$ 和 $b$ 的最近公共祖先。

为了赢得奖品，Tomislav 必须回答主持人提出的若干类似问题。具体来说，他必须回答恰好 $T$ 个形如 $(p, q)$ 的问题，其中 $p$ 和 $q$ 是属于 Tomislav 所选子集的节点标签。对于每个问题，Tomislav 必须提供两棵树中节点 $p$ 和 $q$ 之间的距离，即他必须提供有序元组 $(d_1(p, q), d_2(p, q))$。

你的任务是通过编写一个程序来帮助 Tomislav 准备，从而解决他梦中出现的问题。

交互

这是一个交互式任务。你的程序必须与由组织者编写的扮演游戏节目主持人的程序进行通信。当然，你的程序应扮演 Tomislav 的角色，并确保他赢得大奖。

你的程序首先需要从标准输入的第一行读取四个空格分隔的整数 $N, K, Q$ 和 $T$。

接下来，你的程序应读取任务描述中两棵树的描述。这些描述在两行中给出，第一行描述第一棵树，第二行描述第二棵树。

每棵树由 $N$ 个空格分隔的整数 $p_1, p_2, \dots, p_N$ 给出，其中 $p_i \in \{-1, 1, 2, \dots, N\}$ 表示树中节点 $i$ 的父节点，如果树以节点 $i$ 为根，则 $p_i = -1$。

然后，你的程序应输出 $K$ 个不同的空格分隔的整数 $x_1, x_2, \dots, x_K$ ($1 \le x_i \le N$)，代表 Tomislav 应选择的节点标签子集，并随后刷新输出。

现在，你的程序可以通过向标准输出写入 ? a b ($1 \le a, b \le N$) 来提出最多 $Q$ 个询问。当你的程序完成询问后，它应在单独的一行中写入单个字符 !，并刷新输出。

之后，你的程序可以通过重复读取包含四个空格分隔整数 $d_1(l_1, a), d_1(l_1, b), d_2(l_2, a)$ 和 $d_2(l_2, b)$ 的行来获取询问的答案。

你的程序应继续从标准输入读取主持人提出的所有 $T$ 个问题。每个问题在单行中给出，包含两个空格分隔的整数 $p$ 和 $q$（其中 $p, q \in \{x_1, x_2, \dots, x_K\}$）。

在你的程序读取完所有 $T$ 个问题后，它应通过在单独的行中输出两个空格分隔的整数 $d_1(p, q)$ 和 $d_2(p, q)$ 来回答每一个问题。在打印完所有答案后，你的程序应最后一次刷新输出。

说明：你可以从评测系统中下载示例源代码，该代码能与组织者编写的程序正确交互（包括输出刷新），并解决第一个示例。

数据范围

保证隐藏的边权重是不超过 $2000$ 的正整数。此外，在所有子任务中，均满足 $2 \le K \le 100\,000$ 且 $1 \le T \le \min(K^2, 100\,000)$。

样例

输入格式 1

9 3 2 3
2 -1 2 1 1 5 1 4 5
9 4 5 5 7 3 -1 3 7
1 5 7
? 1 5
? 1 7
!
0 2 5 3
0 3 5 0
1 7
7 5
5 1

输出格式 1

3 5
5 3
2 8

说明

在此示例中，程序选择了子集 $\{1, 5, 7\}$。然后，它询问了 $(1, 5)$ 和 $(1, 7)$。对于第一个问题，节点 $1$ 和 $5$ 的最近公共祖先分别为 $l_1 = 1$ 和 $l_2 = 7$，答案为 $(d_1(1, 1) = 0, d_1(1, 5) = 2, d_2(7, 1) = 5, d_2(7, 5) = 3)$。对于第二个问题，节点 $1$ 和 $7$ 的最近公共祖先分别为 $l_1 = 1$ 和 $l_2 = 7$，答案为 $(d_1(1, 1) = 0, d_1(1, 7) = 3, d_2(7, 1) = 5, d_2(7, 7) = 0)$。最后，程序被问及问题 $(1, 7), (7, 5)$ 和 $(5, 1)$。这些问题的答案分别为 $(d_1(1, 7) = 3, d_2(1, 7) = 5), (d_1(7, 5) = 5, d_2(7, 5) = 3)$ 以及 $(d_1(5, 1) = 2, d_2(5, 1) = 8)$。

Figure 1. 两棵有根树的示例