Вам надано послідовність \(A=(A_1 ,A_2 ,…,A_N )\) довжини \(N\). Дано \(Q\) запитів, обробіть їх усі по порядку.

\(Q\)-й (\(1≤q≤Q\)) запит має один із наступних трьох форматів, який представляє наступні запити:

• 1 \(x_q\) ​ : присвоїти \(x_q\) ​ кожному елементу \(A\).
• 2 \(i_q\) ​  \(x_q\) ​ : додати \(x_q\) ​ до \(A_{i_q}\) ​ .
• 3 \(i_q\) ​ : вивести значення \(A_{i_q}\) ​ ​ .

Обмеження

• \(1≤N≤2×10^5\)
• \(1≤Q≤2×10^5\)
• \(0≤A_i ​ ≤10^9\)  \((1≤i≤N)\)
• Якщо \(q\)-й \((1≤q≤Q)\) запит відповідає другому або третьому формату, \(1≤i_q ≤N\).
• Якщо \(q\)-й (\(1≤q≤Q)\) запит у першому чи другому форматі, \(0≤x_q ​ ≤10^9\) .
• Існує запит у третьому форматі.
• Усі значення у вхідних даних є цілими числами.

Формат вхідних даних

Перший рядок містить ціле число \(N\).

Наступний  рядок містить цілі числа \(A_i\).

Третій рядок містить ціле число \(Q\).

Наступні  \(Q\) рядків містять запити.

Формат вихідних даних

У вихідний потік виведіть \(X\) рядків, де \(X\) — кількість \(q (1≤q≤Q)\), щоб запит \(q\) був у третьому форматі. \(j\)-й \((1≤j≤X)\) рядок має містити відповідь на \(j\)-й такий запит.

Приклад вхідних даних

5
3 1 4 1 5
6
3 2
2 3 4
3 3
1 1
2 3 4
3 3

Приклад вихідних даних

1
8
5

Спочатку A=(3,1,4,1,5). Запити обробляються таким чином:

• \(A_2 ​ =1\), отже, виведіть 1.
• Додайте 4 до \(A_3\) ​, в результаті чого \(A=(3,1,8,1,5)\).
• \(A_3 ​ =8\), тому виведіть 8.
• Присвоїти 1 кожному елементу \(A\), отримаємо \(A\)=(1,1,1,1,1).
• Додайте 4 до \(A_3\) ​, отримаємо \(A\)=(1,1,5,1,1).
• \(A_3 =5\), тому виведіть 5.

Приклад вхідних даних

1
1000000000
8
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
3 1

Приклад вихідних даних

8000000000

Приклад вхідних даних

10
1 8 4 15 7 5 7 5 8 0
20
2 7 0
3 7
3 8
1 7
3 3
2 4 4
2 4 9
2 10 5
1 10
2 4 2
1 10
2 3 1
2 8 11
2 3 14
2 1 9
3 8
3 8
3 1
2 6 5
3 7

Приклад вихідних даних

7
5
7
21
21
19
10