E. Хитрый пароль
ограничение по времени на тест
3.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В целях обеспечения секретности доступ к задачам «Russian Code Cup» во время разработки защищен паролем.

Для выбора пароля жюри умеет генерировать специальную таблицу, содержащую n столбцов и бесконечное число строк. Чтобы построить таблицу, первая строка фиксируется, а все остальные получаются по следующему правилу:

В строке i на позиции p ставится число, равное количеству раз, которое встречается a[i - 1][p] на префиксе a[i - 1][1... p].

Для обеспечения требуемого уровня секретности, жюри должно уметь выполнять следующие операции:

  • Изменить число a[1][p] на число v и перестроить таблицу.
  • Найти число a[x][y], которое будет новым паролем.

Делать все эти действия вручную очень утомительно, поэтому жюри просит вас помочь ему. Напишите программу, отвечающую на запросы жюри.

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

Первая строка содержит целое число n (1 ≤ n ≤ 100000) — количество столбцов. Вторая строка содержит описание первой строки таблицы, то есть n чисел, каждое из которых не меньше 1 и не превосходят 109.

Третья строка содержит целое число m (1 ≤ m ≤ 100000) — количество запросов.

Далее каждая строка содержит описание запроса, состоящее из трех чисел:

  • Если первое число равно 1, то оставшиеся два — целые числа v, p (1 ≤ v ≤ 109; 1 ≤ p ≤ n). В этом случае значение v нужно поставить в позицию p в первой строке.
  • Если первое число равно 2, то оставшиеся два — целые числа x, y (1 ≤ x ≤ 105; 1 ≤ y ≤ n) — строка и столбец ячейки таблицы, из которой нужно получить значениe.
Выходные данные

Выведите ответ на каждый запрос второго типа, в порядке поступления запросов.

Примеры
Входные данные
6
1 2 2 2 3 1
3
2 2 3
1 3 3
2 3 4
Выходные данные
2
1