Statements

Одно из главных нововведений новейшей операционной системы 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, включительно

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

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

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

Во второй строке содержатся четыре числа 1 ≤ X₁, A, B, M ≤ 10⁹ + 10. С помощью них можно сгенерировать исходный массив чисел X₁, X₂, ..., X_N. $\text{[math]}$

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

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

cpy a b l "— для операции copy
sum l r "— для операции sum (l ≤ r)
out l r "— для операции print (l ≤ r)

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

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

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

Примеры тестов

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

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

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

1 2 6 1 2 6 
1 2 1 2 2 6 
6
1 1 2 1 2 6 
13

Дан массив из N неотрицательных чисел, строго меньших 10⁹. Вам необходимо ответить на несколько запросов о величине k-й порядковой статистики на отрезке [l, r].

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

Первая строка содержит число N (1 ≤ N ≤ 450 000) — размер массива.

Вторая строка может быть использована для генерации a_i — начальных значений элементов массива. Она содержит три числа a₁, l и m (0 ≤ a₁, l, m < 10⁹); для i от 2 до N

$\text{[math]}$

В частности, 0 ≤ a_i < 10⁹.

Третья строка содержит одно целое число B (1 ≤ B ≤ 1000) — количество групп запросов.

Следующие B строк описывают одну группу запросов. Каждая группа запросов описывается 10 числами. Первое число G обозначает количество запросов в группе. Далее следуют числа x₁, l_x и m_x, затем y₁, l_y и m_y, затем, k₁, l_k и m_k (1 ≤ x₁ ≤ y₁ ≤ N, 1 ≤ k₁ ≤ y₁ - x₁ + 1, 0 ≤ l_x, m_x, l_y, m_y, l_k, m_k < 10⁹). Эти числа используются для генерации вспомогательных последовательностей x_g и y_g, а также параметров запросов i_g, j_g и k_g (1 ≤ g ≤ G)

$\text{[math]}$

Сгенерированные последовательности описывают запросы, g-й запрос состоит в поиске k_g-го по величине числа среди элементов отрезка [i_g, j_g].

Суммарное количество запросов не превосходит 600 000.

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

Выведите единственное число — сумму ответов на запросы.

Примеры тестов

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

5
1 1 1
5
1
1 0 0 3 0 0 2 0 0
1
2 0 0 5 0 0 3 0 0
1
1 0 0 5 0 0 5 0 0
1
3 0 0 3 0 0 1 0 0
1
1 0 0 4 0 0 1 0 0

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

Зима. 2012 год. На фоне грядущего Апокалипсиса и конца света незамеченной прошла новость об очередном прорыве в областях клонирования и снеговиков: клонирования снеговиков. Вы конечно знаете, но мы вам напомним, что снеговик состоит из нуля или более вертикально поставленных друг на друга шаров, а клонирование — это процесс создания идентичной копии (клона).

В местечке Местячково учитель Андрей Сергеевич Учитель купил через интернет-магазин «Интернет-магазин аппаратов клонирования» аппарат для клонирования снеговиков. Теперь дети могут играть и даже играют во дворе в следующую игру. Время от времени один из них выбирает понравившегося снеговика, клонирует его и:

либо добавляет ему сверху один шар;
либо удаляет из него верхний шар (если снеговик не пустой).

Учитель Андрей Сергеевич Учитель записал последовательность действий и теперь хочет узнать суммарную массу всех построенных снеговиков.

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

Первая строка содержит количество действий n (1 ≤ n ≤ 200 000). В строке номер i + 1 содержится описание действия i:

t m — клонировать снеговика номер t (0 ≤ t < i) и добавить сверху шар массой m (0 < m ≤ 1000);
t 0 — клонировать снеговика номер t (0 ≤ t < i) и удалить верхний шар. Гарантируется, что снеговик t не пустой.

В результате действия i, описанного в строке i + 1 создается снеговик номер i. Изначально имеется пустой снеговик с номером ноль.

Все числа во входном файле целые.

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

Выведите суммарную массу построенных снеговиков.

Примеры тестов

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

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

Вася выписал на доске в каком-то порядке все числа от 1 по N, каждое число ровно по одному разу. Иногда он стирает какое-то число и записывает на его место другое. Количество чисел, выписанных Васей, оказалось довольно болшим, поэтому Вася не может окинуть взглядом все числа. Однако ему надо всё-таки представлять эту последовательность, поэтому он написал программу, которая в любой момент отвечает на вопрос — сколько среди чисел, стоящих на позициях с x по y, по величине лежат в интервале от k до l. Сделайте то же самое.

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

В первой строке лежит два натуральных числа — 1 ≤ N ≤ 100 000 — количество чисел, которые выписал Вася и 1 ≤ M ≤ 100 000 — суммарное количество вопросов и изменений сделанных Васей. Во второй строке дано N чисел — последовательность чисел, выписанных Васей. Далее в M строках находятся описания вопросов. Каждый запрос на изменение числа в некоторой позиции начинается со слова SET и имеет вид SET a b (1 ≤ a ≤ N, 1 ≤ b ≤ N). Это означает, что Вася изменил число, записанное в позиции a на число b. Каждый Васин вопрос начинается со слова GET и имеет вид GET x y k l (1 ≤ x ≤ y ≤ N, 1 ≤ k ≤ l ≤ N).

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

Для каждого Васиного вопроса выведите единственное число — ответ на Васин вопрос.

Примеры тестов

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

4 4
1 2 3 4
GET 1 2 2 3
GET 1 3 1 3
SET 1 4
GET 1 3 1 3

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

1
3
2