An Animal Contest 3 P8 - Monkey Retirement

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Sam the monkey has recently been playing a grid game in his AAC retirement home. Keenan the monkey came to visit him, and Sam showed him his game.

Sam's game is played on a grid with N rows and M columns. Each move, Sam chooses an empty cell and it is filled with the smallest positive integer not present in that row or column.

Sam has been having trouble getting the number Q to appear. Keenan, for some reason, told him that it was easy to achieve Q, so Sam challenged him to get it to appear for the first time on a move between the L^\text{th} and R^\text{th} move inclusive.

Keenan is actually unsure that this is possible, or how to do it, so please help him out.


1 \le N, M \le 500

1 \le Q \le 10^9

1 \le L \le R \le N \times M

Subtask 1 [20%]

L = 1

R = N \times M

Subtask 2 [30%]

L = 1

Subtask 3 [50%]

No additional constraints.

Input Specification

The first and only line of input will contain five space-separated integers, N, M, Q, L, R.

Output Specification

If it is impossible to produce Q between the L^\text{th} and R^\text{th} move inclusive, output -1 on its own line.

Otherwise, output an integer K (L \le K \le R) which is the number of moves you used to achieve Q.

K lines should follow each containing 2 integers i and j, denoting a move at cell (i, j).

If you output an invalid cell, repeat a cell, produce Q before the K^\text{th} move, or do not produce Q on the K^\text{th} move, you will receive WA.

Note: Any valid output will be accepted.

Sample Input

4 4 4 1 16

Sample Output

1 1
2 1
3 1
1 2
1 3
1 4


The moves produce, in order, the values 1, 2, 3, 2, 3, 4.


There are no comments at the moment.