Задача E. Игра

Поле для детской игры представляет собой последовательность кружков, первый из которых является стартом, а последний – финишем. На некоторых из кружков указано действие, которое нужно совершить фишке, попавшей на этот кружок: передвинуть фишку на несколько кружков вперед или назад, или сделать еще один ход. Изначально фишки всех K игроков ставятся на старт. Затем они по очереди делают ходы, которые заключаются в следующем. Игрок получает очередное "случайное" число, используя генератор псевдослучайных чисел, описанный ниже, и передвигает свою фишку на столько кружков вперед, какое число он получил (если это число больше количества кружков до финиша, то игрок останавливается на финише). Если на кружке, куда он попал в результате своего хода, написано, что требуется совершить некоторое действие, то игрок совершает это действие. После этого он совершает действие, указанное на кружке, куда он попал в результате предыдущего действия и т. д. до тех пор, пока он не попадет на кружок, на котором не указано никакого действия.

Игра заканчивается, как только фишка одного из игроков достигнет финиша. Этот игрок и считается победителем. Требуется написать программу, которая по описанию поля и по данным параметрам генератора псевдослучайных чисел определит, кто выиграет в данной игре.

Генератор псевдослучайных чисел устроен следующим образом. Его параметрами являются натуральные числа a, b, c и x₀. Генератор порождает последовательность натуральных чисел x₁, x₂, x₃, … по следующему правилу: x_n+1 равно остатку от деления (ax_n + b) на c (при n = 0, 1, 2, …). Для игры используются числа x₁, x₂, x₃, … именно в этом порядке (число x₀ не используется). Все игроки используют общий датчик, то есть, если, например, первый игрок использовал число x₁ и передал ход второму, то тот будет использовать число x₂, а если ему потребуется повторить ход, то x₃ и т. д.

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

В первой строке входного файла записаны числа a, b, c, x₀, описывающие генератор псевдослучайных чисел. Все числа целые неотрицательные и не превосходят 1000; c > 0. В следующей строке записаны числа K – количество игроков и L – количество кружков поля, включая старт и финиш (1 ≤ K, L ≤ 1 000). В следующих L–2 строках записаны команды во втором, третьем, …, L–1-м кружке (в кружках старта и финиша никаких команд нет и при попадании туда ничего делать не нужно). Каждая команда записывается парой чисел.

Если первое число равно единице, то это означает, что нужно сделать дополнительный ход. При этом, если второе число равно T и T > 0, то нужно сделать ход на T кружков вперед, если T < 0 – то на |T| кружков назад, а если T = 0, то нужно снова воспользоваться датчиком псевдослучайных чисел и сделать указанное им количество шагов вперед.

Если первое число равно нулю, то ничего делать не нужно. (Если первое число равно нулю, то второе число также равно нулю.)

Другие значения первое число принимать не может.

Число T целое, и всегда таково, что при соответствующем ходе фишка не окажется за пределами доски (но может оказаться на клетке Старт или Финиш). Если же T = 0 и очередное "случайное" число больше, чем количество кружков до финиша, то фишка останавливается на финише.

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

В выходной файл выведите одно число – номер игрока-победителя. Гарантируется, что одна из фишек обязательно достигнет финиша, причем за время игры будет совершено не более миллиона перемещений (на "случайное" число или число, указанное в кружке).

Примеры

Задача F. Матрица

Дан набор натуральных чисел: a₁, …, a_N. По этому набору строится таблица чисел размером N x N по следующему правилу: в клетку i-го столбца j-й строки записывается большее из чисел a_i и a_j при i ≠ j (если a_i = a_j, то записывается это число); на пересечении i-го столбца и i-й строки записывается число 0.

Дана таблица чисел. Требуется определить, могла ли она быть построена по данным правилам из какого-либо набора чисел a₁, …, a_N.

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

В первой строке входного файла записано натуральное число N – размер таблицы (1 ≤ N ≤ 500). В следующих N строках записано по N чисел – числа соответствующей строки из таблицы (все числа целые неотрицательные и не превосходят 1 000).

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

В единственную строку выходного файла выведите через пробел числа a₁, …, a_N. Если решений несколько, выведите любое из них. Если набора, удовлетворяющего данной таблице, не существует, выведите одно число "-1".

Примеры

Задача G. Точки

Петя и Вася играют в "точки". Петя отметил на клетчатом листе бумаги несколько точек – узлов сетки. Вася хочет окружить их многоугольником так, чтобы все отмеченные узлы лежали строго внутри (не на границе) этого многоугольника и чтобы все стороны этого многоугольника проходили только по сторонам или диагоналям клеток сетки, а его периметр был минимально возможным. Определите, чему равен периметр такого многоугольника.

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

В первой строке входного файла записано число N – количество отмеченных Петей точек (1 ≤ N ≤ 100 000).

В каждой из следующих N строк записаны по два числа x_i, y_i – координаты точек, нарисованных Петей. Координаты по абсолютной величине не превосходят 10⁶. Некоторые точки могут совпадать.

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

Требуется вывести одно число – периметр искомого многоугольника. Ответ нужно вывести с точностью не менее 0.001.

Примеры

Задача H. Автобусы

В столице одной Очень Демократической Страны все жители в 8 часов утра одновременно выходят со станций метро, ближайших к месту своей работы, и дальше добираются до работы на автобусах. Мэр города хочет построить еще одну станцию метро так, чтобы после этого время, к которому все люди доберутся до места своей работы (то есть время, когда последний работник окажется на работе), было наименьшим возможным.

Автобусное сообщение в столице устроено следующим образом. Есть N автобусных остановок, в частности, возле каждой станции метро расположено по остановке. Между N – 1 парой остановок постоянно курсируют автобусы, время движения от одной остановки до другой – 10 минут. Временем ожидания и пересадки можно пренебречь. Автобусное сообщение в столице организовано так, что от любой автобусной остановки до любой другой можно добраться на автобусах (возможно, с пересадками).

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

В первой строке входного файла записаны два числа N и M – количество автобусных остановок и станций метро соответственно (2 ≤ N ≤ 50 000, 1 ≤ M ≤ 1 000, M < N).

Во второй строке записаны через пробел M чисел – номера автобусных остановок, рядом с которыми есть станции метро (каждая – не более одного раза).

В следующих N – 1 строках записано по два числа – номера автобусных остановок, между которыми курсирует автобус. (Автобус ходит в обоих направлениях. Каждый маршрут указан один раз.)

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

В выходной файл выведите одно число – номер автобусной остановки, рядом с которой следует построить новую станцию метро. (Строить можно возле тех автобусных остановок, возле которых еще нет станций метро). Если решений несколько, выведите одно из них.

Примеры