В первой строке заданы три натуральных числа n, m (1 ≤ n ≤ 10^5, m ≤ 10^7) и a[1] (1 ≤ a[1] < 16714589) - количество элементов в массиве, количество запросов и первый элемент массива соответственно. Вторая строка содержит два натуральных числа u[1] и v[1] (1 ≤ u[1], v[1] ≤ n) - первый запрос.

Элементы a[2], a[3], ..., a[n] заданы следующей формулой:

a[i+1]= (23 * 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 * u[i] + 751 + ans[i] + 2i) mod n) + 1

v[i+1]= ((13 * v[i] + 593 + ans[i] + 5i) mod n) + 1

где ans[i] - ответ на запрос номер i.