Рассмотрим несколько локаций, расположенных в различных целых точках плоскости. Одна из локаций — база, где находятся работники. А в каждой из остальных локаций есть одно задание.

Каждое задание имеет следующие характеристики: длительность выполнения, требуемое количество работников, а также самый ранний момент начала выполнения и самый поздний момент окончания выполнения. Чтобы выполнить задание, нужное количество работников должны одновременно начать его выполнять и непрерывно присутствовать в локации в течение времени, равного длительности выполнения. Каждое задание нужно либо выполнить целиком один раз, либо оставить нетронутым.

Наша задача — определить действия работников так, чтобы получить как можно большую прибыль. Любой работник может участвовать в выполнении любого задания. Мы можем задействовать сколько угодно работников, но каждый должен поучаствовать в выполнении хотя бы одного задания.

Каждый работник в какой-то момент начинает движение на базе, затем перемещается между локациями и выполняет там задания, после чего возвращается на базу и заканчивает движение. Работник может двигаться вдоль координатных осей, и тратит одну минуту на изменение любой одной своей координаты на $$$1$$$ в любую сторону. Работнику нужно заплатить $$$240$$$ кредитов за его появление в нашем решении, а также по $$$1$$$ кредиту за каждую минуту до окончания его движения.

Мы получаем вознаграждение за каждое выполненное задание. Если длительность выполнения задания равна $$$d$$$, а требуемое количество работников равно $$$p$$$, то вознаграждение равно $$$d \cdot p \cdot (p + 5)$$$. Невыполненные задания не влияют на количество кредитов.

Формат входных данных

В первой строке задано целое число $$$n$$$ от $$$500$$$ до $$$2000$$$ — количество локаций. Каждая из следующих $$$n$$$ строк содержит шесть целых чисел и описывает одну локацию в формате $$$x$$$ $$$y$$$ $$$d$$$ $$$p$$$ $$$l$$$ $$$h$$$. Координаты $$$x$$$ и $$$y$$$ — целые числа от $$$0$$$ до $$$100$$$. Длительность выполнения $$$d$$$ — целое число от $$$5$$$ до $$$30$$$ минут. Требуемое количество работников $$$p$$$ — целое число от $$$1$$$ до $$$7$$$ человек. Самый ранний момент начала выполнения $$$l$$$ и самый поздний момент окончания выполнения $$$h$$$ — целые числа от $$$200$$$ до $$$800$$$ минут, причём $$$60 \le h - l \le 300$$$.

Самая первая локация — это база. Её описание — исключение из правил выше, оно имеет формат $$$x$$$ $$$y$$$ $$$0$$$ $$$0$$$ $$$0$$$ $$$0$$$. Все заданные точки $$$(x, y)$$$ различны.

Во всех тестах число $$$n$$$, а также все точки, длительности, количества работников и диапазоны времени выбираются случайно, независимо и равномерно из возможных вариантов.

Формат выходных данных

Выведите инструкции для каждого работника в виде блока из нескольких строк следующего вида:

• start (at-moment) (at-location)

  Первая строка блока. Определяет момент начала движения работника. Локация должна быть базой, то есть иметь номер $$$1$$$.

• arrive (at-moment) (at-location)

  Мы хотим, чтобы работник прибыл в этот момент в эту локацию. Если он не успевает это сделать после предыдущей команды, решение считается неверным. Локации нумеруются с единицы в порядке ввода.

• work (start-moment) (end-moment) (at-location)

  Мы хотим, чтобы работник выполнял задание в этой локации ровно в указанный промежуток времени. Локация должна совпадать с локацией в предыдущей команде прибытия. Если работник не успевает начать выполнение задания после предыдущей команды, или указанный промежуток имеет неправильную длину или не попадает в диапазон времени в локации, решение считается неверным. Эта команда должна присутствовать хотя бы один раз в каждом блоке. Помните, что каждое задание нужно либо выполнить одновременно нужным количеством работников, либо не выполнять вообще, иначе решение будет считаться неверным.

• end

  Последняя строка блока. Работник должен находиться там же, где начал движение.

В каждый момент времени в каждой локации может находиться сколько угодно работников. Все моменты в выводе должны быть целыми числами от $$$0$$$ до $$$1000$$$, все номера локаций — целыми числами от $$$1$$$ до $$$n$$$.

Блоки для различных работников выводите один под другим.

Пример

4
5 15 0 0 0 0
2 13 30 2 200 400
3 12 29 1 350 600
39 21 9 4 671 757

start 335 1
arrive 340 2
work 340 370 2
arrive 372 3
work 372 401 3
arrive 406 1
end
start 335 1
arrive 340 2
work 340 370 2
arrive 375 1
end

Пояснение

Вознаграждение за задание в локации $$$2$$$ равно $$$30 \cdot 2 \cdot (2 + 5) = 420$$$ кредитов.

Вознаграждение за задание в локации $$$3$$$ равно $$$29 \cdot 1 \cdot (1 + 5) = 174$$$ кредита.

Задание в локации $$$4$$$ не выполнено.

Первому работнику нужно заплатить $$$240 + 71 = 311$$$ кредитов.

Второму работнику мы заплатим $$$240 + 40 = 280$$$ кредитов.

Полученная прибыль: $$$420 + 174 - 311 - 280 = 3$$$ кредита.

Заметим, что этот пример слишком короткий ($$$n < 500$$$), так что в проверяющей системе нет такого теста. Пример включён лишь в условие для пояснения.

Система оценки

Каждый тест оценивается отдельно. Оценка за тест равна полученной прибыли, делённой на $$$1000$$$. Если прибыль отрицательна, оценка за тест равна нулю. Если на каком-то тесте решение не выдало корректный ответ, результат на этом тесте также считается равным нулю.

Тестирование

Решения будут проверяться на наборах заранее сгенерированных тестов. Баллы, полученные решением — это сумма результатов на всех тестах. Если на каком-то тесте решение не выдало корректный ответ, результат на этом тесте считается равным нулю.

Во время соревнования есть два способа проверить своё решение в системе.

• Первый — задача A1 — проверка на примерах. Это $$$10$$$ тестов, также доступных участникам для локального тестирования. Как только решение будет проверено, можно посмотреть отчёты на каждом примере, нажав на результат посылки. Тесты для A1 открыты, их можно скачать по ссылкам https://assets.codeforces.com/rounds/1160/codeforces-vrt-2019.tar.gz (для Linux) и https://assets.codeforces.com/rounds/1160/codeforces-vrt-2019.zip (для Windows). После тестирования посылки можно нажать на общий вердикт, чтобы увидеть отдельные результаты на каждом тесте.
• Второй — задача A2 — проверка на предварительных тестах. Это $$$100$$$ тестов, которые сгенерированы заранее, но держатся в секрете. Баллы за предварительные тесты (но не за примеры) используются для построения предварительной таблицы результатов. Результаты на этом этапе не влияют на итоговые результаты, но позволяют примерно сравнить решение с другими.

После окончания соревнования у каждого участника выбирается итоговое решение:

• рассмотрим все решения, посланные для проверки на предварительных тестах;
• выберем те из них, которые получили суммарно строго больше нуля баллов;
• объявим итоговым последнее из таких решений по времени отсылки.

Заметим, что решения, посланные только для проверки на примерах, не влияют на выбор итогового решения.

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