Description

We can encrypt a string into other string.  One method is to put a string into an n×n array first, where n is the smallest number such that n² is equal to or larger than the length of the string.  Each character is put into a cell of the array, from the top left cell of the array and along neighboring cells in the counterclockwise order.  The encrypted string is the output of the row major order.  For example, the input string "Greed is good", whose length is 13, are put into a 4×4 array, as shown in the following figure.

The output string is "Googrd  e  sed i".

If the end of the encrypted string are spaces, don't output them.  For example, the output of "Bass GG" is "B Ga Gss".

Input

The input contains severel test cases. Each test case consists of two lines. The first line contains a positive number n, and the second line contains a string S. The string S should be encrypted by a n*n array. The number of test case is less than 100.

Case 1: the length of S is not more than 16.
Case 2: the length of S is not more than 100.
Case 3: the length of S is not more than 500.
Case 4: the length of S is not more than 1000.

Output

For each test case, output a single line containing the encrypted string.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

S="ABCDEFG...XYZabcdefg...xyz"
Given two intergers M and N, output all different possible sets of N characters from the first M characters in S. Print the sets in ASCII order(i.e. 'A'<'B'<'C'...<'Z'<'a'<'b'...<'z'). Each set should only be printed once, and the elements in the set should also be sorted in ASCII order.

For example, given M=3, N=2, you should output C(3,2)=3 lines, representing different sets of 2 charcters from the set {A,B,C}(first 3 charaters in S). The correct output is:
AB
AC
BC

Note that set {A,B} = {B,A}, thus should only be output once.

Input

The first line of input contains a positive interger T(T<=30), which indicates the number of test case. For the next T lines, each line contains two positive integers M, N (M^N<10^7, M>=N).

case1: 1<=M<=10, 1<=N<=2
case2: 1<=M<=26, 1<=N<=10
case3: 1<=M<=52, 1<=N<=10
case4: 1<=M<=52, 1<=N<=20

Output

For each test case, output all different possible sets of N characters from the first M characters in S. Each set a line, sorted in ASCII order.
Print a blank line after each test case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The words "waterproof" and "proofreading" have a common part "proof", which is the prefix of "proofreading" and the suffix of "waterproof". Given all possible pairs extracted from a list of words, your task is to find the length of the common suffix-prefix of a pair that is the longest one.

For example, if the list consists of "proofreading", "waterproof", and "ingredient", then the answer will be 5, since the common suffix-prefix for the pair of "waterproof" and "proofreading" contains 5 letters and is the longest, in comparison with the common suffix-prefix for the pair of "proofreading" and "ingredient", which is "ing" and has only 3 letters.

Input

The first line is an integer T (T <= 100) denoting the number of test cases. Each case starts with an integer N indicating the number of words. The next N strings are the list of the words for this test case. Each word has at most M letters, all in lower-case.

case 1: 2 <= N <= 10, 1 <= M <= 15
case 2: 2 <= N <= 20, 1 <= M <= 15
case 3: 2 <= N <= 20, 1 <= M <= 30
case 4: 2 <= N <= 30, 1 <= M <= 30

Output

The output should contain T lines for the T cases. Each line shows an integer that represents the longest length of the common part for the best choice of word pair.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Suppose that we have a deck of n(= 2*k) cards, labeled by 1 to n from top to bottom(Like fig.1). A perfect shuffle is a process that divides the cards into equal-sized parts, one with the top k cards, and the other with bottom k cards,, and then re-arranges the card so that the cards of two parts interleave each other; Precisely, the order after a perfect shuffle becomes {k+1, 1, k+2, 2, ..., n, k}(Like fig.2)

We may perform the same shuffling process again and again, so that the order of the cards resumes 1, 2, 3, ..., n.
For example, if n is 4, after the first shuffle we have:
3, 1, 4, 2 (Like fig.3)
Do it again, and the order becomes:
4, 3, 2, 1 (Like fig.4)
The third shuffle yields:
2, 4, 1, 3 (Like fig.5)
And finally, it goes back to:
1, 2, 3, 4 (Like fig.6)

In this question, we are given n as the input, and ask for the minimum number of shuffles (>= 1) to resume the original order.
E.g., n = 2, min num of shuffles = 2.
n = 4, min num of shuffles = 4.
n = 6, min num of shuffles = 3.

Input

The input consists of multiple lines. Each line is a test case, containing a integer n(0 < n <= 1000).

Case 1: n is not more than 10.
Case 2: n is not more than 100.
Case 3: n is not more than 500.
Case 4: n is not more than 1000.

Output

For each case, output the minimum number of shuffles.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input is a permutation of 1, 2, ..., n. For instance, 3, 2, 1. We are provided with a stack, and want to ask if we supply the numbers according to the permutation order, and at each step we can either

(i) get the next number from the supply, and output the number, or
(ii) get the next number from the supply, and push the number to the stack, or
(iii) pop from the stack, and output that number.

Can we obtain the output sequence as 1, 2, 3, ..., n.

So for the case of 3, 2, 1, the answer is YES (we push, push, output, then pop, pop).
Similarly, for the case of 1, 3, 2, the answer is YES, since we output, push, output, pop.
But for 2, 3, 1, the answer is NO.

Hint:
Our strategy could be as follows.
First, we try operation (iii).
If it is invalid, then we try operation (i).
If it cannot produce what we want, try operation (ii).
If we run out of the supply and the stack is not empty. The answer is NO.

Input

There are multiple testcases in the input.
Each case contains two lines. First line contains a positive integer N indicating the length of permutation. The next line contains N distinct numbers (range 1~N) separated by a blank, which describe the given permutation.
The input is terminated by end-of-file (EOF).

Case 1: N <= 10
Case 2: N <= 100
Case 3: N <= 500
Case 4: N <= 1000

Output

For each case, outupt a single line.
If the given permutation can be sorted by a stack, output "YES", otherwise, output "NO".

Sample Input  Download

Sample Output  Download

Tags

Discuss