Боевой маг Ва 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
