Сергій і масив

Дуже проста

Обмеження на час виконання 1 секунда

Обмеження на використання пам'яті 128 мегабайтів

У Сергія є масив, що складається з $n$ цілих чисел $a_{1}, a_{2}, ..., a_{n}$ . Сергій активний хлопчик, тому зараз він збирається виконати $m$ операцій. Кожна з цих операцій буде одного з трьох наступних видів:

Зробити $v_{i}$ -ий елемент масиву рівним $x_{i}$ . Іншими словами, виконати присвоєння $a_{v_{i}} = x_{i}$ .
Збільшити кожен елемент масиву на $y_{i}$ . Іншими словами, виконати $n$ присвоєнь $a_{i} = a_{i} + y_{i} (1 \leq i \leq n)$ .
Записати на листок $q_{i}$ -ий елемент масиву. Тобто елемент $a_{q_{i}}$ .

Допоможіть Сергію, виконайте всі його операції.

Вхідні дані

У першому рядку записані цілі числа $n, m (1 \leq n, m \leq 1 0^{5})$ . У другому рядку записані $n$ цілих чисел $a_{1}, a_{2}, ..., a_{n} (1 \leq a_{i} \leq 1 0^{9})$ — початковий масив.

Наступні $m$ рядків описують операції, $i$ -ий рядок описує $i$ -у операцію. Перше число в $i$ -му рядку — ціле число $t_{i} (1 \leq t_{i} \leq 3)$ , яке позначає тип операції.

Якщо $t_{i} = 1$ , то далі слідують два цілі числа $v_{i}$ і $x_{i} (1 \leq v_{i} \leq n, 1 \leq x_{i} \leq 1 0^{9})$ .
Якщо $t_{i} = 2$ , то далі слідує ціле число $y_{i} (1 \leq y_{i} \leq 1 0^{4})$ .
Якщо $t_{i} = 3$ , то далі слідує ціле число $q_{i} (1 \leq q_{i} \leq n)$ .

Вихідні дані

Для кожної операції третього типу виведіть значення $a_{q_{i}}$ . Значення виводьте в порядку слідування відповідних запитів у вхідних даних.

Приклади

Вхідні дані #1

Відповідь #1

Вхідні дані #2

Відповідь #2

Відправки 2K

Коефіцієнт прийняття 30%