Игра в цвета
Вася играет в увлекательную игру. Перед ним расположены несколько кругов с цветными точками, причем на каждом круге одинаковое количество точек. Обратите внимание, что круги расположены по окружности. Все круги пронумерованы от 1 до N, а точки на каждом круге — от 1 до M. Каждая точка окрашена в один из 30 возможных цветов.
В начале игры Вася ставит фишку на первую точку первого круга. Затем он перемещает фишку T раз по следующему алгоритму:
Предположим, что фишка находится на круге C в точке с номером P.
Определим S как количество различных цветов в K-окрестности точки P на круге C, то есть на отрезке [P-K, P+K]. Учтите, что отрезок замкнут по кругу, поэтому после точки M следует точка 1. Например, если M = 6, P = 5, K = 2, то отрезок [P-2, P+2] будет состоять из точек [3, 6] и [1, 1].
Переместите фишку на круг (N-C+1)+S и в точку P+S. Помните, что круги расположены по окружности, и после круга N следует круг 1.
Вася хочет выяснить, на каком круге и в какой точке окажется фишка после всех перемещений.
Рассмотрим пример. Пусть N = 5, M = 4, K = 1. В этом примере используются только два цвета: черный и белый. Пунктирные линии на рисунке обозначают окрестности точек, где находилась фишка.
Изначально C = 1, P = 1. В 1-окрестности присутствуют оба цвета, то есть S = 2. Следовательно, C'= (5-1+1)+2=2, P'=1+2=3. В новой позиции в 1-окрестности присутствует только белый цвет, поэтому S = 1. C"= (5-2+1)+1=5, P"=3+1=4. Наконец, в предпоследней позиции в 1-окрестности присутствуют оба цвета, S = 2, C"'=(5-5+1)+2=3, P"'=4+2=2.
Для данного набора кругов и числа T вам необходимо определить, где окажется фишка после T перемещений.
Обратите внимание, что данные круги имеют особенность: для i = 1,2, ..., N-1 круг i отличается от круга i+1 не более чем в одной точке.
Входные данные
Первая строка содержит четыре числа: N, M, T, K. Вторая строка содержит M целых чисел, представляющих цвета точек на первом круге. Каждый цвет — это целое число от 0 до 29.
Следующие N-1 строк описывают различия между последовательными кругами: строка i содержит пару чисел P_i, Color_{i+1}, указывающих на точку, в которой круги различаются, и цвет этой точки для круга i+1.
1 ≤ N ≤ 50000, 1 ≤ T, M ≤ 100000, 0 ≤ K < M/2.
Выходные данные
Выходной файл должен содержать два числа: номер круга и номер точки — позицию фишки после T перемещений.