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.

About the output format, please refer to sample output below, the download of sample output is not correct.

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

Hey, do you want to hear something amazing? llHoerlWdo
Tanaka is a crazy idiot. When she finds a string S, she puts it into a M∗N matrix from top-left to bottom-right, and then swaps two columns for T times.

The method to put S in to a M∗N matrix is like this:

S[0] S[1]   ... S[N-1]
S[N] S[N+1] ... S[2*N-1]
...  ...    ... ...
...  ...    ... ...
S[N*(M-1)]  ... S[N*M-1]

For example,if Tanaka finds a string “HelloWorld”, and puts it into a 2∗5 matrix.
the matrix is:

H e l l o
W o r l d

and then swaps 3 times (1, 3), (2, 5), (2, 4)

Step 1. swap column 1 with column 3

l e H l o
r o W l d

Step 2. swap column 2 with column 5

l o H l e
l d W l o

Step 3. swap column 2 with column 4

l l H o e
r l W d o

Now, you receive the matrix which has been swaped T times from Tanaka.
Can you recover the original string from the swaped array.
If you can, Tanaka may be happy to make friends with you.

Input

There’re three numbers M, N, T on the first line.
The following M lines contains N characters on each line, denoting the matrix after T swaps.
Each characters are separated by whitespace.
And the next T lines consisting of two numbers Ai Bi on each line.
Ai Bi means Tanaka swaped column Ai with column Bi on the i-th swap.

• 1 ≤ M, N, T ≤ 1000
• 1 ≤ Ai, Bi ≤ N
• characters are lowercase or uppercase alphabets
• It’s guaranteed that the matrix is full.

Output

Print the original string S.
Remember ‘\n’ on the end of line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Hey, do you want to hear something amazing?  I saw a Paramecium moving 10 millimeters per second!

The Paramecium is at (0,0) and facing north initially (where north refers to positive direction of y-axis, east refers to positive direction of x-axis). The movement of Paramecium is observed and recorded as the following format :

 t_1 action_1
 t_2 action_2
 ...
 t_n action_n

The i-th of the record means that in the t_i-th second, the Paramecium did action_i. Actions by be either "right-turn"(recorded as 0), "left-turn"(recorded as 1), or "stop"(recored as 2).

For example (Sample I/O) :

• Initially, Paramecium is at (0,0), facing north.

• At 7-th second, Paramecium made a right-turn. At this moment it is at (0, 70), facing east.

• At 12-th second, Paramecium made a left-turn. At this moment it is at (50, 70), facing north.

• At 29-th second, Paramecium made a left-turn. At this moment it is at (50, 240), facing west.

• At 487-th second, Paramecium stopped. At this moment it is at (-4530, 240), facing west.

Given the record, please output the coordinate when the Paramecium stopped.

Input

Input contains multiple lines. Each line has two integer: timestamp t (in seconds) and action a.

It is guaranteed that ...

1. 0 <= t < 100000000

2. a=0 or 1 or 2. a=0 means that the action is a right-turn. a=1 means that the action is a left-turn. a=2 mean that the action is stop.

3. The last line is always a=2 (action = stop) and a=2 will only appear in the last line.

Output

Output two integer x, y, separated with a space between them, with a new line character in the end.

Meaning that the Paramecium stopped in (x,y) finally.

Sample Input  Download

Sample Output  Download

Tags

Discuss