Задачі
Розріджені таблиці
Розріджені таблиці
Задано масив з $n$ чисел. Потрібно написати програму, яка буде відповідати на запити наступного виду: знайти мінімум на відрізку між $u$ та $v$ включно.
\InputFile
У першому рядку задано три натуральних числа $n, m~(1 \le n \le 10^5, m \le 10^7)$ та $a_1~(1 \le a_1 < 16714589)$ --- кількість елементів у масиві, кількість запитів і перший елемент масиву відповідно. Другий рядок містить два натуральних числа $u_1$ та $v_1~(1 \le u_1, v_1 \le n)$ --- перший запит.
Елементи $a_2, a_3, ..., a_n$ задано наступною формулою:
$$
a_{i+1} = (23 \cdot a_i + 21563)~mod~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 + ans_i + 2i)~mod~n) + 1
$$
$$
v_{i+1} = ((13 \cdot v_i + 593 + ans_i + 5i)~mod~n) + 1
$$
де $ans_i$ --- відповідь на запит номер $i$.
\OutputFile
Вивести $u_m, v_m$ та $ans_m$ (останій запит та відповідь на нього).
Вхідні дані #1
10 8 12345 3 9
Вихідні дані #1
5 3 1565158