题目背景

TL: 10s -> 2s

题目描述

You are given a sequence of positive integers, followed by a number of instructions specifying updates to be made and queries to be answered on the sequence. Updates and queries are given in an arbitrary order.

Each of the updates replaces a single item in the sequence with a given value. Updates are accumulated: all the following instructions are on the sequence after the specified replacement.

Each of the queries specifies a subsequence of the (possibly updated) sequence and the number of items to exclude from that subsequence. One or more sets of integers will result depending on which of the items are excluded. Each of such sets has the greatest common divisor (GCD) of its members. The answer to the query is the least common multiple (LCM) of the GCDs of all these sets.

:::align{center}

Figure H.1. Answering the last query “Q 2 5 2” of the Sample Input 1 :::

输入格式

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

$$\begin{aligned} &n \ m \\ &a_1 \ldots a_n \\ &c_1 \\ &\vdots \\ &c_m \end{aligned}$$

The first line has two integers, $n$ and $m$. $n$ ($1 \le n \le 10^5$) is the length of the integer sequence, and $m$ ($1 \le m \le 10^5$) is the number of instructions. The original integer sequence $a_1, \ldots, a_n$ is given in the second line.

is given in the second line. $1 \le a_i \le 10^6$ holds for $i = 1, \ldots, n$. Each of the following $m$ lines has either an update instruction starting with a letter U, or a query instruction starting with a letter Q.

An update instruction has the following format.

$$\begin{aligned} &\text{U } j \ x \end{aligned}$$

The instruction tells to replace the $j$-th item of the sequence with an integer $x$. $1 \le j \le n$ and $1 \le x \le 10^6$ hold. Updates are accumulated: all the instructions below are on the sequence after the updates.

A query instruction has the following format.

$$\begin{aligned} &\text{Q } l \ r \ k \end{aligned}$$

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

输出格式

No output is required for update instructions. For each of the query instructions, output a line with the LCM of the GCDs of the sets of the items in all the subsequences made by excluding $k$ items from the sequence $b_l, \ldots, b_r$.

5 10
12 10 16 28 15
Q 1 3 1
Q 3 4 0
Q 2 2 0
Q 2 5 2
U 3 21
Q 1 3 1
Q 2 4 1
Q 3 5 1
Q 4 4 0
Q 2 5 2

4
4
10
20
6
14
21
28
210

提示

For the first query of this test case, “Q 1 3 1”, the subsequence is $12\ 10\ 16$. Eliminating a single item results in three item sets, $\{12, 10\}$, $\{12, 16\}$, and $\{10, 16\}$. Their GCDs are $2$, $4$, and $2$, respectively, and thus the output should be their LCM, $4$.

Note that, the update given as the fifth instruction, “U 3 21”, changes the answer to the same query, “Q 1 3 1”, given as the sixth instruction. The update makes the subsequence to $12\ 10\ 21$. Thus the item sets after eliminating a single item are $\{12, 10\}$, $\{12, 21\}$, and $\{10, 21\}$. Their GCDs are $2$, $3$, and $1$, respectively, and thus the output for this query should be their LCM, $6$.