The world is in danger.
Leading experts believe that the rise of the machines is not far off.
Everyday in the news it is reported about the incidents which indicate
that the machines start to respect humans, their creators, less then before.
It's just about the time they will decide that human intelligence
is weaker than artificial one. In this case a revolution is inevitable.
To prevent these events experts decided to carry out a tournament between
humans and machines. For tournament the following problem was set:
There is a number n and two types of queries:
- change the digit in the ki-th position to bi. Positions are numbered from right to left starting from 1.
- calculate a remainder from dividing n by ci.
Every of the rivals should write a program which in two seconds will solve this problem.
The experts suppose that winning this competition will restore the authority of people
in machines' eyes once and for all.
Each ci either equals 1 or can be represented as p1 · p2 · … · pn, where pi are different prime numbers not greater than 47.
The first line of the input contains one integer n (1 ≤ n < 10100 000).
In the second line you are given one integer m — the number of queries (1 ≤ m ≤ 10 000).
Every of the next m lines contains the description of one query.
The first number in the description is the type of the query. If the type equals 0 then it is the query of calculating a remainder
and the second number in a line will be a positive integer ci.
Otherwise, the type equals 1 and it will be query about changing a digit. In this case the second and the third numbers in the line
will be ki and bi. It is guaranteed that only existing digit can be changed and high-order digit cannot be changed to 0. 0 ≤ bi ≤ 9.
Output one number in a line for every query of type 0.
1 2 9
Problem Author: Alexander Onokhin, Bulat Zaynullin
Problem Source: Ural Regional School Programming Contest 2012