Ray of Light#560
O magic mirror, shining bright!
Reveal your wisdom, show the light,
Share your secret, if you might:
Where to place the source of light?
A student of the Academy of Arcane Optics and Sorcery is conversing with a magic mirror.
On the coordinate plane, there is a square field with vertices at , , (N, N), and . Inside the field, at some interior points with integer coordinates, two-way mirrors are installed. These mirrors are positioned at a 45^\circ angle to the coordinate axes and reflect light. Each point contains at most one mirror, centered exactly at the integer point. There are no mirrors on the boundary. Mirrors come in two types: type mirrors are parallel to the line x + y = 0; type mirrors are parallel to the line x - y = 0. All mirrors have negligible thickness.
At the right boundary, at the point (N, T), is the target to which a light beam should be directed.
Write a program to find an integer-coordinate point on the boundary where a light source can be placed so that a ray, starting there and possibly reflecting off several mirrors, reaches the given target.
The light source cannot be placed at the same position as the target, and its beam must be directed perpendicular to the boundary at that point.
The first line contains three integers: the size of the field , the coordinate of the target , and the number of mirrors (0 < T < N < 500, 0 \leq M \leq (N-1)^2).
The next lines each contain three integers , , —the coordinates of a mirror (0 < x, y < N) and its type ( or ).
Print two integers—the coordinates of a boundary point where the light source should be placed—on the first line. Print the number of times the beam will reflect off mirrors along its path from the source to the target on the second line. If such a point does not exist, print . If there are multiple suitable points, you may output any of them.
Example 1