Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

C. Уильям, Ктолли и Сениориус
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

— Уильям...

— Что случилось?

— Кажется, что-то не так с Сениориусом...

— Я разберусь...

Сениориус изготовлен при помощи соединения специальных талисманов в определённом порядке.

Спустя 500 лет Сениориус находится в плохом состоянии, поэтому Уильям решил полностью его обследовать.

Сениориус сделан из n талисманов, которые Уильям выложил в ряд. На талисмане i написано число ai.

Для того, чтобы починить Сениориус, Уильяму необходимо выполнить m операций, одного из четырёх типов:

  • 1 l r x : Для каждого i такого, что l ≤ i ≤ r, ai становится равным ai + x.
  • 2 l r x : Для каждого i такого, что l ≤ i ≤ r, ai становится равным x.
  • 3 l r x: Вывести x-е по возрастанию число на отрезке [l, r], то есть такое число, которое стояло бы на позиции x в упорядоченном по неубыванию массиве из чисел ai таких, что l ≤ i ≤ r. Гарантируется, что 1 ≤ x ≤ r - l + 1.
  • 4 l r x y : Выведите сумму возведённых в степень x чисел ai таких, что l ≤ i ≤ r по модулю y, то есть .
Входные данные

В первой строке содержатся четыре целых числа n, m, seed, vmax (1 ≤ n, m ≤ 105, 0 ≤ seed < 109 + 7, 1 ≤ vmax ≤ 109).

Тогда тест генерируется следующим псевдокодом:


def rnd():

ret = seed
seed = (seed * 7 + 13) mod 1000000007
return ret

for i = 1 to n:

a[i] = (rnd() mod vmax) + 1

for i = 1 to m:

op = (rnd() mod 4) + 1
l = (rnd() mod n) + 1
r = (rnd() mod n) + 1

if (l > r):
swap(l, r)

if (op == 3):
x = (rnd() mod (r - l + 1)) + 1
else:
x = (rnd() mod vmax) + 1

if (op == 4):
y = (rnd() mod vmax) + 1

Здесь op обозначает тип операции.

Выходные данные

Для каждой операции типа 3 или 4 выведите ответ.

Примеры
Входные данные
10 10 7 9
Выходные данные
2
1
0
3
Входные данные
10 10 9 9
Выходные данные
1
1
3
3
Примечание

В первом тестовом примере исходный массив равен {8, 9, 7, 2, 3, 1, 5, 6, 4, 8}.

Дальнейшие операции таковы:

  • 2 6 7 9
  • 1 3 10 8
  • 4 4 6 2 4
  • 1 4 5 8
  • 2 1 7 1
  • 4 7 9 4 4
  • 1 2 7 9
  • 4 5 8 1 1
  • 2 5 7 5
  • 4 3 10 8 5