대화형 배열 맞히기

시간 제한3초메모리 제한512 MB

요약

길이가 최대 10인 숨겨진 배열 n개를 찾습니다. 질의는 고른 배열들의 내용을 구분자 없이 이어 붙인 결과를 돌려줍니다.

난이도: 어려움10점 중 8점
유형: 구현, 분할 정복, 수학
정답자: 아직 제출이 없습니다

문제

제한 시간: 3000 ms. 메모리 제한: 512 MB.

이 문제는 대화형 문제이다.

심사위원이 비어 있지 않은 정수 배열 $n$ 개 $a_1, a_2, \ldots, a_n$ 을 준비했다. 각 배열은 1000 이하의 양의 정수를 최대 10개 포함한다. 각 배열의 원소는 서로 다르다.

다음 형태의 질의를 할 수 있다. 인덱스 $q_1, q_2, \ldots, q_m$ 을 고른다. 이때 $1 \le m \le n$ 이고 $1 \le q_i \le n$ 이다. 인덱스끼리 서로 달라야 할 필요는 없다. 테스팅 시스템은 배열 $a_{q_1}, a_{q_2}, \ldots, a_{q_m}$ 의 내용을 같은 순서로 알려 준다. 다만 이 내용들은 구분자 없이 이어 붙여져 주어진다.

목표는 $n$ 개 배열의 내용을 모두 찾는 것이다.

예제1

예제 1

입력

3

5 1 1 2 2 1

4 1 2 1 1

2 1 2

예상 출력


? 3 1 2 3

? 3 1 3 1

? 1 2

! 1 1 2 1 2 2 2 1