Это интерактивная задача.
В былые времена гномы пытались развить у себя экстрасенсорные способности:
- В абсолютно тёмную пещеру заводили n гномов.
- На каждого гнома надевали шляпу — белую или чёрную. Гномы в пещере не видели цветов своих шляп и шляп других гномов.
- Гномы по очереди выходили из пещеры на поляну и садились на произвольное места. При этом, выходя из пещеры, каждый гном видел цвета шляп всех гномов, вышедших ранее. Тем не менее, он не видит цвет собственной шляпы и никто из других гномов ему этот цвет не сообщает.
- Задача состояла в том, чтобы все гномы разошлись в две стороны — в одну те, кто носят белые шляпы и в другую — чёрные.
За многие века гномы научились безошибочно выбирать для себя место на поляне. Получится ли подобное у вас?
Вас просят по очереди назвать n различных точек на плоскости с целочисленными координатами. После указания очередной точки вам будет сообщён её цвет — чёрный или белый. Ваша задача — добиться того, чтобы названные точки можно было разбить прямой так, чтобы точки одного цвета лежали по одну сторону от прямой, точки разного цвета — по разные стороны и никакие точки не лежали на прямой. Также вы должны предъявить такую прямую.
В данной задаче интерактор является адаптивным — цвета точек в тесте заранее не зафиксированы и программа жюри может выбирать их произвольным образом, в том числе учитывая вывод вашей программы.
Протокол взаимодействия
В первой строке стандартного потока ввода дано целое число n (1 ≤ n ≤ 30) — количество точек, которое должна назвать ваша программа.
Затем n раз ваша программа должна вывести по два целых числа x и y (0 ≤ x ≤ 109, 0 ≤ y ≤ 109) — координаты очередной точки. Все выведенные вами точки должны быть различными.
В ответ на каждую пару координат ваша программа получит на вход строку «black», если точка имеет чёрный цвет, или «white», если точка имеет белый цвет.
После того, как все n точек будут обработаны, вы должны вывести четыре целых числа x1, y1, x2 и y2 (0 ≤ x1, y1 ≤ 109, 0 ≤ x2, y2 ≤ 109) — координаты точек (x1, y1) и (x2, y2), через которые проходит прямая, разделяющая n точек на белые и чёрные. Точки (x1, y1) и (x2, y2) не должны совпадать.
Взломы
Чтобы взломать решение используйте следующий формат. Первая строка теста должна содержать слово «hack», во второй строке выведите целое число n, на третьей строке выведите последовательность из 0 и 1 — цвета точек, которые будут сообщены взламываемому решению. В отличии от тестов жюри, цвета точек во взломах заранее зафиксированы. Разумеется, взламываемое решение не будет заранее знать цвета в взломе.
Например, взлом соответствующий первому тесту из условия выглядит так:
hack
5
0 0 1 1 0
Примечание
В условии в примере взаимодействия вводимые и выводимые данные расположены для удобства восприятия в хронологическом порядке, при реальном взаимодействии никакие «лишние» переводы строк возникать не должны.
Иллюстрация к первому примеру.
