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つずつ出力してください。
例
入力 | 出力 |
6 4
12 8 16 24 36 48
1 2 5
2 4 10
1 1 6
1 3 6 | 4
2
2 |
Constraints
Time limit: 0.8 seconds
Memory limit: 512 MB
Output limit: 1 MB