Julia es profesora de Ciencias de la Computación y enseña Teoría de Lenguajes Formales en la universidad. En la primera clase del presente semestre, ella definió el concepto de expresiones de paréntesis balanceadas. Ella les explicó a los estudiantes que una expresión de paréntesis W es balanceada si la cadena es vacía, si W = (W1) o W = W1W2, donde W1 y W2 son ambas expresiones balanceadas. Por ejemplo, las expresiones "(())", "()()" y "(()())" son balanceadas. Sin embargo, las expresiones ")," "))((" y "(()(()" no son balanceadas.

Hoy Julia tiene un nuevo desafío para los estudiantes. Dada una secuencia de 1 ≤ S ≤ 100000 paréntesis, el costo de cambiar un paréntesis abierto (openCost), el costo de cambiar un paréntesis cerrado (closeCost), y el número de paréntesis que los estudiantes pueden cambiar (K), ellos necesitan calcular el costo mínimo para balancear un cierto rango de la secuencia de paréntesis si es posible o imprimir "Impossible" en caso contrario. En este problema los estudiantes pueden ejecutar dos tipos de consultas:

1. change(pos): Cambia la dirección del paréntesis en la posición ~1 \le pos \le S~.
2. cost(a, b): Calcula el costo mínimo de balancear el rango [a, b] si es posible ~1 \le a \le b \le S~.

Escriba un programa para que los estudiantes ejecuten ~1 \le Q \le 200000~ consultas de tipo 1 o 2.

Entrada

La entrada contiene en la primera línea la secuencia inicial de paréntesis S, ~|S| \le 100000~. La segunda línea contiene el número de consultas ~Q~ ~(1 \le Q \le 200000)~, el costo de cambiar un paréntesis abierto ~openCost~ ~(1 \le openCost \le 1000)~, el costo de cambiar un paréntesis cerrado ~closeCost~ ~(1 \le closeCost \le 1000)~ y el número de paréntesis ~K~ ~(1 \le K \le 10000)~ que los estudiantes pueden cambiar. Las siguientes ~Q~ líneas tienen la información de cada consulta, tal y como se explicó anteriormente.

Salida

Para cada consulta de tipo 2, imprima el costo mínimo de balancear el rango [a, b] si es posible. En caso contrario, imprima la cadena "Impossible" (sin las comillas).

Ejemplo de entrada

((()()()
9 3 2 3
1 2
2 1 8
1 5
1 8
2 2 7
2 5 6
1 7
1 8
2 1 7

Ejemplo de salida

0
7
2
Impossible