몬테 카를로 백작의 왕관 보석을 훔치기 위한 가장 정교한 강도 계획을 세운 당신은 마지막 장애물인 잠긴 금고를 마주했습니다. 하지만 당신은 바로 이 순간을 위해 훈련하며 금고털이 능력을 갈고닦았습니다.

금고에는 $N$개의 다이얼이 있으며, 각 다이얼은 $1$부터 $2N$까지의 정수 값 중 하나로 설정할 수 있습니다. 몬테 카를로 백작은 각 다이얼에 대해 올바른 비밀 값을 설정해 두었습니다. 금고를 열기 위해 당신은 각 다이얼을 원하는 값으로 설정한 뒤 금고 문 손잡이를 돌립니다. 모든 다이얼이 올바른 비밀 값으로 설정되어 있다면, 아무런 저항을 느끼지 못하고 문이 즉시 열릴 것입니다.

물론, 무작위로 모든 비밀 값을 추측하여 금고를 여는 것은 성공할 가능성이 매우 낮습니다. 하지만 전문 금고털이범으로서, 당신은 추측이 틀리더라도 문을 열려고 할 때 약간의 저항을 느낄 수 있으며, 그 정보를 사용하여 올바른 비밀 값을 알아낼 수 있습니다. 다이얼의 비밀 값이 $h$이고 문을 열려고 할 때 다이얼이 $d$로 설정되어 있다면, 다이얼은 문 손잡이를 돌리는 데 $|h - d|$만큼의 저항을 가합니다. 당신은 모든 다이얼에 걸리는 최대 저항을 느낄 수 있습니다. (이 값이 $0$이라면 금고를 성공적으로 열고 강도 행각을 완료한 것입니다!)

불행히도 보안 팀은 당신의 존재를 알아차렸고 당신의 위치로 접근하고 있습니다. 당신은 초당 한 번씩 금고를 열려고 시도할 수 있지만, 그들은 $4N$초 후에 도착합니다! 당신은 잡히기 전에 강도 행각을 완료할 수 있을까요?

인터랙션

이 문제는 인터랙티브 문제입니다. 인터랙션은 표준 입력으로부터 금고에 있는 다이얼의 개수인 정수 $N$ ($1 \le N \le 500$)을 읽으면서 시작됩니다. 당신의 프로그램은 각 다이얼에 대해 시도할 값을 지정하여 금고 문을 열기 위한 시도를 최대 $4N$번까지 할 수 있습니다. 각 시도 후에는 문 손잡이에서 느껴지는 저항을 전달받게 됩니다.

시도를 하려면, 각 다이얼에 대해 제안할 값 $d_1, d_2, \dots, d_N$ ($1 \le d_i \le 2N$)을 공백으로 구분하여 한 줄에 출력하십시오. 그런 다음 표준 입력으로부터 당신이 느낀 저항을 나타내는 정수 하나를 읽으십시오. 이 저항은 $\max_i |h_i - d_i|$이며, 여기서 $h_i$는 (당신이 알지 못하는) 다이얼 $i$의 비밀 값입니다. 저항이 $0$이면 금고를 연 것이며 프로그램은 종료되어야 합니다. 그렇지 않고 시도 횟수가 남아 있다면 다시 시도할 수 있습니다.

시도 횟수를 모두 소진하면 프로그램은 깔끔하게 종료되어야 합니다 (단, 제한 시간 내에 금고를 열지 못해 경비원에게 잡히면 오답으로 처리됩니다).

각 다이얼의 비밀 값은 강도 행각 이전에 몬테 카를로 백작이 설정한 것이며, 당신의 시도에 따라 변하지 않습니다.

참고

• 출력한 각 줄 뒤에는 반드시 출력 스트림을 비우고(flush), 인터랙션이 완료된 후에는 깔끔하게 종료하십시오. 또한, 출력할 정보와 줄 바꿈에 관한 인터랙션 프로토콜을 정확히 따르십시오. 예를 들어, 프로토콜에서 공백으로 구분된 정수 목록을 한 줄에 출력하도록 요구한다면, 심판은 각 정수를 별도의 줄에 출력하는 것을 허용하지 않습니다.
• 심판이 유효하지 않거나 예상치 못한 입력을 받으면 $-1$을 출력하고 즉시 종료합니다. 당신의 프로그램은 이 오류 보고를 감지하고 깔끔하게 종료하여 오답(Wrong Answer) 판정을 받아야 합니다. 프로그램이 심판의 추가 인터랙션을 기다리며 차단되거나 $-1$을 저항 값으로 해석하려고 시도하면, 오답 대신 다른 판정(시간 초과 또는 런타임 에러 등)을 받을 수 있습니다.
• 로컬 테스트를 위한 명령줄 도구가 제공됩니다. 이 도구의 상단에는 사용법에 대한 설명이 포함되어 있습니다.

예제

예제 1

3

1 1 1

5

3 4 5

1

4 5 6

0