Se tienen un arreglo $a$ de $n$ números enteros positivos. Sobre este arreglo se realizan tres tipos de operaciones:

1. Dado un valor $i$, eliminar un factor primo al azar de $a_i$. Si $a_i$ no tiene factores primos, no se hace nada.
2. Dados dos valores $l$ y $r$, hallar la mínima posible suma de los factores primos de los números $a_l, a_{l+1}, \ldots, a_r$.
3. Dados tres valores $l$, $r$ y $x$, asignar a $a_i$ el valor $x$ para todo $l \leq i \leq r$.

Dado el arreglo $a$ y una secuencia de $q$ operaciones realizadas en orden, determina el resultado de cada operación de tipo 2.

La primera línea contiene un entero $n$ ($1 \leq n \leq 10^5$), el tamaño del arreglo $a$.

La segunda línea contiene $n$ enteros $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^4$), los elementos del arreglo $a$.

La tercera línea contiene un entero $q$ ($1 \leq q \leq 10^5$), el número de operaciones.

Las siguientes $q$ líneas describen las operaciones realizadas en orden. Cada operación está descrita por un número entero $t$ ($1 \leq t \leq 3$) y los valores correspondientes a la operación.

• Si $t=1$, se da un valor $i$ ($1 \leq i \leq n$).
• Si $t=2$, se dan dos valores $l$ y $r$ ($1 \leq l \leq r \leq n$).
• Si $t=3$, se dan tres valores $l$, $r$ y $x$ ($1 \leq l \leq r \leq n$, $1 \leq x \leq 10^4$).

Por cada operación de tipo 2, imprime un entero, la mínima posible suma de los factores primos de los números $a_l, a_{l+1}, \ldots, a_r$.

Subtareas

1. (9 puntos) $1 \leq n \leq 10$.
2. (40 puntos) No hay operaciones de tipo 3.
3. (51 puntos) Sin restricciones adicionales.

Ejemplos

Para el primer caso, las primeras 4 operaciones se realizan de la siguiente manera:

• Se elimina un factor primo al azar de $a_4$; ya que $a_4 = 4 = 2 \times 2$, se obtiene $a_4 = 2$.
• La suma de los factores primos de 10, 9, 2 y 2 es $2 + 5$ $+$ $3 + 3$ $+$ $2$ $+$ $2$ $= 17$.
• Se elimina un factor primo al azar de $a_1$; ya que $a_1 = 10 = 2 \times 5$, se puede obtener $a_1 = 2$ o $a_1 = 5$.
• Hay dos posibles sumas: $2$ $+$ $3 + 3$ $+$ $2$ $ = 10$ o $5$ $+$ $3 + 3$ $+$ $2$ $ = 13$; la menor es igual a 10.