Interactive Array Guessing

Time limit3sMemory limit512 MB

Summary

Given n hidden arrays of up to 10 distinct values each, find all arrays using queries that return concatenated contents of chosen arrays, without delimiters.

Level: Hard8 of 10
Topics: Implementation, Divide and conquer, Math
Solved: No attempts yet

문제

Time limit: 3000 ms. Memory limit: 512 MB.

This is an interactive problem.

The jury has prepared $n$ non-empty integer arrays $a_1, a_2, \ldots, a_n$ . Each array consists of at most 10 positive integers not exceeding 1000. The elements of each array are pairwise distinct.

You can make queries of the following kind: choose several indices $q_1, q_2, \ldots, q_m$ , where $1 \le m \le n$ and $1 \le q_i \le n$ . These indices do not have to be distinct. The testing system tells you the contents of arrays $a_{q_1}, a_{q_2}, \ldots, a_{q_m}$ in the same order. However, these contents are concatenated without any delimiters.

Your task is to find the contents of all $n$ arrays.

Examples1

Example 1

Input

3

5 1 1 2 2 1

4 1 2 1 1

2 1 2

Expected output


? 3 1 2 3

? 3 1 3 1

? 1 2

! 1 1 2 1 2 2 2 1