Après avoir planifié le casse le plus élaboré pour voler le Joyau de la Couronne du Comte Monte Carlo, vous avez rencontré l'ultime obstacle sur votre chemin : un coffre-fort verrouillé. Cependant, vous vous êtes entraîné pour ce moment précis et avez aiguisé vos capacités de perceur de coffres.

Le coffre possède $N$ cadrans, chacun pouvant être réglé sur une valeur entière de $1$ à $2N$. Le Comte Monte Carlo a configuré le coffre avec une valeur secrète correcte pour chaque cadran. Pour tenter d'ouvrir le coffre, vous réglez chaque cadran sur une valeur de votre choix, puis vous tournez la poignée de la porte du coffre. Si chaque cadran est réglé sur sa valeur secrète correcte, vous ne ressentirez aucune résistance et la porte s'ouvrira immédiatement.

Bien sûr, ouvrir le coffre en devinant au hasard toutes les bonnes valeurs secrètes a très peu de chances de réussir. Cependant, en tant qu'expert en la matière, même si votre tentative est erronée, vous ressentez une certaine résistance lorsque vous essayez d'ouvrir la porte, et vous pouvez utiliser cette information pour aider à déchiffrer les valeurs secrètes correctes. Si un cadran a pour valeur secrète $h$ et que le cadran est réglé sur $d$ lorsque vous essayez d'ouvrir la porte, le cadran exercera une résistance $|h - d|$ sur la rotation de la poignée. Vous pouvez ressentir la résistance maximale sur l'ensemble des cadrans. (Notez que si cette valeur est $0$, vous avez réussi à ouvrir le coffre et à terminer votre casse !)

Malheureusement, l'équipe de sécurité a été informée de votre présence et se rapproche de votre position. Vous êtes en mesure de faire une tentative d'ouverture du coffre par seconde, mais ils sont à $4N$ secondes de vous ! Pouvez-vous terminer le casse avant de vous faire attraper ?

Interaction

Ceci est un problème interactif. L'interaction commence par la lecture d'un entier $N$ ($1 \le N \le 500$) depuis l'entrée standard, représentant le nombre de cadrans sur le coffre. Votre programme peut effectuer jusqu'à $4N$ tentatives pour ouvrir la porte du coffre en spécifiant une valeur à essayer pour chaque cadran. Vous serez ensuite informé de la résistance que vous ressentez au niveau de la poignée après chaque tentative.

Pour effectuer une tentative, imprimez une ligne contenant $N$ entiers séparés par des espaces $d_1, d_2, \dots, d_N$ ($1 \le d_i \le 2N$), les valeurs que vous proposez pour chaque cadran. Ensuite, lisez un seul entier depuis l'entrée standard représentant la résistance que vous avez ressentie au niveau de la poignée, $\max_i |h_i - d_i|$, où $h_i$ est la valeur secrète (inconnue pour vous) du cadran $i$. Si la résistance est $0$, vous avez ouvert le coffre et votre programme doit se terminer. Sinon, s'il vous reste des tentatives, vous pouvez réessayer.

Si vous épuisez vos tentatives, votre programme doit se terminer proprement (bien qu'il soit jugé incorrect pour ne pas avoir réussi à forcer le coffre à temps pour échapper aux gardes).

La valeur secrète de chaque cadran a été configurée par le Comte Monte Carlo avant le casse et ne changera pas en réponse à vos tentatives de forçage.

Notes

N'oubliez pas de vider le flux de sortie après chaque ligne que vous imprimez et de quitter proprement une fois l'interaction terminée. Veuillez également vous assurer de suivre exactement le protocole d'interaction ci-dessus concernant les informations à imprimer sur chaque ligne de sortie : par exemple, si le protocole exige que vous imprimiez une liste d'entiers séparés par des espaces sur une seule ligne, le juge n'acceptera pas chaque entier sur sa propre ligne.

Si le juge reçoit une entrée invalide ou inattendue, il imprimera $-1$ puis quittera immédiatement. Votre programme doit détecter ce rapport d'erreur et quitter proprement afin de recevoir un verdict de Wrong Answer. Si votre programme se bloque en attendant une interaction supplémentaire du juge, ou tente d'interpréter le $-1$ comme une valeur de résistance, vous pourriez recevoir un verdict de rejet différent (tel que Time Limit Exceeded ou Runtime Error) au lieu de Wrong Answer.

Vous disposez d'un outil en ligne de commande pour les tests locaux. L'outil contient des commentaires en haut expliquant son utilisation.

Exemples

Entrée 1

3

Sortie 1

1 1 1

Entrée 2

5

Sortie 2

3 4 5

Entrée 3

1

Sortie 3

4 5 6

Entrée 4

0