Медіана об`єднань
Задано 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-ої послідовностей.