{"raw_statement":[{"iden":"statement","content":"Evil wizard Jafar has a huge collection of lamps. He likes touching them, wiping the dust, looking at his reflection in them. He loves all of them almost equally, they are very beautiful, but for every two of them he likes one of them more than another one. Jafar keeps his lamps in a very long hall, all lamps in one line. One day he decided to arrange all lamps along his way from one side of the hall to another in such a way, that for every two neighboring lamps he likes the next one more than previous. In other words Jafar would like a some kind of an ascending order of lamp's quality. You are a new servant of wizard and you should fulfill the desire of your master. The main problem is that you don't know anything about Jafar's preferences. You can ask Jafar for any two lamps which one is better, but you should be careful, he is very busy now in his plans for world domination and you shouldn't ask him too much questions. Note that preferences could be non-transitive. You should output desired order of all lapms or report Jafar that it doesn't exist.\n\nFirst number — N (1 ≤ N ≤ 1000). Answer for every question — string \"_YES_\", if Y is better than X, and \"_NO_\", if X is better than Y.\n\nYour questions — one line with three integers 1, X, Y (1 ≤ X, Y ≤ N, X ≠ Y). You should ask not more than 10 000 questions. In the last line: integer 0, then N integers ai (1 ≤ ai ≤ N) — the desired permutation or N zeros if such permutation doesn't exist. All integers in the lines should be separated by spaces.\n\nThe pipe from your program to the interactor program and the pipe back have limited size. Your program must read from the standard input to avoid deadlock. Deadlock condition is reported as Time-limit exceeded.\n\nTo flush the standard output stream use the following statements:\n\nIn C use fflush(stdout);\n\nIn C++ use cout.flush();\n\nIn Java use System.out.flush();\n\nIf your program receives EOF (end-of-file) condition on the standard input, it MUST exit immediately with exit code 0. Failure to comply with this requirement may result in Time-limit exceeded error.\n\n"},{"iden":"input","content":"First number — N (1 ≤ N ≤ 1000). Answer for every question — string \"_YES_\", if Y is better than X, and \"_NO_\", if X is better than Y."},{"iden":"output","content":"Your questions — one line with three integers 1, X, Y (1 ≤ X, Y ≤ N, X ≠ Y). You should ask not more than 10 000 questions. In the last line: integer 0, then N integers ai (1 ≤ ai ≤ N) — the desired permutation or N zeros if such permutation doesn't exist. All integers in the lines should be separated by spaces."},{"iden":"examples","content":""},{"iden":"note","content":"The pipe from your program to the interactor program and the pipe back have limited size. Your program must read from the standard input to avoid deadlock. Deadlock condition is reported as Time-limit exceeded.To flush the standard output stream use the following statements:In C use fflush(stdout);In C++ use cout.flush();In Java use System.out.flush();If your program receives EOF (end-of-file) condition on the standard input, it MUST exit immediately with exit code 0. Failure to comply with this requirement may result in Time-limit exceeded error."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z} $, $ 1 \\leq N \\leq 1000 $, be the number of lamps.  \nLet $ L = \\{1, 2, \\dots, N\\} $ be the set of lamp indices.  \nLet $ \\succ $ be a strict binary relation on $ L $, where $ x \\succ y $ means \"lamp $ x $ is preferred over lamp $ y $\" (i.e., $ x $ is better than $ y $).  \nThe relation $ \\succ $ is **total** (for all $ x \\ne y $, exactly one of $ x \\succ y $ or $ y \\succ x $ holds) and **may be non-transitive**.\n\n**Constraints**  \n1. You may query the relation $ \\succ $ at most $ 10{,}000 $ times.  \n2. Each query: ask for $ x, y \\in L $, $ x \\ne y $, and receive \"YES\" if $ x \\succ y $, \"NO\" if $ y \\succ x $.  \n3. Goal: Find a permutation $ \\pi = (\\pi_1, \\pi_2, \\dots, \\pi_N) $ of $ L $ such that $ \\pi_i \\succ \\pi_{i+1} $ for all $ i \\in \\{1, \\dots, N-1\\} $, **or** determine that no such permutation exists.\n\n**Objective**  \nOutput a permutation $ \\pi $ of $ L $ such that:  \n$$\n\\pi_1 \\succ \\pi_2 \\succ \\cdots \\succ \\pi_N\n$$  \nor output $ N $ zeros if no such total ascending chain exists.","simple_statement":"You are given N lamps. For any two lamps, Jafar prefers one over the other, but you don’t know the preferences. You can ask at most 10,000 questions: for two lamps X and Y, ask if Y is better than X (answer \"YES\" or \"NO\"). Your goal: arrange all lamps in a line so that each next lamp is preferred over the previous one. If impossible, output N zeros. Output the final order as a permutation of lamp numbers.","has_page_source":false}