Розріджені таблиці

Дуже проста

Обмеження на час виконання 2 секунди

Обмеження на використання пам'яті 128 мегабайтів

Задано масив з $n$ чисел. Потрібно написати програму, яка буде відповідати на запити наступного виду: знайти мінімум на відрізку між $u$ та $v$ включно.

Вхідні дані

У першому рядку задано три натуральних числа $n, m (1 \leq n \leq 1 0^{5}, m \leq 1 0^{7})$ та $a_{1} (1 \leq a_{1} < 16714589)$ — кількість елементів у масиві, кількість запитів і перший елемент масиву відповідно. Другий рядок містить два натуральних числа $u_{1}$ та $v_{1} (1 \leq u_{1}, v_{1} \leq n)$ — перший запит.

Елементи $a_{2}, a_{3}, ..., a_{n}$ задано наступною формулою:

a_{i + 1} = (23 \cdot a_{i} + 21563) m o d 16714589

Наприклад, при $n = 10, a_{1} = 12345$ отримується наступний масив:

a = (12345, 305498, 7048017, 11694653, 1565158, 2591019, 9471233, 570265, 13137658, 1325095)

Запити генеруються наступним чином:

u_{i + 1} = ((17 \cdot u_{i} + 751 + an s_{i} + 2 i) m o d n) + 1

v_{i + 1} = ((13 \cdot v_{i} + 593 + an s_{i} + 5 i) m o d n) + 1

де $an s_{i}$ — відповідь на запит номер $i$ .

Вихідні дані

Вивести $u_{m}, v_{m}$ та $an s_{m}$ (останій запит та відповідь на нього).

Приклади

Вхідні дані #1

Відповідь #1

Відправки 3K

Коефіцієнт прийняття 29%