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

Дан массив (вернее, первая, начальная его версия). Нужно уметь отвечать на два запроса:

• a_i[j] = x — создать из i-ой версии новую, в которой j-ый элемент равен x, а остальные элементы такие же, как в i-ой версии.

• get a_i[j] — сказать, чему равен j-ый элемент в i-ой версии.

Входные данные

Количество чисел в массиве n (1 ≤ n ≤ 10^5) и n элементов массива. Далее количество запросов m (1 ≤ m ≤ 10^5) и m запросов. Формат описания запросов можно посмотреть в примере. Если уже существует k версий, новая версия получает номер k+1. И исходные, и новые элементы массива — целые числа от 0 до 10^9. Элементы в массиве нумеруются числами от 1 до n.

Выходные данные

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

Примеры