Description

There are N strings whose length are exactly 10. And all the strings consists of exactly one 'x' and some '0' or/and '1'.

You need to answer how many kinds of strings are there.

Note: be careful of the efficiency of your strategy. And we don't suggest you to solve this problem by sorting.

Input

The first line contains one integers N (1 ≤ N ≤ 10⁵) – the number of the strings.

Then N lines follow. The i+1-th line contains one integers S_i – the i-th string you are given.

Output

Output how many kinds of strings are there and then output a newline('\n').

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Let's call a grid 8-puzzle board if the gridsize is 3 x 3 and there is exactly one cell is 'x' and others are '1' or '0'.

In one operation, you can exchange the 'x' cell of a 8-puzzle board with any cell which is adjacent to the 'x' cell. The cell (i, j) is adjacent to the cell (i-1, j), (i, j-1), (i, j+1) and (i+1, j).

Now you need to solve T tasks. In each task, you are given two 8-puzzle boards A, B and one integer K. You need to answer whether it's possible to make A into B in at most K operations.

Let's take an example. In the first task of Sample, you can make A into B in the following 2 operations:

0 x 0           0 0 x           0 0 1

1 0 1 ========> 1 0 1 ========> 1 0 x

0 1 1           0 1 1           0 1 1

                exchange (1,3)  exchange (2,3)

Input

The first line contains an integer T (1 ≤ T ≤ 10) – the number of tasks you need to solve.

And for each task, first you are given one integer K (0 ≤ K ≤ 9) – the maximum number of operations you can execute. Then you are given A and B. Both of them are in 3 lines of 3 characters. Please refer to Sample Input.

Output

For each task output "Yes" if it's possible to make A into B in K operations. Otherwise output "No". Then print a newline('\n').

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There are T tasks you have to solve. In each task, you are given a maze which is a n x m grid. Each cell is marked exactly one character. In the begining, you are at starting point. You need to answer whether it's possible to go to destination. Here are the rules:

1. The cell marked '$' is starting point and the cell marked '&' is destination. There must be exactly one starting point and exactly one destination.
2. The cell marked '#' is wall, you cannot be at that cell.
3. Suppose you are at the cell (i, j), you can go to adjacent cell(i.e (i-1, j), (i, j-1), (i, j+1) and (i+1, j)) if the cell you want to go is not out of bounds and is not marked as '#'.
4. If you are at the cell marked lower case letter, you will be send to the cell marked in corresponding upper case letter. But not vice versa. That is if you are at the cell marked upper case letter, nothing will happen. So you can imagine that they are one-way portal. For every existing lower case letter, there must be exactly one corresponding  upper case letter. And vice versa.

The folloing show how to go to destination for the first and the third task in Sample.

$b.#.                           $a.#.

...#B                           ...#A

...##                           #..#.

##..&                           ...#&

                                .#.#.

-the first task                  -the third task

Note: be carefule of the efficiency of your strategy. 

Input

The first line contains an integer T (1 ≤ T ≤ 10) – the number of tasks you have to solve.

For each task, first there are two integers N, M (2 ≤ N, M ≤ 300) – the gridsize of the maze. Then following N lines contain M characters each, the j-th element in the i-th line S_ij is the character marked for the (i, j) cell(S_ij must be '$' or '&' or '#' or '.' or letter).

Output

For each task output "Yes" if it's possible to go to destination. Otherwise output "No". Then print a newline('\n').

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Yazmonkey loves to drink banana milk, he drinks it whenever he is stressfull or he needs his brain power.

Now, there are N groups of programmers are seeking for Yazmonkey's help since it is expert in debugging. Yazmonkey will first help the group of programmers that give the most banana milk to him. Can you help Yazmonkey to find out the order that it is going to help?

Every person in a group will carry a few cartons of banana milk, Yazmonkey is going to help the group that give it the most amount of banana milk, if there are some groups that carry same amount of banana milk, Yazmonkey will first help the group that the person who gives the most amount of banana milk among these groups belong to. If they're still the same, Yazmonkey will first help the group with more people, if they're still the same, Yazmonkey will help them according to the input order.

