Разреженные таблицы

Очень простая

Ограничение по времени выполнения 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 %