Задачі
Persistant Array
Persistant Array
Дан массив (вернее, первая, начальная его версия). Нужно уметь отвечать на два запроса:
\begin{itemize}
\item \textbf{a_i\[j\]} = \textbf{x} --- создать из \textbf{i}-ой версии новую, в которой \textbf{j}-ый элемент равен \textbf{x}, а остальные элементы такие же, как в \textbf{i}-ой версии.
\item \textbf{get a_i\[j\] }--- сказать, чему равен \textbf{j}-ый элемент в \textbf{i}-ой версии.
\end{itemize}
\InputFile
Количество чисел в массиве \textbf{n} (\textbf{1 }≤ \textbf{n }≤ \textbf{10^5}) и \textbf{n }элементов массива. Далее количество запросов \textbf{m }(\textbf{1 }≤ \textbf{m }≤ \textbf{10^5}) и \textbf{m }запросов. Формат описания запросов можно посмотреть в примере. Если уже существует \textbf{k }версий, новая версия получает номер \textbf{k+1}. И исходные, и новые элементы массива --- целые числа от \textbf{0 }до \textbf{10^9}. Элементы в массиве нумеруются числами от \textbf{1 }до \textbf{n}.
\OutputFile
На каждый запрос типа \textbf{get }вывести соответствующий элемент нужного массива.
Вхідні дані #1
6 1 2 3 4 5 6 11 create 1 6 10 create 2 5 8 create 1 5 30 get 1 6 get 1 5 get 2 6 get 2 5 get 3 6 get 3 5 get 4 6 get 4 5
Вихідні дані #1
6 5 10 5 10 8 6 30