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 k_{i}th position to b_{i}. Positions are numbered from right to left starting from 1.
 calculate a remainder from dividing n by c_{i}.
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.
Note.
Each c_{i} either equals 1 or can be represented as p_{1} · p_{2} · … · p_{n}, where p_{i} are different prime numbers not greater than 47.
Input
The first line of the input contains one integer n (1 ≤ n < 10^{100 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 c_{i}.
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 k_{i} and b_{i}. It is guaranteed that only existing digit can be changed and highorder digit cannot be changed to 0. 0 ≤ b_{i} ≤ 9.
Output
Output one number in a line for every query of type 0.
Sample
input  output 

4123456789897654321
5
0 1
0 7
0 10
1 2 9
0 6
 0
0
1
5

Problem Author: Alexander Onokhin, Bulat Zaynullin
Problem Source: Ural Regional School Programming Contest 2012