Олимпиадный тренинг

Задача . C. Уильям, Ктолли и Сениориус

Задача

Темы: Структуры данных Теория вероятностей *2600

— Уильям...

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

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

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

$\text{[math]}$

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

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

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

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

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

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

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

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


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