Медіана об'єднань#4042

Медіана об'єднань

2 секунди

64 мегабайти

Середня

Задано $N$ впорядкованих за неспаданням послідовностей цілих чисел (тобто кожен наступний елемент більший або дорівнює попередньому), у кожній з послідовностей рівно $L$ елементів. Для кожних двох послідовностей виконують наступну операцію: об'єднують їх елементи (у об'єднаній послідовності кожне число буде йти стільки разів, скільки разів воно зустрілось сумарно у об'єднуваних послідовностях), впорядковують їх за неспаданням і дивляться, який елемент у цій послідовності з $2 L$ елементів опиниться на місці номер $L$ (цей елемент називають лівою медіаною).

Напишіть програму, яка для кожної пари послідовностей виведе ліву медіану їх об'єднання.

Вхідні дані

Спочатку вводяться числа $N$ та $L$ ( $2 \leq N \leq 200$ 2 \leq N \leq 200, $1 \leq L \leq 50000$ 1 \leq L \leq 50000). У наступних $N$ рядках задано параметри, які визначають послідовності.

Кожна послідовність визначається п'ятьма цілочисельними параметрами: $x_{1}$ x_1, $d_{1}$ d_1, $a$ , $c$ , $m$ . Елементи послідовності обчислюються наступним чином: $x_{1}$ x_1 нам задано, а для усіх $i$ від $2$ до $L$ : $x_{i} = x_{i - 1} + d_{i - 1}$ x_{i} = x_{i-1} + d_{i-1}. Послідовність $d_{i}$ d_i визначається наступним чином: $d_{1}$ d_1 нам задано, а для $i \geq 2$ i \geq 2 $d_{i} = ((a \cdot d_{i - 1} + c) mod m)$ d_i = ((a \cdot d_{i-1} + c) \bmod m), де $mod$ — операція отримання залишку при діленні $a \cdot d_{i - 1} + c$ a\cdot d_{i-1} + c на $m$ .

Для усіх послідовностей виконуються наступні обмеження: $1 \leq m \leq 40000$ 1 \leq m \leq 40000, $0 \leq a < m$ 0 \leq a < m, $0 \leq c < m$ 0 \leq c < m, $0 \leq d_{1} < m$ 0 \leq d_1 < m. Гарантується, що усі члени усіх послідовностей по модулю не перевищують $1 0^{9}$ 10^9.

Вихідні дані

У першому рядку виведіть медіану об'єднання $1$ -ї та $2$ -ї послідовностей, у другому рядку — об'єднання $1$ -ї та $3$ -ї, і так далі, у $(N - 1)$ (N-1)-ому рядку — об'єднання $1$ -ї та $N$ -ої послідовностей, далі медіану об'єднання $2$ -ї та $3$ -ї, $2$ -ї та $4$ -ї, і т.д. до $2$ -ї та $N$ -ої, потім $3$ -ї та $4$ -ї і так далі. У останньому рядку повинна бути виведена медіана об'єднання $(N - 1)$ (N-1)-ї та $N$ -ої послідовностей.

Приклади

Приклад 1