ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1632. Лазеры

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Никогда ещё спецагент Иван Охотничий не был так близок к провалу. Казалось, проникнуть в секретную лабораторию через вентиляционный люк на потолке и взломать компьютер не составит труда. Однако сверху Иван заметил, что вся лаборатория пронизана N лазерными лучами, при касании любого из которых включается сигнализация. i-й лазерный луч генерируется излучателем, расположенным в точке (Xi, Yi, Zi), и направлен по вектору (ui, vi, wi). Разглядывая лабораторию из-под потолка, Иван смог определить числа Xi и Yi, а по направлению излучателей вычислить ui, vi и wi. Однако, чтобы разработать дальнейший план действий, просто необходимо знать Z-координаты излучателей.
К счастью, для некоторых пар лазерных лучей Иван смог определить, какой из этих лучей расположен выше другого (то есть, существуют такие X, Y, Z1 и Z2, что точка (X, Y, Z1) лежит на первом луче, точка (X, Y, Z2) лежит на втором луче, и Z1 > Z2). Помогите Ивану найти одно из возможных расположений лазеров в пространстве.

Исходные данные

В первой строке записано целое число N — количество лазеров (1 ≤ N ≤ 100). В каждой из следующих N строк записаны по 5 чисел: Xi, Yi, ui, vi, wi, описывающих i-й лазер. Все координаты целые и не превосходят по модулю 100. В следующей строке записано число M — количество пар лазеров, взаимное расположение которых известно Ивану (0 ≤ M ≤ 10000). Каждая из следующих M строк содержит по два различных целых числа i и j, которые означают, что i-й лазер расположен выше j-го (1 ≤ i, jN). Известно, что ни один лазерный луч не параллелен оси OZ и никакие два лазера не лежат в одной вертикальной плоскости.

Результат

Выведите N вещественных чисел по одному в строке — координаты Zi. Координаты не должны превосходить по модулю 106. Числа следует выводить с максимально возможной точностью. Если возможных ответов несколько, выведите любой. Гарантируется, что хотя бы одно расположение лазеров, удовлетворяющее входным данным, существует.

Пример

исходные данныерезультат
4
0 0 1 0 0
1 0 0 1 0
1 1 -1 0 0
0 1 0 -1 0
3
1 2
2 3
3 4
4.000
3.000
2.000
1.000
Автор задачи: Дмитрий Иванков (подготовка — Алексей Самсонов)
Источник задачи: XIII Открытый командный чемпионат УрГУ по программированию