Ray of Light
Light my mirror! Tell
Yes, the whole truth reported
Tell the me a secret,
Set the source of light?
Conversation of a student of the Institute of Precision Optics and Magic with a magic mirror
On the coordinate plate there is a field limited square with vertices (0, 0), (N, 0), (N, N), (0, N). In some interior points of the field with integer coordinates two-way mirrors are established and placed at an angle of 45° to the coordinate axis and reflect light (at each point may be no more than one mirror, which is installed so that its centre coincided with the corresponding period). At the border of mirrors there. Mirrors come in two types: a mirror of the first type parallel to the line x + y = 0, and the second type - direct x – y = 0. All mirrors have a negligible thickness. Examples of reflection ray mirrors of different types are shown in the figures.
Mirror the second type Mirror of the first type
In addition, at the right boundary at the point with coordinates (N, T) is the target that you want to get a beam.
Write a program that finds a point with integer coordinates on the boundary, where you can locate the source of light so that light passing through the field, and perhaps reflected by the multiple mirror belonging to a given target.
The light source can not be located at a single point on a target and should be installed so that it emits a beam was perpendicular to the border at this point.
Input
The first line contains three integers: the size of the field N, the coordinate point with the target T and the number of mirrors on the field of M (0 < T < N < 500, 0 <= M <= (N-1)^2). This is followed by M lines, each of which describes one of the mirror three integers x, y and a, where (x, y) - coordinates of the point at which the mirror is located (0 < x, y < N), a - type of mirror (1 or 2).
Output
In the first line, print out two integers - the coordinates of points on the boundary of the field, which should be a source of light. In the second line print out an integer specifying how many times the beam will be reflected in the mirrors along the path from source to target. If such a point does not exist, output a single number -1. If there are a few points, you can choose any of them.