Informática Avançado - Semana 74

Teste da Árvore de Segmentos

Lowrenzo está fazendo uma prova e se depara com o seguinte problema:

Você tem um vetor de $N$ elementos $(1 \leq N \leq 10^5)$, indexados de $1$ até $N$.

Existem $M$ $(1 \leq M \leq 500 000)$ operações que você precisa fazer.

Cada operações pode ser de uma das seguintes maneiras:

• $C$ $x$ $v$ - Muda o $x$-ésimo elemento do array para $v$.
• $M$ $l$ $r$ - Imprima o minimo de todos os elementos no intervalo $l$ até $r$, inclusive.
• $G$ $l$ $r$ - Imprima o MDC(Máximo Divisor Comum) de todos os elementos no intervalo $l$ até $r$, inclusive.
• $Q$ $l$ $r$ - Imprima a quantidade de números iguais ao resultado da operação $G$ $l$ $r$ entre todos os elementos no intervalo $l$ até $r$, inclusive.

Todos os elementos no vetor estão entre $1$ e $10^9$. Ajude Lowrenzo a resolver esse problema.

Entrada

A primeira linha da entrada contém dois inteiros $N$ e $M$. Na segunda linha da entrada temos $N$ inteiros, representando o array original. Cada uma das próximas $M$ linhas contém uma das operações que foram explicadas anteriormente.

Saída

Imprima a resposta para todas as operações do tipo $M$, $G$ e $Q$.

Exemplos

ENTRADA	SAÍDA
5 5 1 1 4 2 8 C 2 16 M 2 4 G 2 3 C 2 1 Q 1 5	2 4 2
ENTRADA	SAÍDA
5 2 1 1 2 2 2 Q 1 4 Q 3 5	2 3

Enviar solução: DMOJ