Менеджер пам`яті#4310

Менеджер пам`яті

10 секунд

512 мегабайтів

Середня

Одне з головних нововведень найновішої операційної системи Indows 7 - новий менеджер пам'яті. Він працює з масивом довжиною $N$ і дозволяє виконувати три найсучасніші операції:

copy( $a$ , $b$ , $l$ ) - скопіювати відрізок $[a, a + l - 1]$ [a, a+l-1] в $[b, b + l - 1]$ [b, b+l-1];
sum( $l$ , $r$ ) - порахувати суму елементів масиву на відрізку $[l, r]$ [l, r];
print( $l$ , $r$ ) - надрукувати елементи з $l$ по $r$ , включно.

Ви є розробником своєї операційної системи, і Ви, безумовно, не можете обійтись без інноваційних технологій. Вам необхідно реалізувати точно такий самий менеджер пам'яті.

Вхідні дані

Перший рядок вхідного файлу містить ціле число $N$ ( $1 \leq N \leq 1000000$ 1 \leq N \leq 1000000) - розмір масиву, з яким буде працювати Ваш менеджер пам'яті.

У другому рядку містяться чотири числа $1 \leq X_{1}, A, B, M \leq 1 0^{9} + 10$ 1 \leq X_1, A, B, M \leq 10^9+10. З їх допомогою можна згенерувати початковий масив чисел $X_{1}, X_{2}, \dots, X_{N}$ X_1, X_2, \dots, X_N. $X_{i + 1} = (A \cdot X_{i} + B) mod M$ X_{i+1} = (A \cdot X_i + B) \bmod M.

Наступний рядок вхідного файлу містить ціле число $K$ ( $1 \leq K \leq 200000$ 1 \leq K \leq 200000) - кількість запитів, які необхідно виконати Вашому менеджеру пам'яті.

Далі у $K$ рядках містяться описи запитів. Запити задано у форматі:

cpy $a$ $b$ $l$ - для операції copy;
sum $l$ $r$ - для операції sum ( $l \leq r$ l \leq r);
out $l$ $r$ - для операції print ( $l \leq r$ l \leq r).

Гарантується, що сумарна довжина запитів print не перевищує $3000$ . Також гарантується, що усі запити коректні.

Вихідні дані

Для кожного запиту sum або print виведіть у вихідний файл у окремому рядку результат запиту.

Приклади

Приклад 1