1410 - I2P (II) 2018_Yang_Lab1

#	Problem	Pass Rate (passed user / total user)
10245	Spiral Matrix
11830	Play cards 2

10245 - Spiral Matrix

Status | Limits Submit

	Time	Memory
Case 1	1 sec	32 MB
Case 2	1 sec	32 MB
Case 3	1 sec	32 MB
Case 4	1 sec	32 MB

Description

Given two positive integers M and N, construct an M-row, N-column matrix that comprises a sequence of numbers from 1 to M*N arranged in clockwise spiral order. For example, if M = 3 and N = 4, the matrix would be
1 2 3 4
10 11 12 5
9 8 7 6
If M = 4 and N = 4, the matrix would be
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7

Now, given a query integer P (1 <= P <= M*N), you need to print the position of P in the spiral matrix. For example, if M = 4, N = 4, and P = 14, the position of the integer 14 is at the position of row = 2 and column = 3, so the output is

2 3

Input

The input contains three positive integers M N P, where M denotes the number of rows and N denotes the number of columns of the spiral matrix. Both M and N are not greater than 30. P is the query number.

Output

Print two integers that denote the row and column of the position of P. The two integers are separated by a blank. Print a newline at the end of the output.

Sample Input Download

3 4 9

Sample Output Download

3 1

11830 - Play cards 2

Status | Limits Submit

	Time	Memory
Case 1	1 sec	32 MB
Case 2	1 sec	32 MB
Case 3	1 sec	32 MB
Case 4	1 sec	32 MB

Description

Niflheimr is playing cards again!
One day, one of his friends, Ken, suspect that Niflheimr was cheating while shuffling cards. Fortunately, Niflheimr records all the operations he did while shuffling cards, so he wants to undo those operations step by step to find out the original card stack. As an intellegent CS student, let's write a program to help Niflheimr prove his innocence!

Input

First line of input contains two integer n, m, representing # of cards and # of operations.

Next line contains n integers, representing the number on each card from the top (index 0) to the buttom (index n-1) after doing all operations.

Each of the next m lines contains an operation. Operations are in original order.

An operation consists of two integers a and b, meaning Niflheimr moves cards whose index are between a and a+b-1 ( [a, a+b) ) to the top of the card stack. Order of the cards inside the moved part won't be changed.

Index of a card means # of cards on the top of that card. It may change after operations.

It is guaranteed that:

1 ≤ n, m ≤ 10⁴
Number on cards are non-negative integer and do not exceed 10⁷
In each operation, card with index = a+b-1 always exists.

Output

Print out the original card stack from top (index 0) to buttom (index n-1), each number occupies one line.

Sample Input Download

Sample Output Download