LCC/Moose '20 Contest 4 S2 - Pens and Pencils

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 0.5s
Memory limit: 64M

Problem type

Chris has N pencils in a line, some of which he wants to switch with pens. Chris has an unlimited supply of pens, but can only switch a single continuous segment pencils to pens at a time. Chris wants to end with a line of pencils and pens where there are exactly P disjoint continuous segments of pens and he wants to do exactly Q operations of switching a segment of pencils into pens. Chris wants help on this problem, can you give him a set of segments to switch? He'll accept any valid solution!

Input Specification

The only line of input will consist of 3 space separated integers, N (1 \leq N \leq 10^6), P (1 \leq P \leq 10^5), Q (1 \leq Q \leq 10^5).

Output Specification

Output exactly Q lines of output, consisting of two space separated integers, A_i and B_i, indicating that Chris should switch [A_i, B_i] (1 \leq A_i \leq B_i \leq N) into pens. If this is impossible, output Impossible.

Note that none of the ranges can intersect.

Sample Input

10 3 3

Sample Output

4 6
1 2
9 9


There are no comments at the moment.