B. Боевой маг
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Боевой маг Ва Cя купил однородную серебряную пластину в форме выпуклого n-угольника в качестве мишени для заклинаний.

Перед тренировкой Ва Ся наклеил пластину на тонкое прочное магическое стекло той же формы и того же размера. Сегодня Ва Ся отрабатывал заклинание, которое пробивает в металлической пластине круглую дыру. При этом стеклянная часть мишени не разрушается. Круги могут иметь разные радиусы и пересекаться.

После того, как Ва Ся закончил тренировку, он обнаружил, что все заклинания попали точно в цель, то есть все дыры находятся внутри пластины (но могут касаться её сторон). Вася решил повесить получившуюся конструкцию (стекло с остатками серебряной пластины) на дверь и закрепил её за одну из вершин так, что конструкция может вращаться вокруг этой вершины свободно до тех пор, пока не придёт в равновесие.

Найдите координаты вершин пластины после того, как конструкция уравновесится, если стекло является настолько тонким, что его вес можно считать равным нулю.

Входные данные

Первая строка входа содержит три целых числа n, c и v (1 ≤ n ≤ 700, 1 ≤ c ≤ 2000, 1 ≤ v ≤ n) — количество вершин пластины, количество заклинаний, направленных Васей на пластину и номер вершины, за которую в итоге пластина будет подвешена на дверь.

i-я из последующих n строк содержит два целых числа xi and yi — координаты i-й вершины. Вершины занумерованы, начиная с единицы, и перечислены в порядке обхода против часовой стрелки, ( - 104 ≤ xi, yi ≤ 104).

Каждая из последующих c строк содержит по три целых числа cxi, cyi и ri — координаты центра круга, вырезанного очередным заклинанием и его радиус. Гарантируется, что все круги являются невырожденными и лежат внутри многоугольника (возможно, касаясь его сторон).

Выходные данные

Выведите n строк, i-я из которых содержит два числа x и y — координаты i-й вершины после уравновешивания всей конструкции с абсолютной погрешностью 10 - 5 или меньше. Вершины должны быть перечислены в том же порядке, в котором они заданы во входном файле.

Пример
Входные данные
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