Submeta sua solução

Arquivo:

Linguagem: Selecione C++17 / g++ C17 / gcc Javascript Java / JDK Python 3 / CPython

Submete

Nome do arquivo: candidatas.x, onde x deve ser c, cpp, java, js ou py

Candidatas

Carla é uma biotecnóloga que está investigando proteínas para usar em uma vacina. As proteínas estão codificadas em uma longa sequência de números naturais, que vamos chamar de S.

Através de múltiplos experimentos, Carla determinou que uma subsequência contígua de S é candidata se o máximo divisor comum dos elementos da subsequência é maior do que 1.

Carla quer investigar o número de subsequências candidatas contidas em alguns intervalos contíguos de S, possivelmente também alterando alguns elementos de S. Mais precisamente, durante suas pesquisas ela deseja realizar operações de dois tipos:

1. alterar o valor de um elemento da sequência S; e
2. consultar o número de subsequências candidatas em um dado trecho contíguo de S.

Ajude Carla a realizar suas pesquisas e avançar na busca pela vacina!

Entrada

A primeira linha da entrada contém dois inteiros N e M, indicando respectivamente o número de elementos na sequência S e o número de operações a serem realizadas. A segunda linha contém N inteiros S_i, os elementos da sequência S. Os elementos são identificados por índices de 1 a N. Cada uma das M linhas seguintes descreve uma operação e contém três inteiros. O primeiro inteiro, T, indica o tipo de operação e pode ser 1 ou 2. Se a operação é do tipo 1, os dois números seguintes na linha são I e V, indicando que o elemento de índice I da sequência S deve ter o valor atualizado para V. Se a operação é do tipo 2, os dois números seguintes na linha são E e D, indicando respectivamente o índice do elemento inicial e o índice do elemento final de um intervalo contíguo da sequência S.

Saída

Para cada operação do tipo 2, seu programa deve produzir uma única linha, contendo um único inteiro, o número de subsequências candidatas no intervalo indicado.

Restrições

• 1 ≤ N ≤ 10⁵
• 1 ≤ M ≤ 10⁵
• 1 ≤ S_i ≤ 10⁹, para 1 ≤ i ≤ N
• 1 ≤ I ≤ N
• 1 ≤ V ≤ 10⁹
• 1 ≤ E ≤ D ≤ N

Exemplos

Entrada 5 1 9 3 4 8 1 2 2 5

Saída 4

 

Entrada 4 3 4 4 4 4 2 1 4 1 3 5 2 1 4

Saída 10 5

 

Entrada 5 3 2 3 6 4 1 2 1 4 1 3 1 2 3 5

Saída 6 1