eolymp
bolt
Try our new interface for solving problems
Problems

Менеджер памяти

Менеджер памяти

Time limit 10 seconds
Memory limit 512 MiB

Одно из главных нововведений новейшей операционной системы Indows 7 - новый менеджер памяти. Он работает с массивом длины N и позволяет выполнять три самые современные операции:

  • copy(a, b, l) - скопировать отрезок длины [a, a+l-1] в [b, b+l-1];

  • sum(l, r) - посчитать сумму элементов массива на отрезке [l, r];

  • print(l, r) - напечатать элементы с l по r, включительно.

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

Input data

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

Во второй строке содержаться четыре числа 1X_1, A, B, M10^9+10. С помощью них можно сгенерировать исходный массив чисел X_1, X_2, ..., X_N. X_{i+1}=(A*X_i+B) mod M.

Следующая строка входного файла содержит целое число K (1K200000) - количество запросов, которые необходимо выполнить Вашему менеджеру памяти.

Далее в K строках содержится описание запросов. Запросы заданы в формате:

  • cpy a b l - для операции copy;

  • sum l r - для операции sum (lr);

  • out l r - для операции print (lr).

Гарантируется, что суммарная длина запросов print не превышает 3000. Также гарантируется, что все запросы корректны.

Output data

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

Examples

Input example #1
6
1 4 5 7
7
out 1 6
cpy 1 3 2
out 1 6
sum 1 4
cpy 1 2 4
out 1 6
sum 1 6
Output example #1
1 2 6 1 2 6
1 2 1 2 2 6
6
1 1 2 1 2 6
13