\includegraphics{https://static.e-olymp.com/content/d3/d3c8b0eaca8983203b1d303c30016ff1b5b94700.jpg} Решили как-то раз поп и работник его Балда сыграть в игру. Вы должны помочь им, для этого необходимо выбрать знаменатель обыкновенной дроби, но будет лучше, если дробь окажется несократимой, причём при различных числителях таких дробей должно быть наименьшее количество. Среди всех чисел они могут использовать только те, которые выбрал поп, но если подходящих чисел несколько, то Балда хочет именно то число, у которого индекс меньше. Иногда Балда меняет числа в массиве так, как ему захочется, так что предусмотрите и это. \InputFile В первой строке задано количество элементов массива \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{1000000}), в следующей строке через пробелзаданы натуральные числа, знаменатели дроби, причём каждое не превосходит десять миллионов, массив нумеруется с единицы. В третьей строке задано число \textbf{M} (\textbf{1} ≤ \textbf{M} ≤ \textbf{100000}), количество раз, которое они планируют сыграть или изменять массив - поп и его работник Балда, и далее \textbf{M} строк содержат по три числа, строки двух видов: \textbf{1 X Y}, где \textbf{1} ≤ \textbf{X} ≤ \textbf{Y} ≤ \textbf{N} границы отрезка, на котором планируют играть поп и Балда; или \textbf{2 X Z}, где число с индексом \textbf{X }изменяется на \textbf{1} ≤ \textbf{Z} ≤ \textbf{10000000}. \OutputFile Для каждого запроса вида \textbf{1 X Y} в отдельной строке необходимо вывести индекс искомого знаменателя и его значение через пробел.