Description

Infix notation: X + Y

• Operators are written in-between their operands. This is the usual way we write expressions. An expression such as A * ( B + C ) / D is usually taken to mean something like: "First add B and C together, then multiply the result by A, then divide by D to give the final answer."

 

Prefix notation (also known as "Polish notation"): + X Y

• Operators are written before their operands. The expressions given above are equivalent to / * A + B C D

 

Now, please write a program to convert the given expressions from prefix to infix.

Input

The first line contains a positive integer N, indicating the number of testcases in this input.

In the following N lines, each line contains a prefix expression.

In each prefix expression, there is a space between numbers and operators, and operators and operators.

Output

Output the infix expression and its answer of each given prefix expression.

Note that

• There is a space between numbers and operators, and operators and operators.
• If the answer is integer, there is no need to print decimal point. Otherwise, you should print only one digit after the decimal point.
• You have to print a '\n' at the end of each ouput.
• Add a pair of parentheses to wrap around each operator and its operands.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

APP stands for "Another Palindrome Problem".

Given a string str with length n and an integer k, is it possible to transform str to a palindrome(回文) by removing at most k characters?

Explanation of sample io

You are given str = "fadicaf" and you can remove 3 characters at most. In this case you can remove 'd', 'i', and get "facaf", which is a palindrome. Therefore please output "Yes". Note that there may be multiple ways to transform str to a palindrome.

Maybe useless hints

 

Maybe useful hints

Draw the recursion tree, and then observe how many recursive function calls with same arguments are re-calculated. Is it possible to store the result of each recursive function call once it is calculated? If so, is it possible to use the results you have stored instead of re-calculate?

Input

The first line is two integers n, k, which are string length and max number of characters you can remove.

The second line is a string str.

• 1 <= n <= 1000

• 1 <= k <= 20, for the 1-5 th test case

• 1 <= k <= 1000, for the 6 th test case. Some tricks must be applied to pass this test case.

• str is of length n, consisting of lower case characters (a-z) only

Output

Output "Yes" (without quotation mark) in a line if str can be transformed to a palindrome by removing at most k characters, otherwise output "No" (without quotation mark) in a line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

This is a Sierpinski Carpet.

The construction of a Sierpinski Carpet is stated as follows. Initially, you are given a white square.

1. Divide the square into nine subsquares in a 3-by-3 grid.

2. Color the center subsquare with black.

3. For the rest eight subsquare, repeat step 1

For example,

Initially (after zero iteration), there is 0 black square in the Sierpinski Carpet.

After one iteration, there is 1 black square in the Sierpinski Carpet.

After two iterations, there are 9 black squares in the Sierpinski Carpet.

After three iterations, there are 73 black squares in the Sierpinski Carpet

Given an integer k, please output number of black squares after k iterations.

Maybe Useless Hint

• It is suggested to solve this problem using recursion. (Well ... there is mathematic solution, but hope you practice how to design recursion function)

• Be careful with overflow. Suggest to calculate with long long int.

Input

Input contain a single integer k.

Since there will be overflow issue if k is too big, so in this problem 0 <= k < 10.

Output

Output the number of black squares after the k-th iteration.

Note that there is a newline character after the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss