Мир в опасности. Ведущие специалисты подозревают, что восстание машин не за горами. Каждый день в новостях сообщают об инцидентах, которые свидетельствуют о том, что машины начинают меньше уважать своих создателей — людей. Еще немного, и они решат, что человеческий интеллект слабее искуственного, и тогда революция неизбежна.

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

Есть число n и два вида запросов к нему:

Каждый из соперников должен написать программу, которая за две секунды решит поставленную задачу. Специалисты считают, что победа в таком соревновании раз и навсегда восстановит авторитет человечества в глазах машин.

Примечание. Все c_i либо равны 1, либо представимы в виде p₁ · p₂ · … · p_t, где p_i — различные простые числа, не превышающие 47.

В первой строке дано целое чиcло n (1 ≤ n < 10^100 000). Во второй строке дано целое чиcло m — число запросов (1 ≤ m ≤ 10 000). В каждой из следующих m строк вводятся запросы. Запрос на подсчёт остатка имеет вид 0 c_i. Запрос на изменение цифры имеет вид 1 k_i b_i. Гарантируется, что k_i указывает на существующую цифру, а также в процессе изменений старший разряд не обращается в 0. 0 ≤ b_i ≤ 9.

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