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

In this problem, you are asked to implement a program which can find the maximum element M and minimum element mof a two-dimensional array. You need to print the location difference and value difference of M and m. For example, if M is at iM-th row and jM-th column and of value rM, and m is at im-th row and jm-th column and of value rm, then the location difference and value difference of the two elements are (|iM - im| + |jM - jm|) and (|rM - rm|), respectively.

Note that in a given array, no two elements will have the same value.

HINT: You can use C library function:  int abs(int x) ,which returns the absolute value of int x.

Before using abs(), you may need to add the following code at first : #include <stdlib.h>

Input

The first line of the input contains two integer numbers R (2<=R<=10) and C (2<=C<=10).

Each of the next R lines contains C integers, specifying the elements of the two-dimensional array. All of the integers in the same line are separated by a space.

Output

The output contains two integers:  the location difference and the value difference of the maximum and minimum elements, separated by a space.

Note that you do not need to print ‘\n’ at the end of line.

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

The "Mannulus" casino is now celebrating its grand opening in Canterlot! The owner, Lightyear, introduces the cutting-edge technology to the casino : Farseer Cards Auto Detect System. If it works well, the casino will no longer need to employ any dealer!

The question is : the system cannot automatically rank the cards in the correct order. So Lightyear decides to hire a group of programmers to improve the whole system. You, as a beginning programmer, is assigned to write a program to check whether a set of five cards forms a full house or not. Lightyear will then give you T sets of cards to verify the correctness of your program.

Do not disappoint him.

** For someone who doesn't know the definition of full house : https://en.wikipedia.org/wiki/List_of_poker_hands#Full_house

Input

The first line contains an integer T, representing the number of sets Lightyear gives to you.

The next T lines contain 5 cards in each given set, separated by whitespaces.

The cards would range from : {A, 2, 3, 4, 5, 6, 7, 8 ,9 ,10, J, Q, K}.

(In this problem, you don't need to consider the suit of each card.)

• 1 ≤ | T | ≤ 10000

Output

For each set of card, please print 'YES' if the set is a full house, otherwise please print 'NO'.

Remember to print '\n' after each answer.

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

Hey, can I say somthing amazing?  Bacteria touched the air for some reason and begin to widespread in the classroom. The bacteria turned out to be Firmicutes (some kind of bacteria). The classroom can be viewed as a 2D grid map with size R x C. Walls in classroom are denoted as #, clean areas not polluted by Firmicutes are denoted as C, and places where there exist Firmicutes are denoted as F. The classroom is guaranteed to be surrounded by walls. For example a classroom of size 7 x 8 with some area polluted may look like this :

 ########
 #CCC#CC#
 #CFC####
 #CCCCCC#
 #CC#####
 #FCCCCC#
 ########

Firmicutes reproduces rapidly. Initially, some areas in the classroom are polluted by Firmicutes. For every second, if an area is polluted by Firmicutes, the Firmicutes on this area will reproduce themselves and spread to neighboring clean areas. Here, we define neighboring areas of area (r, c) are (r+1, c), (r-1, c), (r, c+1), and (r, c-1). Note that Firmicutes cannot spread onto walls, which means that even if a wall is neighbor to some polluted area, the wall will not be polluted. The following example is a classroom from t = 0 ~ 2 seconds.

Initially, t=0. Some areas are polluted.

 ########
 #CCC#CC#
 #CFC####
 #CCCCCC#
 #CC#####
 #FCCCCC#
 ########

When t=1,

 ########
 #CFC#CC#
 #FFF####
 #CFCCCC#
 #FC#####
 #FFCCCC#
 ########

When t=2,

 ########
 #FFF#CC#
 #FFF####
 #FFFCCC#
 #FF#####
 #FFFCCC#
 ########

Given how the class looks like initially (when t=0) and a time T, please output how the classroom looks like when t=T.

Input

The first line consist of three integers R, C, T, meaning the size of the classroom and a time.

For the following R lines, each line has C characters, being how the classroom looks like initially. Each character will be one of {#, C, F} and the classroom is surrounded by walls (#).

Technical Restrictions

• 3 ≦ R, C ≦ 100

• 0 ≦ T ≦ 100

• The first test case is same as sample IO. It is suggest to use it to check whether your output format is valid.

Output

Please output how the classroom looks like in the T-th second (when t=T).

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Enola's mom leaves Enola a secrete encrypted message! The message seems to be a nonsense combination of lower case alphabets. However, clever Enola soon finds out that the message can be decrypted into a meaningful vocabulary by rearranging the positions of the alphabets. Enola comes up with a vocabulary, can you tell her whether the message can be decrypted into her vocabulary?

Input

The input consists of multiple test case, terminated with EOF (end of file).

On the first line of the test case are two integers n and m, being the length of the encrypted message and the length of a vocabulary.

On the next line are two strings a and b, being the encrypted message and a vocabulary.

• 1 <= n, m <= 1000

• a, b only contains lower case alphabets (i.e. a-z).

Output

For each test case, if a can be decrypted into b by rearranging the positions of alphabets, print "YES" in one line, otherwise print "NO".

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Megumin, a talent explosion magic archwizard, spends a lot of time studying explosion magic spells. For two magic spells A and B, she found that she can combine them together to create a powerful magic spell. Moreover, if the last k characters of A matches the first k characters of B, they can be merged to obtain a more powerful spell. Megumin finds out that the shortest combination of the two spells has maximum power.

For example, if A = "xxxababa" and B = "babayyy", there are severals ways to combine them together:

1. "xxxababababayyy", by simply concatenating A and B, sharing no common characters.

2. "xxxabababayyy", by sharing "ba", the last 2 characters of A and the first 2 characters of B.

3. "xxxababayyy", by sharing "baba", the last 4 characters of A and the first 4 characters of B.

Among all ways of combination, "xxxababayyy" has the maximum power.

Given two magic spells A and B, please output the combination of A and B with maximum power.

Implementation Hints

1. Use strlen() to retrieve length of a string. Remember to #include <string.h>

2. Be careful when using strlen(), or your program might run slowly.

Input

The first line is an integer T, meaning that the input has T test data. Each test data contains a single line.

In each test data, there are two magic spells A and B. Is is guaranteed that A and B only contains lower case alphabets (a-z).

Input consists of two lines. The first line contains A and the second line contains B. It is guaranteed that A and B only contains lower case alphabets (a-z).

• 1 <= T <= 10

• 1 <= |A|, |B| <= 1000

Output

For each test data, please output the answer in one line.  Remember to add new line character ('\n') in the end of each test data.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There’re N banks around the world.
Transactions happen many times every day.
In order to maintain the financial balance, the bank i transfers some money to the bank j once per day.
The amount of transferred money is [ the money of the bank i ] × [ the transfor rate from bank i to bank j ]

Some banks may declare bankrupts because of economic recession.
Let’s say a bank go bankrupt if and only if the money of this bank is less than 10$.
If such situation happens, the bankrupted bank will stop transforing or receiving moneys from any other bank.
Furthermore, the other banks will save the money which should transfor to the bankrupted bank as their own property.

Your task is to compute the amount of money in each bank after T days.

For example:
The transfor rate and the money of each bank are shown in the following tables.
The bank 2 declared a bankrupt on the 3^rd day.
Therefore, the bank 1 stop transforing money to bank 2 after the declaration.

Input

Two numbers N, T on the first line.
The following N lines contains xi per line, denoting the money which bank i has in the begining.
The next N lines consist N numbers for each lines.
There’re r_i1, r_i2, ... , r_iN in the i^th line, representing the transfor rate from bank i to bank j.

It is guaranteed that:

• 1 ≤ N ≤ 500
• 1 ≤ T ≤ 1000
• 10 ≤ xi ≤ 10⁶
• 0.0 ≤ rij ≤ 1.0

Output

There’re N lines in output.
The i^th line contains the amount of money of bank i after T days.
Notice that the amount of money is rounded to 1 decimal places. ( 四捨五入至小數點第1位 )
Remember to print “\n” at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Hey, can I say something amazing? Culturing bacteria is forbidden at school. Your Petri dish(培養皿) will be forfeited if caught by the teachers.

The Petri dishes are placed on the table in a row. Each Petri dish contains a kind of bacteria, labeled with an integer. Two bacteria of the same species will be labeled with the same integer, while two bacteria with different species will be labeled with different integers.

The teacher wants to know that how many species of bacteria he will get if he forfeits the within some range of the table. Given the number of Petri dish N and their species s0, s1, ..., sN-1, the teacher gave you Q queries. For each query, the teacher gave you two integer L and R. You have answer how many species of bacteria there are in range sL, ..., sR.

Input

There are two integers N, Q, begin the number of Petri dish and the number of queries.

The second line are N integers s0, s1, ..., sN-1, being the species of the bacteria.

The following Q lines are queries. Each query occupies a line and contains two integers L and R.

Technical Restrictions

• 1 ≦ N ≦ 1000000

• 1 ≦ Q ≦ 1000000

• 0 ≦ si ≦ 31

• 0 ≦ L ≦ R < N

Test Case Info

1. For the first test case, it is same as sample IO, suggested to use the first test case to check whether your output format is valid.

2. For the test cases from the second to the fifth, you can get an AC by purely by implementing this problem. No additional optimization is required.

3. For the test cases from the sixth to the eighth , some optimization is required. Recall that :

How to estimate the running time of your code?

A usual computer can run 10^9 basic operations (such as +, -, &, |) in 1 second. Although this depends on the judging server, this number serves as a good estimation for the running time of your code. Try to figure out how much operations your code needs to execute to finish all the computations (since not all operations in your code are basic operations, another estimate criterion is 10^8 operations (+, -, *, /, =, ...) in 1 second)!

Output

For each query, please output how many species of bacteria there are in the given range.  Remember to add a new line character after every output.

Explanation of sample IO

For the first query (see orange range), in range [5, 6] there is one bacteria of species 1 and one bacteria of species 0. Since there are two kind of species, output 2. For the second query (see purple range), in range [3, 5] there are two bacteria of species 3 and one bacteria of species 1. Since there are two kind of species, output 2.

Sample Input  Download

Sample Output  Download

Tags

Discuss