The Tale of the Priest and His Worker Balda
Once upon a time, a priest and his worker, Balda, decided to play a game. Your task is to assist them by selecting the denominator of a simple fraction. Ideally, the fraction should be irreducible, and for different numerators, such fractions should be as few as possible.
Among all the numbers, only those chosen by the priest can be used. If multiple numbers are suitable, Balda prefers the one with the smallest index. Additionally, Balda may change the numbers in the array as he wishes, so be prepared for this as well.
Input
The first line contains the number of elements in the array N (1 ≤ N ≤ 1,000,000). The next line contains natural numbers, representing the denominators of the fractions, each not exceeding ten million. The array is indexed starting from one. The third line contains the number M (1 ≤ M ≤ 100,000), which indicates how many times the priest and Balda plan to play or modify the array. Following this, there are M lines, each containing three numbers, representing two types of operations: 1 X Y, where 1 ≤ X ≤ Y ≤ N are the boundaries of the segment where the priest and Balda plan to play; or 2 X Z, where the number at index X is changed to 1 ≤ Z ≤ 10,000,000.
Output
For each query of type 1 X Y, output the index of the desired denominator and its value on a separate line.