eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB

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

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

Вхідні дані

Спочатку вводяться числа N та L (2N200, 1L50000). У наступних 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 нам задано, а для i2d_i = ((a·d_{i-1} + c) mod m), де mod - операція отримання залишку при діленні (a·d_{i-1} + c) на m.

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

Вихідні дані

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

Приклад

Вхідні дані #1
3 6
1 3 1 0 5
0 2 1 1 100
1 6 8 5 11
Вихідні дані #1
7
10
9