Fatores Primos Distintos

Seja $n$ um número natural. A função $\omega(n)$ corresponde ao número de fatores primos distintos que dividem $n$. Por exemplo, $\omega(6) = 2$, pois $6 = 2\times 3$, e $\omega(120) = 3$, pois $120 = 2^2\times 3\times 5$.

Dados $N$ inteiros positivos $a_1, a_2, \ldots, a_N$, processe $Q$ comandos, de um dos dois tipos abaixo:

• $1\ i\ v$: adicione $v$ unidades ao $i$-ésimo elemento;
• $2\ i\ j$: retorne o elemento intervalo $[a_i, a_{i + 1}, \ldots, a_{j-1}, a_j]$ para o qual a função $\omega$ tem valor máximo. Se dois ou mais valores atingirem este máximo, retorne o maior dentre eles. Caso persista o empate, retorne o de menor índice.

Entrada

A primeira linha da entrada contém o valor de $N$ ($1\leq N\leq 2\times 10^5$).

A segunda linha contém $N$ inteiros $a_i$ ($1\leq a_i\leq 10^6, 1\leq i\leq N$), separados por um espaço em branco.

A terceira linha contém o inteiro $Q$ ($1\leq Q\leq 2\times 10^5$), que indica o número de comandos a serem processados.

As $Q$ linhas seguintes contém, cada uma, um comando válido: ou a sequência $1\ i\ v$ ($1\leq i\leq N, 1\leq v\leq 10$), ou a sequência $2\ i\ j$ ($1\leq i\leq j\leq N$).

Saída

Para cada comando que inicia com o número $2$ imprima, em uma linha, a mensagem “#$c$: $j$ $a_j$ $\omega(a_j)$”, onde $c$ é o número do comando processado (cuja contagem tem início com o número um), $j$ é o índice do elemento que maximiza a função $\omega$, $a_j$ é o valor do elemento e $\omega(a_j)$ é o número de primos distintos que dividem este número.

Exemplo de entrada 1

3
6 8 10
5
2 1 2
2 1 3
1 3 1
2 1 3
2 2 2

Exemplo de saída 1

#1: 1 6 2
#2: 3 10 2
#3: 1 6 2
#4: 2 8 1

Explicação do exemplo 1: No vetor inicial, 6 ($2\times 3$) e 10 ($2\times 5$) tem dois fatores primos distintos cada, enquanto que 8 ($2^3$) tem somente um. Assim, no primeiro comando, entre 6 e 8 o número com mais fatores primos distintos é o 6, mas considerados todos os 3 números, 10 é o maior com 2 fatores.

O terceiro comando soma uma unidade a 10, tornando-o igual a 11, o que reduz seus fatores primos distintos a um (o próprio 11). Assim, entre todos o número com maior número de divisores se torna 6, e considerado o 8 apenas, ele é a melhor opção.