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

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

1 секунда
128 мегабайт
Very easy

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

- a_i[j] = x — Создать новую версию из i-й версии, в которой j-й элемент равен x, а все остальные элементы совпадают с элементами i-й версии. - get a_i[j] — Вывести значение j-го элемента в i-й версии.

Input

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

Output

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

Examples

Example 1

Loading
Loading