Input

The first line of input contains one integers T (1 ≤ T ≤ 5), representing the number of test cases.

For each test case, first line of input contains one integer (1 ≤ N ≤ 2000), representing the number of group.
Next input  N lines, each line first input a integer Ki (1 ≤ Ki ≤ 1000000), representing the number of people in this group, and then input Ki integer Aij(1 ≤ Aij ≤ 1000000), representing the quantity of banana milk that each person gives.
Guarantee that for each testcase, there are at most 1000000 persons, that is, sum of Ki is less than or equal to 1000000.

Output

Output the group info(how many banana milk does each person gives with the order that Yazmonkey is going to help.
Remember to output '\n' at the end of every line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Although Yazmonkey is expert in debugging, his typing speed is very slow because every time he it concentrated on typing, he can't help but distracted by the flavor of banana milk. He's dream is to become a best programmer in the universe, so he make up his mind to practice his typing speed and the correctness.

The way how Yazmonkey practice is as follow:

He generates a target string that only contains lowercace and upppercase alphabet and space.
After that, he will start typing. He can only type lowercace and upppercase alphabet, space and backspace.

He wants you to write a program to continuously output whether the string he has typed matchs with the prefix of the target string.
At the end, check whether the string he has typed exactly matchs with the target string.

If it matchs correctly, his prize is a carton of banana milk.

hint:
Since the target string may contains space, maybe you need fgets() to input the target string.
Of course using gets() on OJ platform is fine but never use gets() in practice, you can refer to this link for the reason.
The latest revision of the C standard has definitively removed this function from its specification.

Input

First line of the input contains the target string.
Next, each line represents the key Yazmonkey has pressed.
Keep input until Yazmonkey finish typing.
(\b represents backspace)
Guarantee the length of the target string is ≤ 500000 and the number of keys that Yazmonkey will press is ≤ 1000000.

Output

Everytime when Yazmonkey press a key, if the string he has typed so far matchs with the prefix of the target string then output 1, otherwise output 0.

When Yazmonkey finish typing, check whether the string he has typed matches with the target string.
If matches, output "Correct", otherwise output "Incorrect".
Remember to add '\n' at the end of every line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a NxM array, please sort each diagonal line in ascending order from top-left to bottom-right.

For example, given 4x4 array, you should sort these diagonal lines:

This problem is partial judge, you need to implement the function:

// Sort each diagonal line of arr (which size is row x col)

void array2d_sort(int row, int col, long long arr[][500]);

Input

The first line contains two integers, N, M. 

The next N lines contain the array, each element in the array is separated by a space.

1 ≤ N, M ≤ 500

-10¹⁰ ≤ element in the array ≤ 10¹⁰

Output

Output the diagonally sorted array, with each element in the array separated by a space, and print out a newline after each row.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

There is a game called "Number counting game", and it has some rules as following:

1. In the begining, set total sum (shared by two players) to zero and construct a number list which countains integers 1 ~ N.

2. Player A and player B should take turns selecting one number from the number list and adding it to the total sum.

3. Each number only can be selected once.

4. If one of the players make the total sum ≥ K, then he is the winner.

Now, given q rounds, you are asked to output whether the first player can win at each round. (Suppose both two players always select the optimal strategy)

For example, if N=3, and K=5:

The optimal strategy for the first player in the first choice is to select 1 instead of 2 and 3, so the fisrt player will select 1 in the begining. 

[HINT]

To solve this problem, you can try to find all number selection order recursively. Once the total sum ≥ K, you should return and store whether the first player can win with current number selection.

Input

First line countains an integer which denotes q. (1 ≤ q ≤ 10)

Then, q lines follow.

Each line contains two integers N, K which denote the max chosen number and the wining target number respectly.

(2 ≤ N ≤ 20, 2 ≤ K ≤ N(N+1)/2)

Output

Output contains q lines and each line contain the answer(True/False) ended with '\n'. 

Sample Input  Download

Sample Output  Download

Tags

Discuss