题目描述

题目译自 CEOI 2022 Day1 T3「Prize」

这是一道交互题。

Tomislav 在睡梦中想到了一个问题：给定两棵大小为 $N$ 的树，树上的节点按 $1\sim N$ 分别编号，树则分别编号为树 $1$，树 $2$，树有边权，但是边权被隐藏了起来。

Tomislav 需要向交互库提供一个大小为 $K$ 的编号的子集 $S$，在选择了这个集合后，小 C 可以问 $Q$ 个格式为 $(a,b)$ 的问题，定义 $d_t(x,y)$ 表示树 $t$ 上节点 $x$ 与节点 $y$ 的距离，$l_t$ 表示树 $t$ 上节点 $a$ 与节点 $b$ 的 LCA，交互库会依次回答 $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 S$，Tomislav 必须依次回答 $d_1(p,q)$ 和 $d_2(p,q)$。

可怜的 Tomislav 并不会做，请你帮帮他。

交互过程

第一行输入四个整数 $N,K,Q,T$。

接下来两行，每行 $N$ 个整数，第一行描述树 $1$，第二行描述树 $2$。描述方式为，给出 $N$ 个整数 $p_1,p_2,\ldots,p_N$，如果 $p_i$ 为 $-1$，则 $i$ 为树的根，否则 $p_i$ 为 $i$ 的父亲。

接下来请输出 $K$ 个整数 $x_1,x_2,\ldots,x_K$ 表示小 C 给出的编号集合 $S$，输出后请刷新缓冲区。

接下来你可以输出至多 $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)$，表示询问的答案。

接下来输入 $T$ 行，每行两个整数 $p,q$，表示一组交互库的询问。

你的程序需要回答这 $T$ 个询问，具体的，对于每一个询问，你需要输出一行两个整数 $d_1(p,q)$ 和 $d_2(p,q)$，在你回答完所有的问题后，刷新缓冲区。

附加文件中会有一份示例程序，这份程序可以通过下面的样例，你可以根据这份程序理解交互过程。

数据范围与提示

对于全部数据，保证所有边权为正整数且不超过 $2000$，$2\le K\le 10^5$，$1\le T\le \min(K^2,10^5)$。

交互示例