github.com/captn3m0/codechef.git

---
{"category_name":"hard","problem_code":"FGTREE","problem_name":"Forgotten Tree 9","problemComponents":{"constraints":"","constraintsState":false,"subtasks":"","subtasksState":false,"inputFormat":"","inputFormatState":false,"outputFormat":"","outputFormatState":false,"sampleTestCases":{}},"video_editorial_url":"","languages_supported":{"0":"CPP14","1":"C","2":"JAVA","3":"PYTH 3.6","4":"PYTH","5":"PYP3","6":"CS2","7":"ADA","8":"PYPY","9":"TEXT","10":"PAS fpc","11":"NODEJS","12":"RUBY","13":"PHP","14":"GO","15":"HASK","16":"TCL","17":"PERL","18":"SCALA","19":"LUA","20":"kotlin","21":"BASH","22":"JS","23":"LISP sbcl","24":"rust","25":"PAS gpc","26":"BF","27":"CLOJ","28":"R","29":"D","30":"CAML","31":"FORT","32":"ASM","33":"swift","34":"FS","35":"WSPC","36":"LISP clisp","37":"SCM guile","38":"PERL6","39":"ERL","40":"CLPS","41":"ICK","42":"NICE","43":"PRLG","44":"ICON","45":"COB","46":"SCM chicken","47":"PIKE","48":"SCM qobi","49":"ST","50":"NEM"},"max_timelimit":3,"source_sizelimit":50000,"problem_author":"lg5293","problem_tester":null,"date_added":"9-05-2019","tags":{"0":"june19","1":"junechallenge","2":"lg5293"},"problem_difficulty_level":"Hard","best_tag":"","editorial_url":"https://discuss.codechef.com/problems/FGTREE","time":{"view_start_date":1560763800,"submit_start_date":1560763800,"visible_start_date":1560763800,"end_date":1735669800},"is_direct_submittable":false,"problemDiscussURL":"https://discuss.codechef.com/search?q=FGTREE","is_proctored":false,"visitedContests":{},"layout":"problem"}
---
### Read problem statements in [Hindi](https://www.codechef.com/download/translated/JUNE19/hindi/FGTREE.pdf), [Bengali](https://www.codechef.com/download/translated/JUNE19/bengali/FGTREE.pdf), [Mandarin Chinese](https://www.codechef.com/download/translated/JUNE19/mandarin/FGTREE.pdf), [Russian](https://www.codechef.com/download/translated/JUNE19/russian/FGTREE.pdf), and [Vietnamese](https://www.codechef.com/download/translated/JUNE19/vietnamese/FGTREE.pdf) as well.

There is a rooted binary tree with $N$ nodes. For each node with exactly two children, one of them is called the left child and the other is called the right child. If a node has only one child, it is still specifically called either the left child or the right child.

The nodes are labelled $1$ through $N$ according to the inorder traversal of the tree. That is, the labelling can be generated by the following pseudocode:
```
integer index = 1

function dfs(node n):
    if n has left_child:
        dfs(n.left_child)
    n.label = index
    index += 1
    if n has right_child:
        dfs(n.right_child)

run dfs(root)
```

For each node $x$, the subtree of this node consists of the node $x$ itself and all its (direct or indirect) descendants. Since the nodes are labelled according to inorder traversal, the subtree of node $x$ can be described by two integers $a_x$ and $b_x$ in the following way: the nodes $a_x, a_x+1, \ldots, b_x$ all belong to the subtree of node $x$ and all other nodes do not belong to this subtree.

You do not know the structure of the tree. You would like to reconstruct it by asking questions in the form: "Is $a_x$ equal to $a$ and also $b_x$ equal to $b$?" You may ask at most $300$ such questions. Find the root and the parent of each non-root node.

### Interaction
- First, you should read a line containing a single integer $T$ — the number of test cases. The description of interaction for $T$ test cases follows.
- For each test case, you should start by reading a line containing a single integer $N$.
- Afterwards, you may ask questions. To ask a question, print a line containing the character 'Q' followed by a space and three space-separated integers $x$, $a$ and $b$ ($1 \le x \le N$, $1 \le a \le x \le b \le N$). Then, you should read a line containing the string `"Yes"` if $a$ is equal to $a_x$ and $b$ is equal to $b_x$ or `"No"` otherwise.
- When you are ready to answer, print a line containing the character 'A' followed by a space and $N$ space-separated integers $p_1, p_2, \ldots, p_N$. For each valid $i$, $p_i$ should denote the parent of the $i$-th node or, if the $i$-th node is the root, it should be $-1$. Your answer will be considered correct if it exactly describes the hidden tree.

Don't forget to flush the output after printing each line!

### Constraints
- $1 \le T \le 100$

### Subtasks
**Subtask #1 (20 points):** $1 \le N \le 10$

**Subtask #2 (20 points):** $1 \le N \le 20$

**Subtask #3 (30 points):** $1 \le N \le 50$

**Subtask #4 (30 points):** $1 \le N \le 100$

### Example Input
```
Grader  | You
2       |
2       |
        | Q 1 1 2
No      |
        | A 2 -1
5       |
        | Q 4 1 5
Yes     |
        | Q 1 1 4
No      |
        | Q 3 1 3
Yes     |
        | Q 1 1 2
Yes     |
        | A 3 1 4 -1 4
```

### Explanation
**Example case 1:** The tree has only two nodes — node $2$ is the root and node $1$ is its left child. In this case, we have $a_1 = 1$, $b_1 = 1$, $a_2 = 1$ and $b_2 = 2$. First, we ask if the subtree of node $1$ subtree contains the nodes $1$ and $2$. The answer is "No", so we know that node $2$ is the root and node $1$ is its child, which is what we needed to find out.

**Example case 2:** In the first question, we ask if nodes $1$ through $5$ are all in the subtree of node $4$. In this case, the answer is "Yes", so we know that node $4$ is the root of the whole tree. We still need to ask more questions to determine how nodes $1$, $2$, $3$ and $5$ are connected to it.

<aside style='background: #f8f8f8;padding: 10px 15px;'><div>All submissions for this problem are available.</div></aside>