"Living on the edge!" is a brand new TV game show that targets graph theory enthusiasts as its main audience. During each episode, the host presents a new problem for the contestants to solve. The contestant who solves the problem wins an all-inclusive trip to the Croatian coast, including a guided (Eulerian) tour of the famous Walls of Dubrovnik, as the grand prize.

Tomislav was fortunate enough to get accepted as a contestant in the next episode and immediately began his preparations. He spent countless nights at the library reading up on the most obscure theorems. One night, he accidentally fell asleep and began dreaming about his appearance on the show. Upon waking, he vividly remembered the presented problem and his inability to solve it. The problem went as follows.

The game show host drew two rooted trees, both consisting of ~N~ nodes labelled with integers from ~1~ to ~N~. The trees themselves are labelled with integers ~1~ and ~2~. The host proceeded by stating that both trees are weighted, with positive weights, but the edge weights are purposefully kept secret. After that, Tomislav got the opportunity to choose any subset of node labels, as long as the size of that subset is exactly ~K~.

After Tomislav chose the said subset, he was able to ask at most ~Q~ questions of the form ~(a, b)~, where ~a~ and ~b~ are node labels. For each question, the host answered with an ordered quadruple ~(d_1(l_1, a), d_1(l_1, b), d_2(l_2, a), d_2(l_2, b))~, where ~d_t(x, y)~ represents the distance between nodes labelled ~x~ and ~y~ in tree ~t~, and ~l_t~ represents the label of the lowest common ancestor of nodes labelled ~a~ and ~b~ in tree ~t~.

In order to win the prize, Tomislav had to answer a bunch of similar questions posed by the game show host. More specifically, he had to answer exactly ~T~ questions of the form ~(p, q)~, where ~p~ and ~q~ are node labels belonging to Tomislav's chosen subset. For each question, Tomislav had to respond with the distance between nodes ~p~ and ~q~ in both trees, i.e. he had to provide the ordered tuple ~(d_1(p, q), d_2(p, q))~.

Your task is to help Tomislav with his preparations by writing a program that would solve the problem presented in his dream.

Interaction

This is an interactive task. Your program must communicate with a program made by the organizers which takes the role of the game show host. Of course, your program should take the role of Tomislav and ensure he wins the grand prize.

Your program should first read the parameters ~N~, ~K~, ~Q~, and ~T~ from the task description. These are given as four space-separated integers in the first line of the standard input.

Your program should proceed to read the description of two trees from the task statement. These descriptions are given in two lines, where the first line describes the first tree, while the second line describes the second tree.

Each tree is given as a sequence of ~N~ space-separated integers ~p_1, p_2, \dots, p_N~, where ~p_i \in \{-1, 1, 2, \dots, N\}~ represents the parent of node labelled ~i~ in the tree, or is equal to ~-1~ if the tree is rooted in the node labelled ~i~.

Your program should then output ~K~ different space-separated integers ~x_1, x_2, \dots, x_K~ ~(1 \le x_i \le N)~, representing the subset of node labels Tomislav should choose, and flush the output afterwards.

Your program may now ask up to ~Q~ questions by writing ? a b ~(1 \le a, b \le N)~ to the standard output. When your program has finished asking the questions, it should write a single character ! in its own line, and flush the output.

After that, your program may obtain the answers to the posed queries by repeatedly reading a line consisting of four space-separated integers ~d_1(l_1, a)~, ~d_1(l_1, b)~, ~d_2(l_2, a)~, and ~d_2(l_2, b)~ from the task description.

Your program should proceed by reading all ~T~ of the host's questions from the standard input. You must do so before writing any of your answers to the standard output. Each question is given in a single line by two space-separated integers ~p~ and ~q~ (where ~p, q \in \{x_1, x_2, \dots, x_K\}~) from the task description.

After your program has read all ~T~ questions, it should answer each of them by outputting two space-separated integers ~d_1(p, q)~, and ~d_2(p, q)~ in its own line. After printing all of the answers, your program should flush the output one last time.

Constraints

For all subtasks:

It is guaranteed that the hidden edge weights are positive integers not greater than ~2\,000~.

~2 \le K \le 100\,000~

~1 \le T \le \min(K^2, 100\,000)~

Subtask	Score	Constraints
~1~	~10~	~N = 500\,000~, ~Q = K-1~, trees are identical (including hidden edge weights)
~2~	~25~	~N = 500\,000~, ~Q = 2K-2~
~3~	~19~	~N = 500\,000~, ~K = 200~, ~Q = K-1~
~4~	~22~	~N = 1\,000\,000~, ~K = 1\,000~, ~Q = K-1~
~5~	~24~	~N = 1\,000\,000~, ~Q = K-1~

Sample Interaction

>>> denotes your output. Do not print this out.

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
>>> 3 5
>>> 5 3
>>> 2 8

Explanation for Sample

In this example, the program chose the subset ~\{1, 5, 7\}~. Then, it asked questions ~(1, 5)~ and ~(1, 7)~. For the first question, the lowest common ancestors of ~1~ and ~5~ are ~l_1 = 1~ and ~l_2 = 7~, and the answer is ~(d_1(1, 1) = 0, d_1(1, 5) = 2, d_2(7, 1) = 5, d_2(7, 5) = 3)~. For the second question, the lowest common ancestors of ~1~ and ~7~ are ~l_1 = 1~ and ~l_2 = 7~, and the answer is ~(d_1(1, 1) = 0, d_1(1, 7) = 3, d_2(7, 1) = 5, d_2(7, 7) = 0)~. Finally, the program was asked questions ~(1, 7)~, ~(7, 5)~, and ~(5, 1)~. The answers to these questions are ~(d_1(1, 7) = 3, d_2(1, 7) = 5)~, ~(d_1(7, 5) = 5, d_2(7, 5) = 3)~, and ~(d_1(5, 1) = 2, d_2(5, 1) = 8)~.