ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1926. The Tournament of Intelligences

Time limit: 2.0 second
Memory limit: 64 MB
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.
Note. Each ci either equals 1 or can be represented as p1 · p2 · … · pn, where pi are different prime numbers not greater than 47.

Input

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

Output one number in a line for every query of type 0.

Sample

inputoutput
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