\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} у окремому рядку необхідно вивести індекс шуканого знаменника та його значення через пропуск.