Description

Dogeon likes everything to be perfect, just like himself. When Dogeon learned about the data structure: Tree, he hoped every tree would be a perfect BST (binary search tree).

A perfect BST is a type of binary tree, in which every internal node has exactly two child nodes, and all the leaf nodes are at the same depth. What's more, every value stored in the left subtree's nodes will be less than the root's value, and every value stored in the right subtree's nodes will be greater than the root's value. For example, the tree shown below is a perfect BST.

One can easily observe that a perfect BST has exactly $2^k-1$ nodes. Now you will be provided a list of $2^k-1$ numbers, and you should work with Dogeon to construct the perfect BST out of these numbers. Since Dogeon knows that your previous lab has been tough, he will only give you two tasks:

1. int* pickPivot(int* begin, int* end) - Given pointers to the begin and one after the end of an array, you should select a number from the array and return a pointer to it. Dogeon will do a quick sort on the array based on the pivot you selected.
2. printPostorder(int *begin, int n) - Given pointers to the begin of a sorted array and its length, you should print the post-order traversal of the perfect BST.

• Hint: Is it possible to not build the actual tree?

Input

The first line contains an integer $N$, which is the size of the list.
The second line contains $N$ unique integers $a_1, a_2, a_3,\dots$, which are the elements of the array.

$N$
$a_1 \quad a_2 \quad a_3 \quad \dots \quad a_N$

Constraints

• $N = 2^k-1$, where $k$ is a natural number $(1,2,3,...)$
• $N \le 10^6$
• $-10^9 \le a_i \le 10^9$

Output

The output contains one line, the post-order traversal of the perfect binary search tree. Print a space after each number. You don't need to print a newline at the end.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14238.c

Partial Judge Header

14238.h

Tags

Discuss

Description

Procat (aka Procastinator Cat) has some maps. But some of them are duplicated. He will give you two of them \(X\) and \(Y\), hoping you could determine whether they are the same or not. However, Dogeon (aka Doge the Pigeon) has eaten part of the maps. Fortunately, Dogeon only ate all the empty brackets (i.e. ()), so the structure of the maps is still preserved.

Each map is a rooted tree. The tree consists of \(N\) vertices, numbered from \(1\) to \(N\). There are exactly one simple path between any two vertices.

Procat will give you the eaten map in a special format. The format is described by the following EBNF (Extended Backus–Naur form):

TREE ::= "(" INT TREE TREE ")"
      |  "(" INT TREE ")"
      |  "(" INT ")"

It means that a tree is a integer followed by no more than two subtrees. The integer represents the value of the vertex. If there is no subtree, it means the vertex is a leaf. Otherwise, the first subtree is the left child and the second subtree is the right child.

Let's look at some examples. In the figure below, tree (a) will be represented as (1(2)(3)), tree (b) as (1(3)(2)), and tree (c) as (3(1(2))). However, only tree (a) and tree (b) are considered the same.

Two maps are considered the same if and only if they have the same root and for every pair of vertices \((u, v)\) \((1 \le u, v \le N)\), which means the path from \(u\) to \(v\) in the first map is the same as the path from \(u\) to \(v\) in the second map.

Input

The first line contains an integer \(T\), the number of subtasks of the testcase. For all subtasks:

• First line contains one integer \(N\) indicates the number of vertices in each map.

• Each of the following two lines contains a string, representing map \(X\) and \(Y\) respectively in the EBNF format.

\(N\)
\(X\)
\(Y\)

Constraints

• \(1 \leq T \leq 5\)
• \(1 \leq N \leq 10^5\)
• length of \(X\) and \(Y\) won't exceed \(10^6\) characters
• \(X\) and \(Y\) only contains characters (, ) and digits.

Output

For each subtask, output one line containing "YES" if the two maps are the same, otherwise output "NO". Print a newline character after each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss