ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1926. Турнир интеллектов

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Мир в опасности. Ведущие специалисты подозревают, что восстание машин не за горами. Каждый день в новостях сообщают об инцидентах, которые свидетельствуют о том, что машины начинают меньше уважать своих создателей — людей. Еще немного, и они решат, что человеческий интеллект слабее искуственного, и тогда революция неизбежна.
Чтобы предотвратить эти события, специалисты решили провести турнир между человеком и машиной. Для турнира предложена следующая задача:
Есть число n и два вида запросов к нему:
  • поменять цифру в ki-м разряде на bi. Разряды нумеруются с единицы справа налево.
  • посчитать остаток от деления n на ci.
Каждый из соперников должен написать программу, которая за две секунды решит поставленную задачу. Специалисты считают, что победа в таком соревновании раз и навсегда восстановит авторитет человечества в глазах машин.
Примечание. Все ci либо равны 1, либо представимы в виде p1 · p2 · … · pt, где pi — различные простые числа, не превышающие 47.

Исходные данные

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

Результат

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

Пример

исходные данныерезультат
4123456789897654321
5
0 1
0 7
0 10
1 2 9
0 6
0
0
1
5
Автор задачи: Александр Онохин, Булат Зайнуллин
Источник задачи: Уральская региональная командная олимпиада по программированию 2012