Задачи
Дерево отрезков
Дерево отрезков
Вам дан массив \textbf{A} из \textbf{256} элементов \textbf{a_0}, \textbf{a_1}, ..., \textbf{a_255}, который изначально заполнен нулями. Вам необходимо поддерживать две операции --- изменение на отрезке и нахождение суммы на отрезке. Операция добавления на отрезке имеет вид \textbf{Add(L, R, value)} и означает, что необходимо элементам массива \textbf{a_L}, \textbf{a_\{L+1\}}, ..., \textbf{a_R} добавить \textbf{value}. Операция нахождения суммы на отрезке имеет вид \textbf{Get(L, R)} и должна возвращать сумму \textbf{a_L+a_\{L+1\}+...+a_R}.
Для экономии времени на ввод/вывод первая операция будет представлять собой \textbf{Add(L, R, 1)} с заданными заранее \textbf{L} и \textbf{R}. Каждая следующая операция должна представлять собой \textbf{Add(min(L_new, R_new), max(L_new, R_new), 1)}, где \textbf{L_new} и \textbf{R_new} вычисляются по формулам:
\textbf{L_new = Get(min(L, R), max(L, R)) mod p},
\textbf{R_new = 255 - Get(min(L, R), max(L, R)) mod p}.
где \textbf{mod} - это взятие остатка по модулю.
После каждой такой операции выполняется присваивание \textbf{L = Lnew}, \textbf{R = Rnew}.
\InputFile
В единственной строке входных данных записано четыре целых числа \textbf{q}, \textbf{L}, \textbf{R}, \textbf{p}, где \textbf{q} --- количество операций \textbf{Add}, которые нужно сделать, \textbf{L} и \textbf{R} --- стартовые значения, \textbf{p} --- модуль, по которому нужно брать остатки (\textbf{1} ≤ \textbf{q} ≤ \textbf{5·10^6}, \textbf{0} ≤ \textbf{L} ≤ \textbf{R} ≤ \textbf{255}, \textbf{1} ≤ \textbf{p} ≤ \textbf{125}).
\OutputFile
Выведите \textbf{Get(0, 255)} после последней проведенной операции \textbf{Add}.
Входные данные #1
100 1 1 25
Выходные данные #1
24489