У Сережи есть массив, состоящий из n целых чисел, a1, a2, ..., an. Сережа — активный мальчик, поэтому сейчас он собирается выполнить m операций. Каждая из этих операций будет иметь один из трех следующих видов:
- Сделать vi-ый элемент массива равным xi. Другими словами, выполнить присвоение avi = xi.
- Увеличить каждый элемент массива на yi. Другими словами, выполнить n присвоений ai = ai + yi (1 ≤ i ≤ n).
- Выписать на листок qi-ый элемент массива. То есть элемент aqi.
Помогите Сереже, выполните все его операции.
Выходные данные
Для каждой операции третьего типа выведите значение aqi. Значения выводите в порядке следования соответствующих запросов во входных данных.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 11
1 2 3 4 5 6 7 8 9 10
3 2
3 9
2 10
3 1
3 10
1 1 10
2 10
2 10
3 1
3 10
3 9
|
2
9
11
20
30
40
39
|