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!
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 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
Note that none of the ranges can intersect.
10 3 3
4 6 1 2 9 9