Alice y Bob están comiendo en un restaurante de sushi con cinta transportadora. (El maki es un tipo de sushi). Los comensales en el restaurante se sientan alrededor de una cinta transportadora circular con $N$ posiciones numeradas del 1 al $N$ en sentido horario. Alice se sienta en la posición $p_A$ y Bob se sienta en la posición $p_B$.

El restaurante sirve $M$ tipos diferentes de maki. Hay $K$ platos distintos colocados en la cinta transportadora. El $i$-ésimo plato consiste en $x_i$ piezas de un solo tipo de maki y cada pieza cuesta $c_i$ monedas. El mismo tipo de maki puede aparecer en varios platos y tener costos diferentes en cada uno. No se añadirán más platos aparte de los que ya están en la cinta transportadora y no hay otros clientes en el restaurante (quizás eligieron un restaurante de maki mal calificado...).

Hay como máximo un plato por posición. Cada segundo, la cinta transportadora gira en sentido horario. Formalmente, si hay un plato en la posición $N$, se mueve a la posición 1; y todos los demás platos se mueven de la posición $i$ a la posición $i + 1$. Cuando un plato está frente a un comensal, este puede tomar inmediatamente cualquier cantidad de piezas de él, o elegir no tomar ninguna. Por ejemplo, si hay un plato con 5 piezas de maki frente a Alice, ella puede elegir tomar solo 2. Los comensales pueden tomar maki de los platos que tienen frente a ellos antes de que la cinta gire por primera vez.

Alice y Bob quieren regresar a casa lo antes posible para ver su documental de sushi favorito. Conocen la distribución completa del restaurante y cada uno tiene una cantidad deseada de piezas de cada tipo de maki que quiere comer para quedar satisfecho. Ayúdelos a determinar el tiempo mínimo (en segundos) que necesitan pasar en el restaurante y el costo mínimo (en monedas) para que queden satisfechos dentro de ese tiempo.

Entrada

La primera línea de la entrada contiene cinco enteros separados por espacios $N, M, K, p_A$ y $p_B$, donde $N$ ($2 \le N \le 10^9$) es el número de posiciones de la cinta transportadora, $M$ ($1 \le M \le 10^5$) es el número de tipos de maki, $K$ ($1 \le K \le \min(2 \cdot 10^5, N)$) es el número de platos, y $p_A$ y $p_B$ ($1 \le p_A, p_B \le N, p_A \neq p_B$) son las posiciones de Alice y Bob, respectivamente.

La segunda línea contiene $M$ enteros separados por espacios $a_i$ ($0 \le a_i \le 10^6$), donde $a_i$ es la cantidad de piezas de maki del tipo $i$ que Alice quiere comer.

La tercera línea contiene $M$ enteros separados por espacios $b_i$ ($0 \le b_i \le 10^6$), donde $b_i$ es la cantidad de piezas de maki del tipo $i$ que Bob quiere comer.

Cada una de las siguientes $K$ líneas describe un plato. La $j$-ésima línea contiene cuatro enteros separados por espacios $s_j, t_j, x_j$ y $c_j$, donde $s_j$ ($1 \le s_j \le N$) es la posición inicial del plato, $t_j$ ($1 \le t_j \le M$) es el tipo de maki en el plato, $x_j$ ($1 \le x_j \le 10^6$) es la cantidad de piezas en el plato, y $c_j$ ($1 \le c_j \le 10^6$) es el costo por pieza. Todos los platos tienen posiciones iniciales diferentes (todos los $s_j$ son distintos).

Figura M.1: Posición inicial de Alice, Bob y los platos en el Ejemplo 1.

Salida

Imprima dos enteros: el tiempo mínimo en segundos que Alice y Bob necesitarán pasar en el restaurante y el costo mínimo en monedas para que queden satisfechos dentro de ese tiempo. Si es imposible que ambos queden satisfechos, imprima impossible.

Ejemplos

Entrada 1

10 2 3 5 7
3 1
4 1
5 1 9 2
6 2 5 3
8 1 9 7

Salida 1

9 20

Entrada 2

5 1 1 2 3
2
2
5 1 3 3

Salida 2

impossible