Дерево відрізків
Вам задано масив 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.