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:

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₁ · p₂ · … · p_n, where p_i are different prime numbers not greater than 47.

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 high-order digit cannot be changed to 0. 0 ≤ b_i ≤ 9.

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