ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Open Ural FU Championship 2011

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. The Island of Märket

Time limit: 1.0 second
Memory limit: 64 MB
Märket is uninhabited island in the Baltic Sea. Historically, the western part of the island belongs to Sweden, while the eastern part belongs to Finland. In 1885, Finns built a lighthouse on the island. There were no clear maps of the island at that time, so later Sweden declared that the lighthouse had been built on its territory. To settle the territorial dispute, Sweden and Finland marked the border on the island so that the areas of the Swedish and Finnish parts were equal and the lighthouse was completely on the Finnish territory.
We assume that Märket is a rectangle on the plane and the lighthouse is a square located strictly inside this rectangle. The sides of the rectangle and of the square are parallel to the coordinate axes. The southwest corner of the island has coordinates (0, 0) and the northeast corner has coordinates (w, h). The border must be a polyline with vertices at points with integer coordinates. The line must connect the north coast with the south coast and its segments must be parallel to the coordinate axes. The line must not have common points with the west or east coasts of the island and must have exactly one common point with the north coast and one common point with the south coast. The border must not cross the lighthouse but can touch it.
Your task is to draw a border between the countries on the island map.


The first line contains the integers w and h, which are the dimensions of the island (3 ≤ w, h ≤ 106; w · h is even). In the second line you are given integers x, y, and d, which are the coordinates of the southwest corner of the lighthouse and the length of a side of the lighthouse (d > 0; 0 < x < wd; 0 < y < hd).


Output the number of vertices of the polyline in the first line. In the following lines output the integer coordinates of the vertices starting from the vertex on the north coast and ending with the vertex on the south coast. The vertical and horizontal segments of the line must alternate; the first and the last segments must be vertical. The lengths of all the segments must be positive. The polyline must not intersect or touch itself. The number of vertices must not exceed 1 000. If there are several ways to draw the border, output any of them. If it is impossible to draw a border satisfying the above conditions, output “Impossible”.


6 3
1 1 1
4 3
4 2
1 2
1 1
4 1
4 0
10 10
1 1 8
Problem Author: Eugene Kurpilyanskiy (idea by Leonid Volkov)
Problem Source: Open Ural FU Championship 2011
To submit the solution for this problem go to the Problem set: 1865. The Island of Märket