You had a directed graph with nodes and edges, but forgot the orientation of each edge. That is, the -th edge could either go from to or from to . 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 and . In response, she will give you a list of all the edges that go from some node in set to some node in set . To challenge you further, she provides the extra constraint that the sum of the sizes of and over all questions must not exceed .

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 space-separated integers and .

The next lines each contain space-separated integers and , representing that the -th edge either goes from to or from to . Each edge connects distinct nodes, and there is at most one edge between any nodes.

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

Line 1: `?`

, followed by a space, followed by space-separated integers and .

Line 2: space-separated integers , representing the nodes in set .

Line 3: space-separated integers , representing the nodes in set .

Furthermore, must hold, all must be distinct, and all must be distinct.

In response, you should read in one line from Siesta. This line will contain , followed by space-separated integers , representing the list of the indices of the edges in the graph that go from some node in set to some node in set .

If you believe you have a solution to the problem, you may output `!`

, followed by a space, followed by a binary string of length . The -th character of this string should be `1`

if the -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 exceeds , 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 -rd and -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 over all questions does not exceed . Note that only changing the orientation of the -nd edge here would be an equally valid solution.

## Comments