Дан массив (вернее, первая, начальная его версия). Нужно уметь отвечать на два запроса: \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 }вывести соответствующий элемент нужного массива.