408093: GYM102984 I Selecting Points and Segments

Your task is to select $$$N$$$ points on the coordinate plane and draw $$$M$$$ straight segments connecting them such that there will be exactly $$$K$$$ finite faces. Here, faces are the regions into which the plane is divided by the segments. One of the regions is infinite and should be ignored.

More formally, your configuration must satisfy the following conditions:

• The $$$x$$$ and $$$y$$$ coordinates of each point must be integers from $$$1$$$ to $$$79$$$.
• All points must have different positions.
• There must not be multiple line segments connecting two points.
• Two different line segments must not intersect except at an endpoint.
• Points other than the endpoints of the segment must not be on the segment.

In the figure below, (a) is a case in which one face is created with 3 points and 3 line segments. (b) is a case in which 3 faces are made with 4 points and 6 line segments. (c) is an incorrect output because there are curves, and (d) is incorrect because there are intersecting line segments.

On the first line, there are three positive integers, $$$N$$$, $$$M$$$, and $$$K$$$, representing the number of points, the number of segments, and the number of faces to be created, respectively ($$$3 \leq N \leq 3000$$$, $$$0 \leq M$$$, $$$0 \leq K$$$).

It is guaranteed that, for the given $$$N$$$, $$$M$$$, and $$$K$$$, a solution exists.

On the first $$$N$$$ lines, the print coordinates of selected points. The $$$i$$$-th of those lines must contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le 79$$$): the coordinates of $$$i$$$-th point.

Then print $$$M$$$ lines describing segments. Each of these lines must containin two integers between $$$1$$$ and $$$N$$$: the indices of points connected by a segment.

If there is more than one possible solution, print any one of them.

4 6 3

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

6 5 1

1 1
1 2
2 1
3 1
3 2
4 1
1 2
1 3
2 3
4 5
5 6

The left picture shows 3 faces made with 4 points and 6 line segments.

The right picture shows 1 face made with 6 points and 5 line segments.

{}

{}