Description

A string of parentheses is said to be valid if it satisfies one of the following rules:

(1) The string is an empty string.

(2) If strings S and T are both valid, then ST is valid.

(3) If a string S is valid, then {S}, [S], (S) and <S> are valid as long as S does not contain any parentheses with higher precedence than its enclosing parentheses. The precedence order of parentheses from high to low is { }, [ ], ( ), < >.  Therefore, a string of {[]()} is valid, but a string of {([])} is not.

Given a string consisting of parentheses, determine if it is a valid string.

Input

The first line of the input contains an integer N (N ≤ 10000) denoting the number of test cases. Each of the next N lines corresponds to a test case, which contains a string of parentheses, and the maximum string length is no more than 1000 characters. Note that an empty string (a line which contains the newline character only) may be present in the input and it should be considered as a valid string according to rule (1).

Difficulty level 1: N <= 10

Difficulty level 2: N <= 50

Difficulty level 3: N <= 100

Difficulty level 4: N <= 1000

Difficulty level 5: N <= 10000

Output

For each test case, print in each line a "Yes" or a "No" to indicate that the string is valid or not. 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a string S, generate all different possible set of K characters in the string with P paddings, and sort them in lexicographic (dictionary) order. A padding is expressed as an underline '_'. For example, if K=2 and P=1, and the given string S is ‘CDBABBD’, the output would be

_AB
_AC
_AD
_BB
_BC
_BD
_CD
_DD
A_B
A_C
A_D
AB_
AC_
AD_
B_B
B_C
B_D
BB_
BC_
BD_
C_D
CD_
D_D
DD_

Input

The first line of input contains a positive integer T (T <= 30), which indicates the number of test cases.

For each case, there is a string S (length| <= 100), a positive integer K (K <= 10), and a nonnegative integer P (P <= 3) in a line. The length of S is less than or equal to 100 and S contains only 'A'-'J'; The number K, less than or equal to 10, indicates the number of non-padding characters in an output set. The nonnegative integer P indicates the number of paddings.

Output

For each test case, print in each line all different possible sets of K characters in the string with P paddings. The answers have to be sorted in the dictionary order, one substring per line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a sequence S of digits and a number K, for example S = "4113" and K = 2. In the sequence S, there is one '4', followed by two '1's, followed by one '3'. Then we can produce a new sequence S' = "142113".
(note: "one 4"  -> 14, "two 1s" -> 21, "one 3"  -> 13)

This is the first round, and we need to do it for K rounds. The input of the (i+1)-th round is the output from the i-th round. When i = 1, the sequence is the input S. Your task is to print the output after K rounds.

Another example:
S = "323", and K = 1
then we have one '3', followed by one '2', and followed by one '3'. So the next sequence S' would be "131213"
(note: "one 3" -> 13, "one 2" -> 12, "one 3" -> 13) 

Input

The input includes multiple test cases.
The first line of the input is an integer T (T <= 1000) specifying the number of test cases. For each case, the first line contains a sequence S. The second line contains one integer K.

Difficulty level 1: length of S <= 5, 1 <= K <= 2

Difficulty level 2: length of S <= 100, 1 <= K <= 2

Difficulty level 3: length of S <= 100, 1 <= K <= 5

Difficulty level 4: length of S <= 100, 1 <= K <= 5

Difficulty level 5: length of S <= 1000, 1 <= K <= 10 

Output

For each test case outputs one line, the output after k rounds.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Write a program that simulates a mouse in a maze. The program must count the steps taken by the mouse from the starting position to the goal.

An example of a maze:
S$###
$$#$$
$$$##
##$$G

It consists of S (starting position), # (walls), $ (road) and G (goal). In this example, it needs 7 steps from S to G. The mouse can move in four directions: up, down, left, and right. There may be more than one way to reach the goal, but the program only needs to print the smallest number of steps. If there is no way from S to G, then print -1.

Input

The first line has an integer N (1 <= N <= 1000), which means the number of test cases. For each case, the first line contains two integers. The first and second integers R and C (3 <= R,C <= 500) represent the numbers of rows and columns of the maze, respectively. The total number of elements in the maze is thus R * C. The following R lines, each containing C characters, specify the elements of the maze.

Output

Print the smallest number steps to reach the goal for each case. There is a newline character at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss