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

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

Given a series of numbers, e₁, e₂, e₃, ..., e_N.

With these numbers, we want to know what the sum is in some consecutive range.

In every testcase, you will be given M queries.

Each of them contains two integers which represent left bound (L) and right bound (R) respectively.

Your mission is to give the result of e_L + e_L+1 + ... + e_R,

-

Hint 0 : If you get WA for testcase 1, sample input and output might help you.

Hint 1 : If you get TLE for next three testcases, you should think how to decrease some redundant operations for calculations. Try to store other useful information in the array, instead of sum up all the elements for every query! You may search for the problem's title: "prefix sum".

Hint 2 : If you get MLE, you have to reduce the size of array you created and decide what exactly should be in the array.

Input

First line contains one integer N which is the size of elements.

Second line will have N integers representing all elements in the testcase.

Third line contains one integer M which is the number of queries.

For following M lines, each line contains exactly two integers that stand for left bound (L) and right bound (R) respectively.

It is guaranteed that:

1. 10 ≦ N ≦ 1,000,000

2. 0 ≦ e_i ≦ 100,000, for 1 ≦ i ≦ N

3. L must be less than or equal to R, and R won't exceed the size of elements.

Output

For each query, just give the answer in one line.

Also, remember to print '\n' in the end of line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

It's time for PE class to end. But teacher wants to gather everybody to announce something important.

Since the teacher is a nice person, he would like to pick a place which can reduce the moving distance of all students.

Please tell the teacher where it is!

Formally, given some students on an x-y plane, find a lattice point (X, Y), X and Y are integer, which minimize the sum of |X-Xi| + |Y - Yi|, where Xi and Yi is the i-th student's location on x-y plane.

Input

First line contains two integer N and M, representing the boundary of area.

For the next N lines, each contains M integers, representing how many students are at each position.

For example, if the i-th row and the j-th column of these N lines contains an integer X, then it means there are X students at (i, j).

It is guaranteed that N <= 100, M <= 100, there won't be more than 20 students at the same place.

Output

Find out the place where the teacher should gather everybody.

Print two integer, representing which row and column should the teacher pick.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given an N*M grid, does there exist a square of size X*X containing zeros only?

Input

First line contains 3 numbers N, M, X, with the meaning mentioned in problem description.

For the next N lines, each contains M integers which is either 0 or 1.

It is guaranteed that 1 <= N, M <= 120, 1 <= X <= min(N, M).

Output

If there is a square of size X*X, print "YES" (without quotes), otherwise print "NO" (without quotes).

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a string S and a pattern P, please check if the pattern P is contained in the string S.

Examples:

• S = abcdefg, P = abcde => the answer is YES
• S = abcdefg, P = DEF => the answer is NO (DEF != def)
• S = abcdefg, P = qaq => the answer is NO
• S = abcdefg, P = ac => the answer is NO

Input

First line of input is the string S and its length L_s separated by a space.

Second line of input is the pattern P and its length L_p separated by a space.

It is guaranteed that 1 <= L_p <= 500, L_p <= L_s <= 100000.

Output

If the pattern P is contained in the string S, print out "YES" (without quotes); otherwise print "NO" (without quotes).

Sample Input  Download

Sample Output  Download

Tags

Discuss