В Байтландском лесу растет $10^6$ деревьев, расположенных в ряд и пронумерованных от $1$ до $10^6$. На краю леса, прямо перед деревом номер $1$, живет Байтазавр.

Байтазавр решил сесть на диету и начать вести спортивный образ жизни. Он подготовил план на следующие $n$ дней: в $i$-й день он совершит прогулку от дома до дерева номер $a_i$ и обратно, съедая с каждого встреченного дерева ровно $v_i$ листьев, но с каждого дерева только один раз за одну прогулку*.

Изначально Байтазавр амбициозно решил, что $v_i = 0$ для каждого $i$, но быстро понял, что вряд ли выдержит такую голодовку и должен постепенно корректировать количество съедаемых листьев. Байтазавр будет исправлять свой план с помощью $m$ модификаций: $j$-я модификация заключается в увеличении количества съедаемых листьев на значение $w_j$ для первых $p_j$ дней. Иными словами, для каждого $i = 1, 2, \dots, p_j$ значение $v_i$ будет увеличено на $w_j$.

Время от времени, между выполнением модификаций, Байтазавр будет задавать вопросы. Всего он задаст $z$ вопросов, $j$-й из которых будет звучать так: сколько листьев с дерева номер $d_j$ будет съедено Байтазавром суммарно в течение первых $p_j$ дней текущего плана?

Помогите Байтазавру и ответьте на его вопросы.

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

В первой строке входных данных содержатся три целых числа $n, m$ и $z$ ($1 \le n, m, z \le 10^6, n \cdot m \cdot z \le 10^{16}$), обозначающие соответственно: количество дней запланированной диеты Байтазавра, количество модификаций, которые совершит Байтазавр, и количество вопросов, на которые Байтазавру нужны ответы.

Во второй строке находится последовательность из $n$ целых чисел $a_1, \dots, a_n$ ($1 \le a_i \le 10^6$), обозначающих номера деревьев, к которым Байтазавр будет ходить в соответствующие дни плана.

В следующих $m+z$ строках содержатся описания модификаций плана и описания вопросов Байтазавра, по одному описанию в строке: Строка, описывающая $j$-ю модификацию плана, состоит из трех целых чисел $1, p_j, w_j$ ($1 \le p_j \le n, 1 \le w_j \le 10^6$), обозначающих соответственно количество дней и значение, на которое Байтазавр увеличивает количество съедаемых листьев. Строка, описывающая $j$-й вопрос, состоит из трех целых чисел $2, p_j, d_j$ ($1 \le p_j \le n, 1 \le d_j \le 10^6$), обозначающих соответственно количество дней и дерево, для которого нужно посчитать количество съеденных листьев.

Среди этих $m + z$ строк будет ровно $m$ описаний модификаций и ровно $z$ описаний вопросов. Описания даны в хронологическом порядке, то есть при ответе на данный вопрос необходимо учитывать в плане те модификации, которые были выполнены до того, как был задан вопрос (т.е. они даны ранее во входных данных), и не учитывать модификации, которые будут выполнены позже (т.е. они даны позже во входных данных).

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

На выходе должно быть $z$ строк, $j$-я из которых должна содержать ответ на $j$-й вопрос, т.е. количество листьев, которые Байтазавр съест с дерева номер $d_j$ в течение первых $p_j$ дней плана, рассматриваемого Байтазавром в момент задания вопроса.

*Байтазавр придумал, что в одну сторону он будет есть только с деревьев с нечетными номерами, а на обратном пути — только с деревьев с четными номерами. Таким образом он распределяет приемы пищи равномерно по всему маршруту.

Примеры

Пример 1

3 2 4
3 4 1
2 3 1
1 2 10
2 1 2
2 3 1
1 3 1
2 3 2

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

0
10
20
22

Примечание

Пояснение к примеру: План Байтазавра состоит из трех дней ($n = 3$). Байтазавр выполнит $m = 2$ модификации начального плана и задаст $z = 4$ вопроса.

В первый день план предусматривает прогулку к дереву номер $a_1 = 3$, во второй день — к дереву номер $a_2 = 4$, а в третий день — к дереву номер $a_3 = 1$. Изначально $v_1 = v_2 = v_3 = 0$, то есть Байтазавр не планирует есть листья. Затем Байтазавр выполняет модификации и задает вопросы:

• 2 3 1 — Байтазавр спрашивает, сколько листьев он съест за первые 3 дня плана с дерева номер 1 — ответ 0, так как Байтазавр еще не запланировал поедание листьев.
• 1 2 10 — Байтазавр модифицирует план, увеличивая значение $v_i$ для первых 2 дней на 10. После этой модификации имеем: $v_1 = 10, v_2 = 10, v_3 = 0$.
• 2 1 2 — Байтазавр спрашивает, сколько листьев он съест в течение только первого дня плана с дерева номер 2 — ответ 10, так как в первый день во время прогулки к дереву номер $a_1 = 3$ он съест $v_1 = 10$ листьев с дерева номер 2, которое находится по пути.
• 2 3 1 — Байтазавр спрашивает, сколько листьев он съест за первые 3 дня плана с дерева номер 1 — в этот раз ответ 20, так как в первый день он съест $v_1 = 10$ листьев, во второй день съест $v_2 = 10$ листьев, а в третий день съест $v_3 = 0$ листьев.
• 1 3 1 — Байтазавр модифицирует план, увеличивая значение $v_i$ для первых 3 дней на 1. После этой модификации имеем: $v_1 = 11, v_2 = 11, v_3 = 1$.
• 2 3 2 — Байтазавр спрашивает, сколько листьев он съест за первые 3 дня плана с дерева номер 2 — ответ 22, так как в первый день он съест $v_1 = 11$ листьев, во второй день съест $v_2 = 11$ листьев, а в третий день он пойдет на прогулку только к дереву $a_3 = 1$, поэтому дерево 2 он вообще не посетит.

Подзадачи

В следующей таблице запись $a \sim b$ означает $0.99 \cdot b < a \le b$.