Задача №113919. Sparse
Дан массив из~\(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\)).
Запросы генерируются следующим образом: \(\)u_{i + 1} = \bigl((17 \cdot u_{i} + 751 + ans_{i} + 2i) \bmod n\bigr) + 1\(\) \(\)v_{i + 1} = \bigl((13 \cdot v_{i} + 593 + ans_{i} + 5i) \bmod n\bigr) + 1\(\) где \(ans_{i}\)~--- ответ на запрос номер \(i\).
Обратите внимание, что \(u_i\) может быть больше, чем \(v_i\).
Формат выходных данных
В выходной файл выведите \(u_m\), \(v_m\) и~\(ans_m\) (последний запрос и~ответ на~него).
Формат входных данных
В~первой строке входного файла даны три натуральных числа \(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\)).
Запросы генерируются следующим образом: \(\)u_{i + 1} = \bigl((17 \cdot u_{i} + 751 + ans_{i} + 2i) \bmod n\bigr) + 1\(\) \(\)v_{i + 1} = \bigl((13 \cdot v_{i} + 593 + ans_{i} + 5i) \bmod n\bigr) + 1\(\) где \(ans_{i}\)~--- ответ на запрос номер \(i\).
Обратите внимание, что \(u_i\) может быть больше, чем \(v_i\).
Формат выходных данных
В выходной файл выведите \(u_m\), \(v_m\) и~\(ans_m\) (последний запрос и~ответ на~него).
Сдать: для сдачи задач необходимо войти в систему