Range GCD Queries

n個の要素からなる配列と、q個のクエリが与えられます。クエリには2種類あり、1つは指定された区間内の最大公約数（GCD）を計算するもの、もう1つは配列の特定の位置にある要素を更新するものです。これらのクエリを効率的に処理することが求められます。

入力

最初の行には、配列要素数とクエリ数を表す2つの整数 n と q (1 ≤ n, q ≤ 100000) が与えられます。

2行目には、配列の初期状態を表す n 個の整数 (1 ≤ a_i ≤ 10^9) がスペース区切りで並んでいます。

続く q 行には、各クエリが1行に1つずつ指定されています:

• For range GCD queries: The line starts with the number 1 followed by two integers and (), representing the range of indices [] for which the GCD needs to be calculated.

• For array update queries: The line starts with the number 2 followed by two integers and (), representing the index of the element to be updated and its new value .

出力

区間GCDクエリごとに、指定された範囲の要素のGCDを1行に1つずつ出力してください。

例