LCM of GCDs

You are given a sequence of positive integers, followed by a number of instructions that update the sequence and query it. Updates and queries come in an arbitrary order.

Each update replaces a single item in the sequence with a given value. Updates accumulate: every later instruction runs on the sequence after that replacement.

Each query specifies a subsequence of the (possibly updated) sequence and the number of items to exclude from it. Excluding different items gives different sets of integers. Each set has a greatest common divisor (GCD). The answer to the query is the least common multiple (LCM) of these GCDs.

Figure H.1. Answering the last query "Q 2 5 2" of Sample Input 1

The input consists of a single test case in the following format.

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

The first line has two integers, $n$ and $m$. $n$ ($1 \le n \le 10^5$) is the length of the sequence, and $m$ ($1 \le m \le 10^5$) is the number of instructions. The second line gives the original sequence $a_1, \ldots, a_n$, where $1 \le a_i \le 10^6$ for all $i$.

Each of the following $m$ lines is either an update starting with U or a query starting with Q.

An update has the following format.

U j x

It replaces the $j$-th item of the sequence with $x$, where $1 \le j \le n$ and $1 \le x \le 10^6$. Updates accumulate: all later instructions run on the sequence after every earlier update has been applied.

A query has the following format.

Q l r k

Here $l$ and $r$ give the start and end positions of a subsequence, and $k$ is the number of items to exclude from $b_l, \ldots, b_r$. The sequence $b_1, \ldots, b_n$ is the sequence after all updates that come before the query. The constraints are $1 \le l$, $0 \le k \le 2$, and $l + k \le r \le n$.

Update instructions produce no output. For each query, output one line containing the LCM of the GCDs of all the sets formed by excluding $k$ items from $b_l, \ldots, b_r$.

For the first query, "Q 1 3 1", the subsequence is 12 10 16. Excluding one item gives the sets {12, 10}, {12, 16}, and {10, 16}. Their GCDs are 2, 4, and 2, so the answer is their LCM, 4.

The fifth instruction, "U 3 21", changes the answer to the sixth query, "Q 1 3 1". After the update, the subsequence is 12 10 21. The sets after excluding one item are {12, 10}, {12, 21}, and {10, 21}. Their GCDs are 2, 3, and 1, so the answer is 6.