Pool

Billiards, also commonly known as "pool," is a popular game in North America. The game is played on a rectangular table with six pockets — one at each corner and one in the middle of each of the two longer sides. The object of the game is to strike a cue ball so that it collides with other balls, knocking them into the pockets.

The surface of the pool table measures 108″ by 54″. To make computation easier, we place it on the Cartesian plane with its southwest corner at (0, 0) and its northeast corner at (108, 54). The centers of the 6 pockets, numbered 1 through 6, therefore have coordinates (0, 0), (54, 0), (108, 0), (0, 54), (54, 54), and (108, 54), respectively (see Figure 2). The billiard balls are spherical and measure 2″ in diameter.

Figure 2: Diagram of the pool table.

Given the location of the cue ball, a target ball, and a number of other balls on the table, write a program that determines whether a particular shot can be made. The cue ball may be struck in any direction, always travelling in a straight line. Collisions between balls are perfectly elastic, so the target ball always travels in a straight line, away from the point on its surface that the cue ball contacts (see Figure 3).

Figure 3: Diagram of a pool-ball collision.

A shot is considered possible if the cue ball can be struck so that it collides directly with the target ball, which in turn sends the target ball directly into a pocket. Neither ball may collide with any other ball, bounce off the edges of the table (the cushions), or have its center cross the boundary of the table. In other words, no bank shots, combination shots, spin shots, or other trick shots are considered. Note that the difference between the incoming angle of the cue ball and the outgoing angle of the target ball must be greater than 90°. The target ball is considered to have landed in a pocket when its center coincides with the center of that pocket.

You may assume that the cue ball disappears immediately after making contact with the target ball.

The input contains multiple test cases. The first line of each test case contains four real numbers xc yc xt yt, where (xc, yc) is the location of the cue ball and (xt, yt) is the location of the target ball. The second line contains an integer n (0 ≤ n ≤ 14), the number of additional balls on the table, followed by n pairs of real numbers x1 y1 … xn yn, where (xi, yi) is the location of the i-th additional (possibly obstructing) ball. No two balls overlap, and every ball lies strictly in the interior of the table; in particular, all given coordinates satisfy 3 < x < 105 and 3 < y < 51.

The input is terminated by a line containing only the number 0, which should not be processed.

For each test case, output on a single line the number(s) of the pocket(s) into which the target ball can be shot, sorted in ascending order and separated by single spaces. If no clear shot exists, output no shot.