4075 - Jules and Parentheses

Created by Rubén Alcolea Núñez
Added by ymondelo20 (2018-09-05)
Limits
Total Time: 10000 MS | Test Time: 1000 MS |Memory: 512 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Jules is a Computer Science professor who teaches Formal Language Theory at the university. In the first class of the current semester, she defined the concept of balanced parentheses expressions. She explained to her students that a parentheses expression W is balanced if W is the empty string, if W = (W1) or W = W1W2 where W1 and W2 are both balanced expressions. For example, the expressions "(())", "()()", and "(()())" are balanced. However the expressions ")", "))((", and "(()(()" are not balanced.

Today Jules has a new challenge for the students. Given a sequence of 1 ≤ S ≤ 105 parentheses, the cost of changing an open parenthesis (openCost), the cost of changing a closing parenthesis (closeCost), and the number of parentheses that the students can change (K), they need to compute the minimum cost to balance a certain range of a sequence of parentheses. It may also be impossible to balance the range, in which case they should answer "Impossible". In this problem the students can perform two types of queries:
  1. change(pos): change the direction of parenthesis at position 1 ≤ pos ≤ S.
  2. cost(a, b): compute the minimum cost to balance the range [a, b] if it is possible 1 ≤ a ≤ b ≤ S.
Write a program for the students to perform 1 ≤ Q ≤ 2 × 105 queries of type 1 or 2.
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 de un paréntesis en una posición 1 ≤ pos ≤ S.
  2. cost(a, b): Calcula el costo mínimo de balancear el rango [a, b] si es posible 1 ≤ a ≤ b ≤ S.
Escriba un programa para que los estudiantes ejecuten 1 ≤ Q ≤ 200000 consultas de tipo 1 o 2
Jules is a Computer Science professor who teaches Formal Language Theory at the university. In the first class of the current semester, she defined the concept of balanced parentheses expressions. She explained to her students that a parentheses expression W is balanced if W is the empty string, if W = (W1) or W = W1W2 where W1 and W2 are both balanced expressions. For example, the expressions "(())", "()()", and "(()())" are balanced. However the expressions ")", "))((", and "(()(()" are not balanced.

Today Jules has a new challenge for the students. Given a sequence of 1 ≤ S ≤ 105 parentheses, the cost of changing an open parenthesis (openCost), the cost of changing a closing parenthesis (closeCost), and the number of parentheses that the students can change (K), they need to compute the minimum cost to balance a certain range of a sequence of parentheses. It may also be impossible to balance the range, in which case they should answer "Impossible". In this problem the students can perform two types of queries:
  1. change(pos): change the direction of parenthesis at position 1 ≤ pos ≤ S.
  2. cost(a, b): compute the minimum cost to balance the range [a, b] if it is possible 1 ≤ a ≤ b ≤ S.
Write a program for the students to perform 1 ≤ Q ≤ 2 × 105 queries of type 1 or 2.

Input specification

The input contains in the first line the initial sequence of parentheses S, where |S| ≤ 105. The second line contains the number of queries Q (1 ≤ Q ≤ 2 × 105), the cost of changing an open parenthesis openCost (1 ≤ openCost ≤ 1000), the cost of changing a closing parenthesis closeCost (1 ≤ closeCost ≤ 1000) and the number of parentheses K (1 ≤ K ≤ 104) that the students can change. The following Q lines have the information of each query, as it was explained above.
La entrada contiene en la primera línea la secuencia inicial de paréntesis S, |S| ≤ 100000. La segunda línea contiene el número de consultas Q (1 ≤ Q ≤ 200000), el costo de cambiar un paréntesis abierto openCost (1 ≤ openCost ≤ 1000), el costo de cambiar un paréntesis cerrado closeCost (1 ≤ closeCost ≤ 1000) y el número de paréntesis K (1 ≤ K ≤ 10000) que los estudiantes pueden cambiar. Las siguientes Q líneas tienen la información de cada consulta, tal y como se explicó anteriormente.
The input contains in the first line the initial sequence of parentheses S, where |S| ≤ 105. The second line contains the number of queries Q (1 ≤ Q ≤ 2 × 105), the cost of changing an open parenthesis openCost (1 ≤ openCost ≤ 1000), the cost of changing a closing parenthesis closeCost (1 ≤ closeCost ≤ 1000) and the number of parentheses K (1 ≤ K ≤ 104) that the students can change. The following Q lines have the information of each query, as it was explained above.

Output specification

For each query of type 2, print the minimum cost to balance the range [a, b] if it is possible. Otherwise print "Impossible" (without the quotes).
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).
The input contains in the first line the initial sequence of parentheses S, where |S| ≤ 105. The second line contains the number of queries Q (1 ≤ Q ≤ 2 × 105), the cost of changing an open parenthesis openCost (1 ≤ openCost ≤ 1000), the cost of changing a closing parenthesis closeCost (1 ≤ closeCost ≤ 1000) and the number of parentheses K (1 ≤ K ≤ 104) that the students can change. The following Q lines have the information of each query, as it was explained above.

Sample input

((()()()
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

Sample output

0
7
2
Impossible

Hint(s)