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. 

   (1) Si $t=1$, se da un valor $i$ ($1 \leq i \leq n$). 
   (2) Si $t=2$, se dan dos valores $l$ y $r$ ($1 \leq l \leq r \leq n$). 
   (3) 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

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

Para el primer caso, las primeras 4 operaciones se realizan de la siguiente manera: (1) Se elimina un factor primo al azar de $a_4$; ya que $a_4 = 4 = 2 \times 2$, se obtiene $a_4 = 2$. (2) La suma de los factores primos de 10, 9, 2 y 2 es \underline{$2 + 5$} $+$ \underline{$3 + 3$} $+$ \underline{$2$} $+$ \underline{$2$} $= 17$. (3) 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$. (4) Hay dos posibles sumas: \underline{$2$} $+$ \underline{$3 + 3$} $+$ \underline{$2$} $ = 10$ o \underline{$5$} $+$ \underline{$3 + 3$} $+$ \underline{$2$} $ = 13$; la menor es igual a 10.