Description

Bob is a man who wants to climb 3 step stairs.

Suppose he can only climb 1 or 2 step at a time.

Then , there are 3 possible ways to climb 3 step stairs

          (1)  1 step + 1 step + 1 step
          (2)  1 step + 2step
          (3)  2 step + 1step

The question is : if Bob want to climb X step stairs. 

How many possible ways are there to climp X step stairs.

Input

An integer N represents the number of testcases.

Then , there are following N lines.

Each line contain an integer X that  represents the number of stairs in that testcase.

P.S. 1<= X <=40

Output

An integer represents the number of possible way to climb N stairs.

Note that you have to add '\n' at the end of output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In this problem, we want you to use an array A to implement a perfect binary tree (a kind of binary tree which all interior nodes have two children and all leaves have the same depth or same level.). Given the level order sequence of the tree, please output the sequence of number after the tree is flattened. 

We call this flattening v2 "preorder traversal", which is another version of the origianl flattened tree.

For example, a perfect binary tree with level order sequence 4 2 6 1 3 5 7 looks like : 

After preorder traversal, so you should output 4 2 1 3 6 5 7. (Notice: This order is different from the homework)

 

[Hint]:

In the homework, the order of the output is inorder. (left child node -> root -> right child node)

In this problem, we need you to output the preorder sequence. (root -> left child node -> right child node)

 

 

Here is some tips for you guys to implement a binary tree.

1. A[1] is the root of the tree.

2. For the node locates in A[k], its left child locates in A[2k] and its right child locates in A[2k+1].

3. You can write a recursive function "find_seq" which takes the root index as its argument.

Input

The first line contains one integer n, representing the number of nodes in the tree.

The second line contains n integer ai, representing the level order of the tree.

It is guaranteed that :

• n = 2^k - 1
• 1 ≤ k ≤ 10
• a₁ ~ a_n is a permutation of 1 ~ n

Output

Please output the sequence of number after the tree is traversal. Each number is separated by a whitespace.

Note that you have to add '\n' at the end of output

Sample Input  Download

Sample Output  Download

Tags

Discuss