Just Another Disney Problem

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.

Input

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.

Output

Your questions — one line with three integers 1, X, Y (1 ≤ X, Y ≤ N, X ≠ Y). You should ask not more than 10000questions. In the last line: integer 0, then N integers a_i (1 ≤ a_i ≤ N) — the desired permutation or N zeros if such permutation doesn’t exist. All integers in the lines should be separated by spaces.

Note

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 Wall 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 code0. Failure to comply with this requirement may result in Time-limit exceeded error.