GCD의 LCM

양의 정수로 이루어진 수열이 주어지고, 이어서 수열을 갱신하는 명령과 수열에 대해 질의하는 명령이 주어진다. 갱신과 질의는 임의의 순서로 나온다.

각 갱신 명령은 수열의 한 원소를 주어진 값으로 바꾼다. 갱신은 누적되어, 이후의 모든 명령은 그 교체가 반영된 수열에서 수행된다.

각 질의는 (갱신 후의) 수열의 부분 수열과 그 부분 수열에서 제외할 원소의 개수를 지정한다. 제외하는 원소에 따라 서로 다른 정수 집합이 만들어지고, 각 집합에는 최대공약수(GCD)가 있다. 질의의 답은 이 최대공약수들의 최소공배수(LCM)이다.

그림 H.1. 샘플 입력 1의 마지막 질의 "Q 2 5 2"에 답하는 과정

입력은 다음 형식의 테스트 케이스 하나로 이루어진다.

n m
a1 . . . an
c1
.
.
.
cm

첫 줄에는 두 정수 $n$과 $m$이 주어진다. $n$ ($1 \le n \le 10^5$)은 수열의 길이이고, $m$ ($1 \le m \le 10^5$)은 명령의 개수이다. 둘째 줄에는 원래 수열 $a_1, \ldots, a_n$이 주어지며, 모든 $i$에 대해 $1 \le a_i \le 10^6$이다.

이어지는 $m$개의 줄은 각각 U로 시작하는 갱신 명령이거나 Q로 시작하는 질의 명령이다.

갱신 명령의 형식은 다음과 같다.

U j x

수열의 $j$번째 원소를 $x$로 바꾼다. 여기서 $1 \le j \le n$, $1 \le x \le 10^6$이다. 갱신은 누적되며, 이후의 명령은 지금까지의 모든 갱신을 적용한 수열에서 수행된다.

질의 명령의 형식은 다음과 같다.

Q l r k

$l$과 $r$은 부분 수열의 시작 위치와 끝 위치이고, $k$는 $b_l, \ldots, b_r$에서 제외할 원소의 개수이다. 수열 $b_1, \ldots, b_n$은 그 질의 이전의 모든 갱신을 적용한 수열이다. 제약 조건은 $1 \le l$, $0 \le k \le 2$, $l + k \le r \le n$이다.

갱신 명령에는 출력이 없다. 각 질의마다 $b_l, \ldots, b_r$에서 $k$개의 원소를 제외해 만든 모든 집합의 최대공약수들의 최소공배수를 한 줄에 출력한다.

첫 번째 질의 "Q 1 3 1"의 부분 수열은 12 10 16이다. 원소 하나를 제외하면 {12, 10}, {12, 16}, {10, 16} 세 집합이 나오고, 각 최대공약수는 2, 4, 2이다. 따라서 답은 이들의 최소공배수인 4이다.

다섯 번째 명령 "U 3 21"은 여섯 번째 질의 "Q 1 3 1"의 답을 바꾼다. 갱신 후 부분 수열은 12 10 21이 된다. 원소 하나를 제외한 집합은 {12, 10}, {12, 21}, {10, 21}이고, 최대공약수는 2, 3, 1이다. 따라서 이 질의의 답은 6이다.