Description

Mr. Kuo is an adventurer. One day, he finds a secret room in a cave.

There is some hint to the password of this room.

 

Mr. Kuo is given an integer N and a string S = s₁s₂...s_N consisting of L, R, F, and B.

At first, Mr. Kuo has a string A = "0".

For each i = 1, 2, ..., N :

• If s_i is L, insert i to the left the "number" of i - 1 in A.
• If s_i is R, insert i to the right the "number" of i - 1 in A.
• If s_i is F, insert i to the front of A.
• If s_i is B, insert i to the back of A.

 

The final contents of A is the password. Please help Mr. Kuo find the password.

 

For example, N = 6 and S = "LRFRLB", then：

• s₁ = L, insert 1 to the left of 0, A = "10".
• s₂ = R, insert 2 to the right of 1, A = "120".
• s₃ = F, insert 3 to the front, A = "3120".
• s₄ = R, insert 4 to the right of 3, A = "34120".
• s₅ = L, insert 5 to the left of 4, A = "354120".
• s₆ = B, insert 6 to the back of A, A = "3541206".

 

Input

The first line contains one integer T — the number of test cases. Description of the test cases follows.

The first line of each test cases contains an integer N.

The second line of each test cases contains a string S consisting of L, R, F, and B of length N.

 

For each test：

1. T ≤ 100, N ≤ 100, S consists of L and R.
2. T ≤ 100, N ≤ 1000, S consists of L and R.
3. T ≤ 100, N ≤ 10000, S consists of L and R.
4. T ≤ 100, N ≤ 1000, S consists of L, R, F, and B.
5. T ≤ 100, N ≤ 10000, S consists of L, R, F, and B.
6. T ≤ 10, N ≤ 100000, S consists of L, R, F, and B.

 

Output

For each test case print a string A — the final contents of the password, seperated by spaces.

 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a prefix expression, please evaluate its value.

The grammar of prefix expression could be defined as: EXPR := OP EXPR EXPR | CONSTANT, where OP is one of +, -, *, /, %. For division and modolus operations, we adapt C behavior, i.e., rounding to zero.

It's guaranteed that in each step of the calculation the value is always between [-2⁶³, 2⁶³).

Note

You can use atoi() to convert a string to integer.

Input

There's only one line containing the prefix expression. There are spaces between each operands and operators. Each number in the expression is no less than -2³¹ and less than 2³¹.

Output

Please print out the value of the expression. Remember to put a newline character at the end of line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The story is just for fun. You can skip it and navigate to the last pragraph and hint directly as you wish.

Palm Islands are renowned artificial islands in Dubai, as well as a world-famous tourist hotspot, which shape is just like a palm, attracting thousands of millions of tourists every year. For the purpose of promoting the development of the tourism industry, Grand Duchy（大公國）of NTHU has also decided to build an artificial island called ''Tree Island''. The whole island consists of \(n\) attractions and \(n-1\) bidirected roads which connect two different attractions. Every two attractions are connected and between which there exists a unique path.

With an eye to developing tourism industry, the authority concerned planned to build some highway. Nevertheless, due to the inadequate budget, the Office of General Affairs resolved to build a highway between two ''second-longest'' attractions. Note that the ''second-longest'' distance means the distance is strictly less than the longest distance.

Hint

Recall the homework of the longest distance (a.k.a. diameter) of a tree. Instead of performing DFS twice, there is a solution to find the diameter in one DFS. For any tree whose root is \(i\), if we have two properties of its subtrees / children (\(j\)): the diameter (denoted by \(d\)) and the longest distance to any leaf (denoted by \(p\)), then we have \(p_i=\displaystyle\max_{\forall j\text{ is a child of }i}(p_j+w_{i,j})\), and \(d_i\) is either in its subtrees: \(\displaystyle\max_{\forall j\text{ is a child of }i}d_j\) or passing through the root: \(p_i+\displaystyle\max_{\forall j'\text{ is a child of }i}(p_{j'}+w_{i,j'})\), where \(j'\) mustn't be the same as we took in \(p_i\). For instance:

In the above digraph, we choose \(0\) to be root. For all internal nodes, \(p_4=18\) and \(d_4=28\); \(p_5=2+18=20\) and \(d_5=\max\{28, 20+10\}=30\); \(p_0=6+20=26\) and \(d_0=\max\{30, 26+8\}=34\).

Hence your task is to extend the above concept to second longest diameter. That is, could you find the relation between the root and its subtrees / children of the four properties:  diameter (\(d\)), the second diameter (\(d'\), the answer), the longest distance to any leaf (\(p\)) and the second-longest distance to any leaf (\(p'\))? What are the candidates of \(d_i, d'_i\) and what are the candidates of \(p_i, p'_i\)?

Note that since the tree is a bit large, you may need use a hand-written linked list (or some dynamic-length array) to store the tree.

Input

There are \(n\) lines in each test case. The first line contain an integer \(n < 10^5\) indicating the number of the attractions. The remaining \(n-1 \) lines contains three integers \(u_i, v_i, w_i (0\leq u_i, v_i<n, 0 < w_i < 100)\) which means there is an edge connected \(u_i, v_i\) lengthed \(w_i\).

There are 6 test cases. In the first two ones, \(n < 100\). In another two ones, \(w_i=1\). 

Output

Please print out an integer which is the ''second longest'' distance. Remember to put a newline character at the end of line.

Sample Input  Download

Sample Output  Download

Tags

Discuss