402835: GYM100917 B Battle Mage

Battle mage Va Sya bought a silver plate with form of convex polygon with n vertices to practice his spells.

Then he glued the plate on the thin glass of same form and shape, put this plate as a target and started his practice. Today Va Sya practices a spell which makes a perfect circular hole in the plate itself, but keeps the glass untouched. Note that circles may overlap.

After Va Sya ended up his practice session, he noticed, that all circles from the spells lied inside the plate (but may touch it's edge).

Then he decided to hang the whole construction (glass with remaining parts of silver plate) on the door using selected vertex, so it can rotate freely around this vertex until it is stable.

Find the final coordinates of vertices of the plate, if glass is so thin that its weight must be considered as zero.

First line of the input contains three integers n, c and v (1 ≤ n ≤ 700, 1 ≤ c ≤ 2000, 1 ≤ v ≤ n) — number of vertices in the polygon, number of spells casted by Va Sya and 1-based number of the vertice he used to hang the remaining plate.

i-th of next n lines contains two integers x_i and y_i — coordinates of the i-th vertice ( - 10⁴ ≤ x_i, y_i ≤ 10⁴). Vertices are listed in counterclockwise order.

Each of next c lines contains three integers cx_i, cy_i and r_i — coordinates of center and radius of one circle. It is guaranteed that all circles are non-degenerated and lie inside the polygon (possibly touches it's edge).

Print n lines, i-th of then containing x and y — final coordinates of i-th vertice with absolute error 10^- 5 or less. Vertices must be listed in same order as in the input file.

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

2.253456 -1.176442
4.714949 0.538507
3.000000 3.000000
0.538507 1.285051