XXVI Olimpíada Brasileira de Informática
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:
- alterar o valor de um elemento da sequência S; e
- consultar o número de subsequências candidatas em um dado trecho contíguo de S.
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 Si, 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 ≤ 105
- 1 ≤ M ≤ 105
- 1 ≤ Si ≤ 109, para 1 ≤ i ≤ N
- 1 ≤ I ≤ N
- 1 ≤ V ≤ 109
- 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 |
