Alice i Bob jedzą w restauracji z przenośnikiem taśmowym do maki (maki to rodzaj sushi). Klienci w restauracji siedzą wokół okrągłego przenośnika taśmowego z $N$ pozycjami ponumerowanymi od $1$ do $N$ w kierunku zgodnym z ruchem wskazówek zegara. Alice siedzi na pozycji $p_A$, a Bob na pozycji $p_B$.

Restauracja serwuje $M$ różnych rodzajów maki. Na przenośniku znajduje się $K$ różnych talerzy. $i$-ty talerz zawiera $x_i$ kawałków jednego rodzaju maki, a każdy kawałek kosztuje $c_i$ monet. Ten sam rodzaj maki może pojawiać się na wielu talerzach i mieć różne ceny na różnych talerzach. Na przenośnik nie zostaną dodane żadne nowe talerze poza tymi, które już się na nim znajdują, a w restauracji nie ma innych klientów (być może wybrali słabo ocenianą restaurację z maki...).

Na każdej pozycji znajduje się co najwyżej jeden talerz. Co sekundę przenośnik obraca się zgodnie z ruchem wskazówek zegara. Formalnie, jeśli talerz znajduje się na pozycji $N$, przesuwa się na pozycję $1$; wszystkie inne talerze przesuwają się z pozycji $i$ na pozycję $i + 1$. Gdy talerz znajduje się przed klientem, może on natychmiast zabrać z niego dowolną liczbę kawałków lub zdecydować się nie brać żadnego. Na przykład, jeśli przed Alice znajduje się talerz z $5$ kawałkami maki, może ona zdecydować się zabrać tylko $2$. Klienci mogą zabierać maki z talerzy znajdujących się przed nimi, zanim taśma obróci się po raz pierwszy.

Alice i Bob chcą wrócić do domu jak najszybciej, aby obejrzeć swój ulubiony film dokumentalny o sushi. Znają pełny układ restauracji i każdy z nich ma pożądaną liczbę kawałków każdego rodzaju maki, które chce zjeść, aby być usatysfakcjonowanym. Pomóż im określić minimalny czas (w sekundach), jaki muszą spędzić w restauracji, oraz minimalny koszt (w monetach), aby stali się usatysfakcjonowani w tym czasie.

Wejście

Pierwsza linia wejścia zawiera pięć liczb całkowitych oddzielonych spacjami $N, M, K, p_A$ oraz $p_B$, gdzie $N$ ($2 \le N \le 10^9$) to liczba pozycji na przenośniku, $M$ ($1 \le M \le 10^5$) to liczba rodzajów maki, $K$ ($1 \le K \le \min(2 \cdot 10^5, N)$) to liczba talerzy, a $p_A$ oraz $p_B$ ($1 \le p_A, p_B \le N, p_A \neq p_B$) to odpowiednio pozycje Alice i Boba.

Druga linia zawiera $M$ liczb całkowitych oddzielonych spacjami $a_i$ ($0 \le a_i \le 10^6$), gdzie $a_i$ to liczba kawałków maki typu $i$, które chce zjeść Alice.

Trzecia linia zawiera $M$ liczb całkowitych oddzielonych spacjami $b_i$ ($0 \le b_i \le 10^6$), gdzie $b_i$ to liczba kawałków maki typu $i$, które chce zjeść Bob.

Każda z kolejnych $K$ linii opisuje talerz. $j$-ta linia zawiera cztery liczby całkowite oddzielone spacjami $s_j, t_j, x_j$ oraz $c_j$, gdzie $s_j$ ($1 \le s_j \le N$) to pozycja początkowa talerza, $t_j$ ($1 \le t_j \le M$) to rodzaj maki na talerzu, $x_j$ ($1 \le x_j \le 10^6$) to liczba kawałków na talerzu, a $c_j$ ($1 \le c_j \le 10^6$) to koszt za jeden kawałek. Wszystkie talerze mają różne pozycje początkowe (wszystkie $s_j$ są różne).

Rysunek M.1: Pozycja początkowa Alice, Boba oraz talerzy w Przykładzie 1.

Wyjście

Wypisz dwie liczby całkowite: minimalny czas w sekundach, jaki Alice i Bob będą musieli spędzić w restauracji, oraz minimalny koszt w monetach, aby stali się usatysfakcjonowani w tym minimalnym czasie. Jeśli osiągnięcie satysfakcji przez oboje jest niemożliwe, wypisz impossible.

Przykład

Wejście 1

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

Wyjście 1

9 20

Wejście 2

5 1 1 2 3
2
2
5 1 3 3

Wyjście 2

impossible