Медиана объединений
Дано N упорядоченных по неубыванию последовательностей целых чисел (т.е. каждый следующий элемент больше либо равен предыдущему), в каждой из последовательностей ровно L элементов. Для каждых двух последовательностей выполняют следующую операцию: объединяют их элементы (в объединённой последовательности каждое число будет идти столько раз, сколько раз оно встретилось суммарно в объединяемых последовательностях), упорядочивают их по неубыванию и смотрят, какой элемент в этой последовательности из 2L элементов окажется на месте номер L (этот элемент называют левой медианой).
Напишите программу, которая для каждой пары последовательностей выведет левую медиану их объединения.
Входные данные
Сначала вводятся числа N и L (2 ≤ N ≤ 200, 1 ≤ L ≤ 50000). В следующих N строках задаются параметры, определяющие последовательности.
Каждая последовательность определяется пятью целочисленными параметрами: x_1, d_1, a, c, m. Элементы последовательности вычисляются следующим образом: x_1 нам задано, а для всех i от 2 до L: x_{i }= x_{i-1} + d_{i-1}. Последовательность d_i определяется следующим образом: d_1 нам задано, а для i ≥ 2 d_i = ((a·d_{i-1} + c) mod m), гдеmod - операция получения остатка от деления (a·d_{i-1} + c) на m.
Для всех последовательностей выполнены следующие ограничения: 1 ≤ m ≤ 40000, 0 ≤ a < m, 0 ≤ c < m,0 ≤ d_1 < m. Гарантируется. что все члены всех последовательностей по модулю не превышают 10^9.
Выходные данные
В первой строке выведите медиану объединения 1-й и 2-й последовательностей, во второй строке - объединения 1-й и 3-й, и так далее, в (N-1)-ой строке - обединения 1-й и N-ой последовательностей, далее медиану объединения 2-й и 3-й, 2-й и 4-й, и т.д. до 2-й и N-ой, затем 3-й и 4-й и так далее. В последней строке должна быть выведена медиана объединения (N-1)-й и N-ой последовательностей.