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