C. Персистентный массив

Дан массив. Обрабатывайте запросы двух видов:

• 1 v i x — создать новую версию из версии $v$, присвоив её $i$-му элементу значение $x$;
• 2 v i — вывести $i$-й элемент версии $v$.

Исходный массив — версия ноль. Каждый запрос первого вида создаёт версию со следующим номером; запросы второго вида версий не создают.

В первой строке — числа $n$ и $q$ ($1 \le n, q \le 2 \cdot 10^5$). Во второй — $n$ чисел исходного массива ($|a_i| \le 10^9$). Далее $q$ запросов; номер версии не превосходит числа уже созданных, $1 \le i \le n$, $|x| \le 10^9$.

На каждый запрос второго вида выведите значение элемента.