Description

Palindrome is a string that is identical to its reverse, like "level" or "aba".  Check whether a given string is a palindrome or not.

Input

The input consists of multiple lines. Each line contains a string. The length of each string is less than 100000.  The number of test case is less than 1000.

Output

For each test case, output "Yes" if it's a palindrome or "No" if it's not a palindrome in a line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Compute C = A × B, where A, B and C are matrices of size n × m, m × p, and n × p, respectivily.

Input

There are multiple (≤50) test cases in each data set.

Each case begins with a line of three integers n, m and p, which denote the dimensions of the matrices defined in the problem description. Each of the following n lines contains m integers a_ij, representing the elements in matrix A, and then m lines of p integers b_ij, representing the elements in matrix B.

There is a blank line between two successive test cases, and the input is terminated by end-of-file.

For data set #1, 1 ≤ n, m, p ≤ 5 and |aij|, |bij| ≤ 30.

For data set #2, 1 ≤ n, m, p ≤ 20 and |aij|, |bij| ≤ 500.

For data set #3, 1 ≤ n, m, p ≤ 50 and |aij|, |bij| ≤ 7000.

For data set #4, 1 ≤ n, m, p ≤ 100 and |aij|, |bij| ≤ 10000.

Output

For each test case, output n lines of p integers representing the elements of matrix C.

Please use single space to seperate two successive elements in the same line, and do not output any leading or trailing space characters.

Also, please output a blank line after each matrix.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a string A and n strings B1, B2, B3, …, Bn, count the number of occurrences of string A in each of B1, B2, B3, … , and print the maximum number of occurrences. All of the strings contain only digits.

For example, if A is “50” , n = 3, and the n strings are

“5005”

“055050”

“55000”

then your answer should be 2 because A appears in “5005”  one time,  in “055050” two times, and in “55000” one  time. So the maximum number of occurrences is 2.

Note that if A is “99” and B1 is “9999”, the number of occurrences of A in B1 is counted as 3.

You may assume string B1 is always longer than string A.

Input

The first line of the input is the string A (0<length of A<=4). The second line is n (1<n<10) .

For the next n lines, each line contains a string Bi (length of A < length of Bi <9) and a ‘\n’ at the end of the line.

Output

The maximum number of occurrences of A appears in B1, B2, …, Bn. Note that you DO NOT need to print ‘\n’ at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Source : ACM International Collegiate Programming Contest Asia Regional Contest, Tsukuba, 2016/10/16 

You are given an ordered sequence of integers, (1,2,3,...,n). Then, a number of requests will be given. Each request specifes an integer in the sequence. You need to move the specied integer to the head of the sequence, leaving the order of the rest untouched. Your task is to find the order of the elements in the sequence after following all the requests successively.

Sample Output Explanation : In Sample Input 1, the initial sequence is (1; 2; 3; 4; 5). The first request is to move the integer 4 to the head, that is, to change the sequence to (4; 1; 2; 3; 5). The next request to move the integer 2 to the head makes the sequence (2; 4; 1; 3; 5). Finally, 5 is moved to the head, resulting in (5; 2; 4; 1; 3).

Input

The input consists of a single test case of the following form.

n m

e₁

:

e_m

The integer n is the length of the sequence ( 1 <= n <= 200000 ). The integer m is the number of requests ( 1 <= m <= 100000 ). The following m lines are the requests, namely e₁,...,e_m, one per line. Each request e_i ( 1 <= i <= m ) is an integer between 1 and n, inclusive, designating the element to move. Note that, the integers designate the integers themselves to move, not their positions in the sequence.

Output

Output the sequence after processing all the requests. Its elements are to be output, one per line, in the order in the sequence.

There should be a new line at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

SunMoon likes spiral(漩渦). On the N*N’s space, he starts moving into the left top corner, (0,0), and walking right for totally N steps (including the first movement into (0,0)). He then walks down for N-1 steps, then walks left for N-2 steps and then walks up for N-3 steps… until no more steps are possible. When he walks across that space, he will draw '#' on the floor. The others that he doesn’t pass will be  ‘ ‘. Please tell SunMoon what the resulting spiral(漩渦) looks like.

