109. Медиана объединения-2

Дано N упорядоченных по неубыванию последовательностей целых чисел (т.е. каждый следующий элемент больше либо равен предыдущему), в каждой из последовательностей ровно L элементов. Для каждых двух последовательностей выполняют следующую операцию: объединяют их элементы (в объединенной последовательности каждое число будет идти столько раз, сколько раз оно встречалось суммарно в объединяемых последовательностях), упорядочивают их по неубыванию и смотрят, какой элемент в этой последовательности из 2L элементов окажется на месте номер L (этот элемент называют левой медианой).

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

Сначала вводятся числа N и L (2 $\le$ N $\le$ 200, 1 $\le$ L $\le$ 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 $\ge$ 2 $d_i$ = ((a$d_{i–1}$+c) mod m), где mod – операция получения остатка от деления (a$d_{i–1}$+c) на m.

Для всех последовательностей выполнены следующие ограничения: 1 $\le$ m $\le$ 40000, 0 $\le$ a $\lt$ m, 0 $\le$ c $\lt$ m, 0 $\le$ $d_1$ $\lt$ m. Гарантируется, что все члены всех последовательностей по модулю не превышают $10^9$.

В первой строке выведите медиану объединения 1-й и 2-й последовательностей, во второй строке — объединения 1-й и 3-й, и так далее, в (N‑1)-ой строке — объединения 1-й и N-ой последовательностей, далее медиану объединения 2-й и 3-й, 2-й и 4-й, и т.д. до 2-й и N-ой, затем 3-й и 4-й и так далее. В последней строке должна быть выведена медиана объединения (N–1)-й и N-ой последовательностей.

Последовательности, объединения которых мы считаем, таковы:

1 4 7 10 13 16

0 2 5 9 14 20

1 7 16 16 21 22