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\%~ 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.