Mystical Tree Oracle

This is an interactive problem.

A long time ago, in the heart of the Nordic lands, there was a brave warrior named Roni. Renowned for his fearless courage and sharp mind, Roni could solve puzzles that even the wisest sages could not unravel. One day, Roni was summoned to an ancient forest where a mysterious tree stood. This tree was unlike any other – it was completely invisible, and its nodes and branches could not be seen by mortal eyes. In each node lived an ancient sprite, and the degree (i.e. the number of incident edges) of each node was the key to understanding the tree's structure.

The kingdom’s oracle, known as Xoracle, was a powerful entity. However, it could only answer one kind of question: "Tell me the bitwise XOR of the degrees of node A and node B." Here, the bitwise XOR operation is denoted by \(\oplus\) (in C++ and Python, it is the operator ^).

With this mysterious information, Roni must deduce the degree of every one of the \(N\) nodes in the tree in order to conquer the ancient sprites and unlock the tree's secret. The tree has \(N\) nodes and \(N-1\) edges, meaning it is connected (there exists a path between any two nodes). After at most \(Q\) queries to the oracle, its wisdom will be sealed forever.

Your task is to determine the degree of every node by strategically querying the oracle. When you query using two nodes \(i\) and \(j\), you will receive \(\operatorname{deg}(i) \oplus \operatorname{deg}(j)\) as the answer.

Note: Since this is an interactive problem, you normally make queries and flush your output after each query. For the purpose of testing, an offline simulation is allowed. In such a hack format, the input will first contain \(N\) and \(Q\) (separated by a space), and then (optionally) the actual degrees might be provided. In our sample solution, we ignore the queries and simply output a valid degree sequence corresponding to a star tree, which always forms a valid tree (for \(N>1\), the center node has degree \(N-1\) and all other nodes have degree 1; for \(N=1\), the degree is 0).

inputFormat

The first line of input contains two space-separated integers \(N\) and \(Q\), where \(N\) is the number of nodes in the tree and \(Q\) is the maximum number of queries you may perform. Nodes are numbered from 1 to \(N\).

In an interactive setting, your program may then make at most \(Q\) queries in the following format:

? i j

For testing purposes, the additional input may include the actual degrees, but your solution must only output the final answer in the format described below.

outputFormat

After you have finished your queries, output a single line starting with an exclamation mark !, followed by a space and then \(N\) space-separated integers representing the degrees of the \(N\) nodes (in any order). The output operation itself does not count as a query. Make sure to flush the output after each output operation.

sample

1 0

! 0