Input

There is a positive number T(1 <= T <= 1000). It means that there are T numbers.

In next T lines, each line contains a positive number N(1 <= N <= 5000)，which is the size of the space.

Output

Please show the resulting spiral(漩渦).

Note: The first step is to enter (0,0), and the second step is to enter (0,1)…and so on.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

    SunMoon is playing a game, he has to control the character to dodge the enemy’s attack. However, the enemy’s attack speed is so fast that as long as he is in the attack range, he will be hurt immediately. To prevent this situation, he will make every effort to avoid being in the enemy’s attack range.

    You can think of the character as a rectangle that it’s four edges are parallel to the x-axis and y-axis. The enemy’s attack range is also a rectangle that it’s four edges are parallel to the x, y-axis. If the character and the enemy’s attack range has a cross (that is, the area of the intersection of the two rectangle is greater than 0), the character will be attacked, otherwise he will be safe.

    Since playing the game is too complicated, SunMoon want to design an Al to help him play the game, please help him determine whether the role will be attacked or not.

Input

   There is an integer T in the first line (1 <= T <= 1000000), meaning that it will ask T times. Next, following T lines, each lines contain eight numbers Ax0, Ay0, Ax1, Ay1, Bx0, By0, Bx1, By1.

    For the rectangle of SunMoon’s character, its left-down coordinate is (Ax0, Ay0) and right-top coordinate is (Ax1, Ay1). For the rectangle of enemy’s attack range, its left-down coordinate is (Bx0, By0) and right-top coordinate is (Bx1, By1)

    It is guaranteed that Ax0<Ax1, Ay0<Ay1, Bx0<BX1, By0<By1, and Ax0, Ay0, Ax1, Ay1, Bx0, By0, Bx1, By1 are all in the range of int.

Output

    For every ask, please tell SunMoon weather his character will be attacked or not. If he will be attack, please output “BOY NEXT DOOR,DEEP DARK FANTASY” without the quotation marks. Otherwise, please output “Do you like WHAT YOU SEE,ASS WE CAN”, also without the quotation marks.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Determine the positions of each letter in a given string (with length < 1000001). Then output the positions of each letters in lexicographical order. For each letter, output its positions in increasing order. 

For example, “AbAABBCAaa”

A is at position 0, 2, 3, 7; B is at position 4, 5; C is at position 6; a is at position 8, 9; b is at position 1.

Input

There is only one row, and it is a string S with length smaller than 1000001. 

Output

Please output the answer according to the above requirements, and remember to add ‘\n’ at the end of the outcome of every letter.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

American‧SHENGDIYAGE is a global influential company.
Now, you have a chance to visit its factory. The factory is constitute by N*M spaces. The left top space is (0,0) and the right down is ( N-1, M-1).
First, you are located at (0,0), and then company's president will give you some instructions you should follow. There are four kinds of instructions that are represented by 1,2,3,4:

・1 means to go up .
    If you at (1,2), then u will go to (0,2)
・2 means to go down .
    If you at (1,2), then u will go to (2,2)
・3 means to go left .
    If you at (1,2), then u will go to (1,1)
・4 means to go right .
    If you at (1,2), then u will go to (1,3)

But sometimes the president will give wrong instructions such as asking you to walk to boundary. When you get a wrong instruction , you have to stop at the same position, waiting for his next instruction.
After visiting, you want to know how many times you have passed each space(The number of times of each space will increase by one each time you pass the space), and you also want to know the number of wrong instructions that the president have said.

Input

There are 2 integers N,M in the first line. N, M <= 1000, which means there are N*M spaces in the factory.
The next number, K, means there are K instructions.Then the next line contains K instructions given by President.

Output

Output an integer in the first line indicating the number of wrong instructions given by President. Then output N*M numbers to represent the times you have passed each space.

Sample Input  Download

Sample Output  Download

Tags

Discuss