Restore the Permutation
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Alex, Kostya, Andrew and Sergey have recently attended the famous Russian competitive programming camp.
One day, during the excursion they've became bored. Especially Sergey. So he asked Alex for some nice problem they can think about to dispel the boredom. And Alex told the following problem:
There is an 1-indexed permutation A of the first N positive integers, which is not known. You can ask two following kinds of queries:
- 1 X Y D : is it true that |AX - AY| is divisible by D without remainder?
- 2 X Y : is it true that AX < AY
Andrew and Kostya came up with the solution very quickly. But Sergey was really puzzled with this task. However, after thinking for some time, he came up with a solution too.
And then he figured out that he actually misheard the original problem that was a really easy one.
First Sergey got upset because of spending time for solving the non-existing problem, but then he realized that he can give this problem in a contest.
So he proposes to solve his version of the problem. :)
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first (and only) line of each test case contains a single integer N denoting the number of numbers in the permutation.
For each test case, output Q lines.
On every of these Q output first the type of the query, then the parameters, separated with single spaces. There can be three possible query types: the first two with the same format from the statement and the following one:
- 3 A1 A2 ... AN denoting the resulting permutation.
For the queries (types 1 and 2) you output, you will receive a feedback. The judge program will output "Yes" or "No" (both without quotes), denoting the answer to the corresponding query.
In a test case, you can ask no more than 13 × N queries of the first type and no more than N-1 queries of the second type. It is guaranteed that it will be possible to restore the permutation under the given constraints.
Please flush output buffer anytime you output a query.
- 1 ≤ sum of N ≤ 105
- 1 ≤ X, Y, D ≤ N
- Subtask 1 (16 points): 1 ≤ N ≤ 3
- Subtask 2 (25 points): 1 ≤ N ≤ 13
- Subtask 3 (30 points): 1 ≤ N ≤ 100
- Subtask 4 (29 points): 1 ≤ N ≤ 104
Input: 2 2 2 Output: 2 1 2 > (FEEDBACK) No 3 2 1 2 1 2 > (FEEDBACK) Yes 3 1 2
|Tags||divide-and-conq, ltime41, recursion, xcwgf666|
|Time Limit:||5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.