Задача №3562. Разреженные таблицы
Дан массив из \(n\) чисел. Требуется написать программу, которая будет отвечать на запросы следующего вида: найти минимум на отрезке между \(u\) и \(v\) включительно.
В первой строке входного файла даны три натуральных числа \(n\), \(m\) (\(1 \le n \le 10^{5}\), \(1 \le m \le 10^{7}\)) и \(a_1\) (\(0 \le a_1 < 16\,714\,589\)) — количество элементов в массиве, количество запросов и первый элемент массива соответственно. Вторая строка содержит два натуральных числа \(u_1\) и \(v_1\) (\(1 \le u_1, v_1 \le n\)) — первый запрос.
Элементы \(a_2, a_3, \ldots, a_n\) задаются следующей формулой: \(\) a_{i + 1} = (23 \cdot a_{i} + 21563) \bmod 16714589. \(\)
Например, при \(n = 10\), \(a_1 = 12345\) получается следующий массив: \(a\) = (12345, 305498, 7048017, 11694653, 1565158, 2591019, 9471233, 570265, 13137658, 1325095).
Запросы генерируются следующим образом:
\(v_{i + 1} = \bigl((13 \cdot v_{i} + 593 + ans_{i} + 5i) \bmod n\bigr) + 1\),
В выходной файл выведите \(u_m\), \(v_m\) и \(ans_m\) (последний запрос и ответ на него).
10 8 12345 3 9
5 3 1565158