{"raw_statement":[{"iden":"statement","content":"Aram got bored of having a job, so he quit and went off to the distant country of Lalaland.\n\nLalaland has $N$ cities with unexciting names of $1, 2, \\\\dots, N$. There are $N -1$ rail lines connecting pairs of cities, making it possible to get from any city to any other. In other words, Lalaland is a tree.\n\nLalaland has something called an _unjob_. Unjobs are similar to jobs, except that people who have an unjob can't be fired, have no obligations, and don't get paid. This is exactly what Aram is looking for so he can prove theorems all day long.\n\nThe Lalaland government knows that the general public views these unjobs as somewhat unsavory, and they may also be attracting large numbers of foreigners into the country. Hence they passed a law requiring people with unjobs to live in faraway _terminal cities_: cities that are only connected to one rail line. The government hoped that this would keep people with unjobs far away from the center of their country.\n\nAram wants to go to a terminal city. Having never been to Lalaland, he asked his cosmopolitan friend David if he knows of a terminal city. David said no, but claimed to have travelled between every pair of cities of Lalaland and can remember if any given city was on the unique shortest sequence of rail lines between them. He lets Aram ask up to $N$ questions of the following form:\n\n \"For cities $a$, $b$, and $c$, do you pass by city $b$ as you travel along the shortest path from $a$ to $c$?\"\n\nIf Aram asks more than $N$ questions, David will get tired and take a nap for who knows how long. Help Aram quickly find a terminal city!\n\nThe first line of input from the judge contains a single integer $N$ ($3 <= N <= 2 thin 000$), the number of cities in Lalaland.\n\nFollowing this, you may submit up to $N$ queries of the following forms: \n\nThe judge will respond with either $1$ indicating that city $b$ is indeed between cities $a$ and $c$, or $0$ indicating that it is not.\n\nAt any time, you may submit an answer in the following form: \n\nAfter answering, your program must terminate immediately to get a verdict. Failing to follow this interaction protocol may result in unexpected errors. \n\nIf your input is malformed, the judge will output _-1_. Upon reading _-1_ your program should exit immediately to get a wrong answer verdict, otherwise you may get another error.\n\nPlease be sure to use the stream flushing operation after each query in order not to leave part of your output in the buffer. For example, in C++ you can use _fflush(stdout)_ or end with _cout <{}< endl_ or _cout <{}< flush_. In Java you can use _System.out.flush()_. In Python, you can use _stdout.flush()_. \n\nThe sample has two terminal cities, $1$ and $3$. Either answer would be accepted.\n\n"},{"iden":"interaction","content":"The first line of input from the judge contains a single integer $N$ ($3 <= N <= 2 thin 000$), the number of cities in Lalaland.Following this, you may submit up to $N$ queries of the following forms:   _? a b c_ — ($1 <= a, b, c <= N$) which asks if city $b$ will be visited while taking the shortest set of rail lines from city $a$ to city $c$. The judge will respond with either $1$ indicating that city $b$ is indeed between cities $a$ and $c$, or $0$ indicating that it is not.At any time, you may submit an answer in the following form:   _! x_ ($1 <= x <= N$) — which means your program claims that $x$ is a terminal city. After answering, your program must terminate immediately to get a verdict. Failing to follow this interaction protocol may result in unexpected errors. If your input is malformed, the judge will output _-1_. Upon reading _-1_ your program should exit immediately to get a wrong answer verdict, otherwise you may get another error.Please be sure to use the stream flushing operation after each query in order not to leave part of your output in the buffer. For example, in C++ you can use _fflush(stdout)_ or end with _cout <{}< endl_ or _cout <{}< flush_. In Java you can use _System.out.flush()_. In Python, you can use _stdout.flush()_. "},{"iden":"note","content":"The sample has two terminal cities, $1$ and $3$. Either answer would be accepted."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z} $, $ 8 \\leq N \\leq 1000 $, be the board dimension.  \nLet $ B \\in \\{ -, *, K \\}^{N \\times N} $ be the board configuration, where:  \n- $ B[i][j] = '-' $: empty square,  \n- $ B[i][j] = '*' $: professor’s piece at row $ i $, column $ j $,  \n- $ B[i][j] = 'K' $: your king at row $ i $, column $ j $.  \n\nLet $ P \\subseteq \\{ (i,j) \\mid 0 \\leq i,j < N \\} $ be the set of positions where pawns may be placed.  \n\n**Constraints**  \n1. Pawns can only be placed on empty squares: $ (i,j) \\in P \\Rightarrow B[i][j] = '-' $.  \n2. A pawn at $ (i,j) $ attacks squares $ (i-1, j-1) $ and $ (i-1, j+1) $ (diagonally upward-left and upward-right).  \n3. The king at $ (k_i, k_j) $ attacks all 8 adjacent squares: $ \\{ (k_i + \\delta_i, k_j + \\delta_j) \\mid \\delta_i, \\delta_j \\in \\{-1, 0, 1\\}, (\\delta_i, \\delta_j) \\neq (0,0) \\} $.  \n4. Pawns cannot be placed on squares occupied by the king or professor’s pieces.  \n5. All professor’s pieces (i.e., all $ (i,j) $ with $ B[i][j] = '*' $) must be under attack by at least one pawn or the king.  \n\n**Objective**  \nFind the minimum size of $ P $ such that every professor’s piece is attacked by either the king or at least one pawn.  \nIf impossible, output $ -1 $.","simple_statement":"You have an N×N chessboard with your king (K) and the professor’s pieces (*). You can place pawns to attack all professor’s pieces. A pawn attacks two diagonally forward squares (up-left and up-right). A king attacks all 8 surrounding squares. Pawns cannot overlap with existing pieces. Find the minimum number of pawns needed to attack every professor’s piece, or -1 if impossible.","has_page_source":false}