Вам задано ціле число \(N\) і послідовність \(A=(A_1 ,A_2 ,…,A_N )\) довжини \(N\).

Дано \(Q\) запитів, обробіть їх у заданому порядку. Кожен запит належить до одного з наступних двох видів:

• 1 \(k\) \(x\) : установіть значення \(A_k\) ​ на \(x\).
• 2 \(k\) : вивести значення \(A_k\) ​.

Обмеження

• \(1≤N≤10^5\)
• \(1≤Q≤10^5\)
• \(0≤A_i ​ ≤10^9\)  \((1≤i≤N)\)
• \(1≤k≤N\) для всіх запитів.
• \(0≤x≤10^9\) для всіх запитів першого виду.
• Є принаймні один запит другого виду.
• Усі значення у вхідних даних є цілими числами.

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

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

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

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

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

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

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

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

3
1 3 5
7
2 2
2 3
1 3 0
2 3
1 2 8
2 2
2 1

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

3
5
0
8
1

Спочатку A=(1,3,5).

• Для 1-го запиту A=(1,3,5), де A2 ​ =3, тому має бути виведено 3.
• Для 2-го запиту A=(1,3,5), де A3 ​ =5, тому має бути виведено 5.
• 3-й запит встановлює значення A3 до 0, роблячи A=(1,3,0).
• Для 4-го запиту A=(1,3,0), де A3 ​ =0, тому має бути виведено 0.
• 5-й запит встановлює значення A2 до 8, роблячи A=(1,8,0).
• Для 6-го запиту A=(1,8,0), де A2 ​ =8, тому має бути виведено 8.
• Для 7-го запиту A=(1,8,0), де A1 ​ =1, тому має бути виведено 1.

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

5
22 2 16 7 30
10
1 4 0
1 5 0
2 2
2 3
2 4
2 5
1 4 100
1 5 100
2 3
2 4

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

2
16
0
0
16
100

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

7
478 369 466 343 541 42 165
20
2 1
1 7 729
1 6 61
1 6 838
1 3 319
1 4 317
2 4
1 1 673
1 3 176
1 5 250
1 1 468
2 6
1 7 478
1 5 595
2 6
1 6 599
1 6 505
2 3
2 5
2 1

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

478
317
838
838
176
595
468