Alice et Bob mangent dans un restaurant à tapis roulant de makis. (Le maki est une sorte de sushi). Les clients du restaurant sont assis autour d'un tapis roulant circulaire comportant $N$ positions numérotées de $1$ à $N$ dans le sens des aiguilles d'une montre. Alice est assise à la position $p_A$ et Bob est assis à la position $p_B$.

Le restaurant sert $M$ sortes de makis différentes. Il y a $K$ assiettes différentes disposées sur le tapis roulant. La $i$-ème assiette se compose de $x_i$ morceaux d'une seule sorte de maki et chaque morceau coûte $c_i$ pièces. Une même sorte de maki peut apparaître sur plusieurs assiettes et avoir des coûts différents selon l'assiette. Aucune assiette supplémentaire ne sera ajoutée à celles déjà présentes sur le tapis roulant et aucun autre client n'est présent dans le restaurant (peut-être ont-ils choisi un restaurant de makis mal noté...).

Il y a au plus une assiette par position. Chaque seconde, le tapis roulant tourne dans le sens des aiguilles d'une montre. Formellement, s'il y a une assiette à la position $N$, elle se déplace à la position $1$ ; et toutes les autres assiettes se déplacent de la position $i$ à la position $i + 1$. Lorsqu'une assiette est devant un convive, celui-ci peut immédiatement en prendre n'importe quel nombre de morceaux, ou choisir de ne rien prendre. Par exemple, s'il y a une assiette avec $5$ morceaux de maki devant Alice, elle peut choisir d'en prendre seulement $2$. Les convives peuvent prendre des makis sur les assiettes qui se trouvent devant eux avant que le tapis ne tourne pour la première fois.

Alice et Bob veulent rentrer chez eux le plus rapidement possible pour regarder leur documentaire préféré sur les sushis. Ils connaissent la disposition complète du restaurant et chacun a un nombre souhaité de morceaux de chaque type de maki qu'il veut manger pour être rassasié. Aidez-les à déterminer le temps minimum (en secondes) qu'ils doivent passer dans le restaurant et le coût minimum (en pièces) pour qu'ils soient rassasiés dans ce laps de temps.

Entrée

La première ligne de l'entrée contient cinq entiers séparés par des espaces $N$, $M$, $K$, $p_A$ et $p_B$, où $N$ ($2 \le N \le 10^9$) est le nombre de positions sur le tapis roulant, $M$ ($1 \le M \le 10^5$) est le nombre de types de makis, $K$ ($1 \le K \le \min(2 \cdot 10^5, N)$) est le nombre d'assiettes, et $p_A$ et $p_B$ ($1 \le p_A, p_B \le N, p_A \neq p_B$) sont les positions respectives d'Alice et de Bob.

La deuxième ligne contient $M$ entiers séparés par des espaces $a_i$ ($0 \le a_i \le 10^6$), où $a_i$ est le nombre de morceaux de maki de type $i$ qu'Alice veut manger.

La troisième ligne contient $M$ entiers séparés par des espaces $b_i$ ($0 \le b_i \le 10^6$), où $b_i$ est le nombre de morceaux de maki de type $i$ que Bob veut manger.

Chacune des $K$ lignes suivantes décrit une assiette. La $j$-ème ligne contient quatre entiers séparés par des espaces $s_j$, $t_j$, $x_j$ et $c_j$, où $s_j$ ($1 \le s_j \le N$) est la position de départ de l'assiette, $t_j$ ($1 \le t_j \le M$) est le type de maki sur l'assiette, $x_j$ ($1 \le x_j \le 10^6$) est le nombre de morceaux sur l'assiette, et $c_j$ ($1 \le c_j \le 10^6$) est le coût par morceau. Toutes les assiettes ont des positions de départ différentes (tous les $s_j$ sont distincts).

Sortie

Affichez deux entiers : le temps minimum en secondes qu'Alice et Bob devront passer dans le restaurant et le coût minimum en pièces pour qu'ils soient rassasiés dans ce temps minimum. S'il est impossible pour eux deux d'être rassasiés, affichez impossible.

Exemples

Exemple 1

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

9 20

Exemple 2

5 1 1 2 3
2
2
5 1 3 3

impossible