Description

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

The maze type is shown in following figure:

S$###
$$#$$
$$$##
##$$F

it consists of S (starting point), #(walls), $(road) and F (final point).

In above case, it needs 7 steps from S to F as following figure,

S$###
$$#$$
$$$##
##$$F

and the mouse can move in the four directions: up, down, left, right. There may be more than one way to reach final point, the program only need to print the least steps.

If there is no way from S to F, then print -1.

Input

The first line has an integer N(1<=N<=10^6), which means the number of test cases.

For each case, the first line has 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 x C.

The following R lines, each containing C characters, specify the elements of the maze.

Output

Print out the least steps for each case, and there is a new line character at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Wild cats take care of each other in the wild. However, when winter comes, the preys are not enough to feed all the cats. Therefore, the cats dine according to the order of their occupations. The order is as follows:
1. elder
2. nursy
3. kitty
4. warrior
5. apprentice
6. medicent
7. deputy
8. leader

In the tradition of the cat society, three different cats serve as the medicent, the deputy, and the leader respectively.
As for the other cats, except that the apprentices have the dining priority of the young over the old, for the other occupations, the old have higher priority. If the occupations and the ages of two or more cats are the same, they will dine in lexicographic order according to their names.

Input

There are multiple test cases.

The first line of each test case contains two integers N and M, indicating the number of cats and the portions of food respectively, where 0<N,M<=10000.

The next N lines are the information of each cat, including name, occupation, and age.
The length of the names will not exceed 30 letters and will contain no spaces.

Output

Please output the cats that could eat the food in order, each name a line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a positive integer N of int type, you are asked to find the maximum K such that N/(pow(2,K)) is a positive integer.

Input

The input is a positive integer N. (0<N)

Output

Please output pow(2,K).

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Flip game is played on a rectangular 4x4 field with two-sided pieces placed on each of its 16 squares. One side of each piece is white and the other one is black and each piece is lying either it's black or white side up. Each round you flip 3 to 5 pieces, thus changing the color of their upper side from black to white and vice versa. The pieces to be flipped are chosen every round according to the following rules:

1. Choose any one of the 16 pieces.
2. Flip the chosen piece and also all adjacent pieces to the left, to the right, to the top, and to the bottom of the chosen piece (if there are any).

Consider the following position as an example:

bwbw
wwww
bbwb
bwwb

Here "b" denotes pieces lying their black side up and "w" denotes pieces lying their white side up. If we choose to flip the 1st piece from the 3rd row (this choice is shown at the picture), then the field will become:

bwbw
bwww
wwwb
wwwb

The goal of the game is to flip either all pieces white side up or all pieces black side up. You are to write a program that will search for the minimum number of rounds needed to achieve this goal.

Input

The first line of the input is a positive integer T (T&lt;100), representing there are T test cases. Next, there are 4*T lines, each of which consists of 4 ‘w’ or ‘b’ characters. Each 4 of these 4*T lines correspond to one test case.

Output

For each test case in the input your program must produce one line of output, containing either an integer indicating the smallest number of lamps needed to reach a winning configuration, in case such a configuration exists, or the words "Impossible".

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given an integer pointer array **ptr with size N, and an integer array *array with size (N+1)*N/2. Please use malloc function to allocate memory to **ptr and *array. The *array is an ascending sequence of numbers. Each pointer in array **ptr shall point to one element of *array. And the elements pointed by the **ptr are also ascending.

For example, when n = 5, the size of **ptr will be 5, and the size of *array will be 15. The first pointer of **ptr is *ptr[0] which points to array[0], and the second pointer of **ptr is *ptr[1] which points to array[1], and the third pointer of **ptr is *ptr[2] which points to array[3], and the fourth pointer of **ptr is *ptr[3] which points to array[6].

Input

The first line is size of **ptr

The second line is offset

offset < size <10000

Output

Print each pointer of **ptr + offset

Note that you need to print a newline character ‘\n’ after each number, that is, just one number will be shown in each line of the output.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Given a linked list, you have to reverse it and output the result.

You have to implement four function:

1. Node* Create_List(Node*, int);

This function is used to create the linked list according to the input.

2. Node* Reverse_List(Node*);

This function is used to reverse the given linked list.

3. void Print_List(Node*);

This function is used to print out the key value in the linked list.

4. void Free_List(Node*);

This function is used to free the memory space.

Input

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

The next line contains n integers, each of which represents a node in the linked list.

It is guaranteed that :

• 1 ≤ n ≤ 10
• 0 ≤ ai ≤ 100

Output

You need to output the reversed linked lists.

Each key value is separated by "->".

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss