문제 106
수열의 구간 최솟값과 최대공약수
길이가 $N$인 음이 아닌 정수 수열 $A_0,A_1,\cdots,A_{N-1}$이 주어진다. 수열을 변경하지 않고 다음 $Q$개의 쿼리를 순서대로 처리해 보자.
- $0\ l\ r$: $A_l,A_{l+1},\cdots,A_{r-1}$의 최솟값을 구한다.
- $1\ l\ r$: $A_l,A_{l+1},\cdots,A_{r-1}$의 최대공약수를 구한다.
모든 원소가 $0$인 구간의 최대공약수는 $0$이다.
입력
첫 번째 줄에 두 정수 $N$, $Q$가 공백으로 구분되어 주어진다. $(1 \le N, Q \le 200\,000)$
두 번째 줄에 수열의 원소 $A_0, A_1, \cdots, A_{N-1}$이 공백으로 구분되어 주어진다. $(0 \le A_i \le 10^9)$
세 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리의 종류를 나타내는 정수 $t$와 두 정수 $l$, $r$이 공백으로 구분되어 주어진다. $(t \in \{0, 1\}; 0 \le l < r \le N)$
출력
각 쿼리의 답을 쿼리가 주어진 순서대로 한 줄에 하나씩 출력한다.
예제 입력 1
5 6 12 0 18 6 24 0 0 5 1 0 5 0 2 5 1 2 5 0 1 2 1 1 2
예제 출력 1
0 6 6 6 0 0