e-olymp
Змагання

December 18 - RMQ

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

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

Вхідні дані

У першому рядку задано три натуральних числа n, m (1n105, m107) та a1 (1a1 < 16714589) - кількість елементів у масиві, кількість запитів і перший елемент масиву відповідно. Другий рядок містить два натуральних числа u1 та v1 (1u1, v1n) - перший запит.

Елементи a2, a3, ..., an задано наступною формулою:

ai+1 = (23 * ai + 21563) mod 16714589.

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

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

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

ui+1 = ((17 * ui + 751 + ansi + 2i) mod n) + 1,

vi+1 = ((13 * vi + 593 + ansi + 5i) mod n) + 1,

де ansi - відповідь на запит номер i.

Вихідні дані

Вивести um, vm та ansm (останій запит та відповідь на нього).

Ліміт часу 2 секунд
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
10 8 12345
3 9
Вихідні дані #1
5 3 1565158
Автор В.Гольдштейн
Джерело 2010 Зимние сборы в Харькове, День 2