You had a directed graph with $N$ nodes and $M$ edges, but forgot the orientation of each edge. That is, the $i$-th edge could either go from $u_i$ to $v_i$ or from $v_i$ to $u_i$. Siesta still remembers the orientations, but she insists on keeping it a mystery and not telling you. Instead, she invites you to play the following detective game:

In one question to Siesta, you may ask about two sets of nodes $A$ and $B$. In response, she will give you a list of all the edges that go from some node in set $A$ to some node in set $B$. To challenge you further, she provides the extra constraint that the sum of the sizes of $A$ and $B$ over all questions must not exceed $3000$.

Your task is to change the orientation of some subset of the edges in the graph such that the resulting graph is acyclic. Can you solve this problem?

Interaction

This is an interactive problem. The first line contains $2$ space-separated integers $N$ $(2\le N\le 300)$ and $M$ $(1\le M\le \frac{N(N-1)}{2})$.

The next $M$ lines each contain $2$ space-separated integers $u_i$ and $v_i$ $(1\le u_i,v_i\le N)$, representing that the $i$-th edge either goes from $u_i$ to $v_i$ or from $v_i$ to $u_i$. Each edge connects $2$ distinct nodes, and there is at most one edge between any $2$ nodes.

You will then begin interaction with Siesta. To ask her a question, you should print $3$ lines to the output:

Line 1: ?, followed by a space, followed by $2$ space-separated integers $|A|$ and $|B|$ $(1\le |A|,|B|)$.
Line 2: $|A|$ space-separated integers $a_i$ $(1\le i\le |A|)$, representing the nodes in set $A$.
Line 3: $|B|$ space-separated integers $b_i$ $(1\le i\le |B|)$, representing the nodes in set $B$.

Furthermore, $1\le a_i,b_i\le N$ must hold, all $a_i$ must be distinct, and all $b_i$ must be distinct.

In response, you should read in one line from Siesta. This line will contain $R$, followed by $R$ space-separated integers $r_i$ $(1\le i\le R)$, representing the list of the indices of the edges in the graph that go from some node in set $A$ to some node in set $B$.

If you believe you have a solution to the problem, you may output !, followed by a space, followed by a binary string of length $M$. The $i$-th character of this string should be 1 if the $i$-th edge should have its orientation changed, or 0 otherwise. You must terminate your program immediately after performing this operation.

If at any point your output is ill-formatted, you attempt an invalid question, or the sum of $|A|+|B|$ exceeds $3000$, Siesta will respond with -1. At this point your program should exit in order to receive a Wrong Answer verdict.

Please note that you may need to flush stdout after each operation, or interaction may halt. In C++, this can be done with fflush(stdout) or cout << flush (depending on whether you use printf or cout). In Java, this can be done with System.out.flush(). In Python, you can use sys.stdout.flush().

Sample Interaction

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

4 5
4 1
4 2
2 1
2 3
4 3
>>> ? 2 1
>>> 1 3
>>> 4
2 1 5
>>> ? 1 1
>>> 3
>>> 2
0
>>> ? 4 4
>>> 1 3 2 4
>>> 2 3 4 1
5 3 4 1 5 2
>>> ! 00101

Sample Explanation

The initial graph is as follows (note that you cannot directly infer the orientations of the edges from the initial input):

After changing the orientation of the $3$-rd and $5$-th edge, as specified in the last line of the sample interaction, the graph looks like this:

This interaction would receive an Accepted verdict, since the graph is indeed acyclic after changing the specified orientations, and the sum of $|A|+|B|$ over all questions does not exceed $3000$. Note that only changing the orientation of the $2$-nd edge here would be an equally valid solution.