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