When does Jennifer do math?

This is one of the world's largest unsolved problems at the moment, with dozens of world-renowned scientists struggling to find the answer to this question. You, a brilliant young researcher, have been working on this problem for the past six months. You've come up with a list of $N$ integers representing times you think Jennifer might do math.

However, one day, you find that your list has been stolen by the very Jennifer herself! You managed to strike a deal with Jennifer, and she has agreed to answer some peculiar questions about the list of numbers. In one question, you can ask her about:

1. the bitwise AND of the $i$-th and $j$-th numbers, or
2. the bitwise OR of the $i$-th and $j$-th numbers

for some indices $(i,j)$, and she will respond with the correct result.

Quirky as she is, Jennifer only permits questions on $M$ unordered pairs of indices $(a_i,b_i)$, which she will tell you before you start asking questions. She guarantees that you are able to determine a unique list of numbers by asking questions about only these $M$ pairs, regardless of the numbers in the list itself. However, since Jennifer is on a tight schedule (perhaps she needs to do math), she will answer no more than $2N-1$ questions.

Given these critical conditions, please write a program to recover your list of numbers!

Interaction

This is an interactive problem. The first line contains $2$ integers $N$ $(1\le N\le {10}^5)$ and $M$ $(0\le M\le 5\times {10}^5)$, the length of the list and the number of permitted pairs of indices respectively.

The next $M$ lines each contain $2$ integers $a_i$ and $b_i$ $(1\le a_i,b_i\le N)$, representing a permitted pair of indices $(a_i,b_i)$. In particular, it may be the case that $a_i=b_i$. It is guaranteed that you are able to determine a unique list of numbers by only asking questions about these $M$ pairs, regardless of the numbers in the list itself.

You will then begin interaction with Jennifer. If you would like to ask a question, you may output ? i & j (followed by a \n character) to ask the first type of question, or ? i | j (followed by a \n character) to ask the second type of question. For each of these questions, the pair $(i,j)$ or $(j,i)$ must be permitted. After either of these questions, Jennifer will respond with an integer (followed by a \n character), the answer to that question.

Otherwise, you may output ! followed by a space-separated list of $N$ integers in the range $[0,{10}^9]$ (followed by a \n character), representing your guess of the list of numbers. You must terminate your program immediately after performing this operation. Note that this operation does not count towards the limit of $2N-1$ questions.

For all cases, it is guaranteed that all of the correct numbers in the list are integers in the range $[0,{10}^9]$. Also, the list is fixed before the interaction begins and will not depend on your choice of questions.

For $30\mathrm{\%}$ of available marks, it is guaranteed that $1\le N\le {10}^3$, $M=\frac{N^2-N}{2}$, and all pairs $(i,j)$ where $i<j$ are permitted.

If at any point you attempt an invalid question (such as invalid output format or a prohibited pair of indices), Jennifer will respond with -1. You should terminate your program immediately after receiving this feedback, or you may receive an arbitrary verdict. If you exceed the limit of $2N-1$ questions or the final list you output is incorrect, you will receive a Wrong Answer verdict. Otherwise, you will receive a verdict of Accepted for the corresponding test case.

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.

In this case, Jennifer stole your list which had the numbers $[3,1,4,1,5]$.

5 9
1 2
1 3
1 5
2 3
2 4
2 5
3 4
3 5
4 5
>>> ? 1 & 3
0
>>> ? 2 | 5
5
>>> ? 4 | 3
5
>>> ? 1 & 2
1
>>> ? 4 | 5
5
>>> ! 3 1 4 1 5

Sample Explanation

This interaction would receive an Accepted verdict, since it correctly guessed the list of numbers using only the permitted pairs and it did not exceed the limit of $2N-1$ questions. Note that, for example, the questions ? 1 & 4, ? 4 | 1, and ? 1 & 1 are not permitted since $(1,4)$ and $(1,1)$ are not among the list of permitted pairs to ask questions about.