В целях обеспечения секретности доступ к задачам «Russian Code Cup» во время разработки защищен паролем.
Для выбора пароля жюри умеет генерировать специальную таблицу, содержащую n столбцов и бесконечное число строк. Чтобы построить таблицу, первая строка фиксируется, а все остальные получаются по следующему правилу:
В строке i на позиции p ставится число, равное количеству раз, которое встречается a[i - 1][p] на префиксе a[i - 1][1... p].
Для обеспечения требуемого уровня секретности, жюри должно уметь выполнять следующие операции:
- Изменить число a[1][p] на число v и перестроить таблицу.
- Найти число a[x][y], которое будет новым паролем.
Делать все эти действия вручную очень утомительно, поэтому жюри просит вас помочь ему. Напишите программу, отвечающую на запросы жюри.
Выходные данные
Выведите ответ на каждый запрос второго типа, в порядке поступления запросов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 2 2 2 3 1
3
2 2 3
1 3 3
2 3 4
|
2
1
|