Jade City tiene un sistema ferroviario circular con $N$ estaciones numeradas $1,2,\ldots,N$ en sentido horario. Debido al rápido desarrollo de la ciudad en los últimos años, ya está en uso una línea adicional que conecta la estación $1$ y la estación $K$ ($1<K\le N$). Además de estas dos estaciones terminales, hay otras $M$ estaciones en la línea. Están numeradas $N+1,N+2,\ldots,N+M$ en el sentido de la estación $1$ a la estación $K$. Véase la figura $14$.

Figura 14: Ilustración del sistema ferroviario de Jade City

Las vías que conectan estaciones adyacentes tienen distintas longitudes, por lo que recorrerlas requiere diferentes cantidades de tiempo. Para simplificar, las etiquetamos así:

• $c_i$: para $1\le i\le N-1$, la vía entre la estación $i$ y la estación $i+1$;

• $c_N$: la vía entre la estación $N$ y la estación $1$;

• $x_0$: la vía entre la estación $1$ y la estación $N+1$;

• $x_j$: para $1\le j\le M-1$, la vía entre la estación $N+j$ y la estación $N+j+1$;

• $x_M$: la vía entre la estación $N+M$ y la estación $K$.

Dados los tiempos de viaje de cada una de estas vías, queremos calcular la forma más rápida de viajar de una estación $u$ a otra $v$ utilizando este sistema ferroviario. Sin embargo, de vez en cuando algunas vías pueden quedar fuera de servicio por mantenimiento, de modo que el tren no puede pasar por ellas. Inicialmente todas las vías están disponibles.

Entrada

La primera línea contiene los tres enteros $N,K,M$ de la descripción, seguidos de un entero $Q$, el número total de consultas u operaciones de actualización. La segunda línea contiene $N$ enteros no negativos que indican los tiempos de viaje $t$ por las vías $c_1,c_2,\ldots,c_N$, respectivamente. La tercera contiene $M+1$ enteros no negativos que indican los tiempos de viaje $t$ por las vías $x_0,x_1,\ldots,x_M$, respectivamente. Después siguen $Q$ líneas, cada una con una operación en el siguiente formato:

• Si la línea empieza por la letra q seguida de dos enteros $u,v$ ($1\le u,v\le N+M$), se pide imprimir el menor tiempo de viaje de la estación $u$ a la estación $v$, si existe una ruta. En caso contrario, imprime impossible.

• Si la línea empieza por la letra c seguida de un entero $i$ ($1\le i\le N$), se cambia el estado de la arista etiquetada $c_i$. En concreto, si $c_i$ estaba disponible, pasa a estar fuera de servicio; si estaba fuera de servicio, pasa a estar disponible.

• Si la línea empieza por la letra x seguida de un entero $j$ ($0\le j\le M$), se cambia el estado de la arista etiquetada $x_j$. En concreto, si $x_j$ estaba disponible, pasa a estar fuera de servicio; si estaba fuera de servicio, pasa a estar disponible.

Restricciones

• $1\le N,K,M,Q\le10^6$;

• El tiempo de viaje de cualquier vía es un entero no negativo de como máximo $200$.

Salida

Para cada consulta, imprime la respuesta correspondiente en una línea separada.

Ejemplos

Entrada 1

4 3 1 9
2 3 8 4
1 1
q 3 4
x 0
q 3 4
c 3
q 3 4
c 1
q 3 4
x 0
q 3 4

Salida 1

6
8
9
impossible
6