Поделитесь пирогами
Лунар Роуз — добрая и чистосердечная девушка, родившаяся в тихом городке в день Праздника середины осени. Каждый год на свой день рождения она наслаждается двумя тортами: одним в честь дня рождения и одним в честь праздника.
В этом году Лунар захотела разделить эти торты с Джэдди, своим парнем, в этот особенный день. Однако Джэдди всё испортил:
Когда Лунар поставила два торта на стол, она попросила Джэдди разрезать их так, чтобы каждый получил половину лунного торта и половину торта на день рождения. Но Джэдди, будучи ленивым и импульсивным, просто сделал один разрез, не задумываясь, и хотя оба торта были разрезаны на две части, они оказались неравными. Что ещё хуже, Лунар, будучи перфекционисткой, очень разозлилась на Джэдди за его небрежность и решила расстаться с ним. Бедный Джэдди!
Джэдди очень сожалел о случившемся. Лунар, будучи доброй, не могла видеть его страдания и решила дать ему второй шанс. Однако она поставила жёсткое условие: Джэдди может сделать только один разрез, чтобы разделить оба торта на равные половины. Строгая мисс Роуз!
Оба торта представляют собой выпуклые многоугольники; стол и нож можно считать бесконечной плоскостью и линией. Ваша задача — помочь Джэдди найти линию, которая удовлетворит условию Лунар, чтобы он смог вернуть её расположение.
Входные данные
Первая строка входных данных содержит положительное целое число T (T ≤ 100), обозначающее количество тестов. Далее следуют T тестов. Каждый тест описывает два торта (многоугольника): каждый многоугольник начинается с целого числа n, обозначающего количество вершин, за которым следуют n пар целых чисел (x, y), представляющих координаты вершин в порядке против часовой стрелки. Предполагается, что каждый многоугольник имеет не более 20 вершин, а все координаты находятся в диапазоне от [-1000, 1000]. Кроме того, два многоугольника могут быть разделены линией, не касаясь ни одной из точек линии.
Выходные данные
Для каждого теста выведите два вещественных числа k и b, начиная с номера теста, что означает, что Джэдди должен разрезать торты вдоль линии y=k*x + b. Гарантируется, что и k, и b в ответах находятся в диапазоне от [-10000, 10000]. Любой ответ с относительной или абсолютной ошибкой 10^{-4} считается приемлемым.