eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

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

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

Лимит времени 2 секунды
Лимит использования памяти 128 MiB

Дан массив из n чисел. Требуется написать программу, которая будет отвечать на запросы следующего вида: найти минимум на отрезке между u и v включительно.

Входные данные

В первой строке заданы три натуральных числа 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.

Выходные данные

Вывести u_m, v_m и ans_m (последний запрос и ответ на него).

Пример

Входные данные #1
10 8 12345
3 9
Выходные данные #1
5 3 1565158
Автор В.Гольдштейн
Источник 2010 Зимние сборы в Харькове, День 2