Алиса и Боб обедают в ресторане с конвейерной лентой, на которой подают маки (разновидность суши). Посетители ресторана сидят вокруг круговой конвейерной ленты с $N$ позициями, пронумерованными от $1$ до $N$ по часовой стрелке. Алиса сидит на позиции $p_A$, а Боб — на позиции $p_B$.

Ресторан предлагает $M$ различных видов маки. На конвейерной ленте расставлено $K$ различных тарелок. $i$-я тарелка содержит $x_i$ кусочков маки одного вида, и каждый кусочек стоит $c_i$ монет. Один и тот же вид маки может встречаться на нескольких тарелках и иметь разную стоимость на разных тарелках. Новые тарелки на ленту не добавляются, и других посетителей в ресторане нет (возможно, они выбрали ресторан с плохим рейтингом...).

На каждой позиции находится не более одной тарелки. Каждую секунду конвейерная лента поворачивается по часовой стрелке. Формально, если тарелка находится на позиции $N$, она перемещается на позицию $1$; все остальные тарелки перемещаются с позиции $i$ на позицию $i + 1$. Когда тарелка оказывается перед посетителем, он может немедленно взять с неё любое количество кусочков или не брать ничего. Например, если перед Алисой находится тарелка с $5$ кусочками маки, она может выбрать взять только $2$. Посетители могут брать маки с тарелок, находящихся перед ними, до того, как лента повернётся в первый раз.

Алиса и Боб хотят вернуться домой как можно скорее, чтобы посмотреть свой любимый документальный фильм о суши. Они знают полную планировку ресторана, и у каждого из них есть желаемое количество кусочков каждого вида маки, которые они хотят съесть, чтобы насытиться. Помогите им определить минимальное время (в секундах), которое им нужно провести в ресторане, и минимальную стоимость (в монетах), чтобы они оба насытились за это время.

Входные данные

Первая строка входных данных содержит пять целых чисел $N, M, K, p_A$ и $p_B$, где $N$ ($2 \le N \le 10^9$) — количество позиций на конвейерной ленте, $M$ ($1 \le M \le 10^5$) — количество видов маки, $K$ ($1 \le K \le \min(2 \cdot 10^5, N)$) — количество тарелок, а $p_A$ и $p_B$ ($1 \le p_A, p_B \le N, p_A \neq p_B$) — позиции Алисы и Боба соответственно.

Вторая строка содержит $M$ целых чисел $a_i$ ($0 \le a_i \le 10^6$), где $a_i$ — количество кусочков маки типа $i$, которое хочет съесть Алиса.

Третья строка содержит $M$ целых чисел $b_i$ ($0 \le b_i \le 10^6$), где $b_i$ — количество кусочков маки типа $i$, которое хочет съесть Боб.

Каждая из следующих $K$ строк описывает тарелку. $j$-я строка содержит четыре целых числа $s_j, t_j, x_j$ и $c_j$, где $s_j$ ($1 \le s_j \le N$) — начальная позиция тарелки, $t_j$ ($1 \le t_j \le M$) — тип маки на тарелке, $x_j$ ($1 \le x_j \le 10^6$) — количество кусочков на тарелке, а $c_j$ ($1 \le c_j \le 10^6$) — стоимость одного кусочка. Все тарелки имеют разные начальные позиции (все $s_j$ различны).

Выходные данные

Выведите два целых числа: минимальное время в секундах, которое Алисе и Бобу нужно провести в ресторане, и минимальную стоимость в монетах, чтобы они оба насытились за это минимальное время. Если для обоих невозможно насытиться, выведите impossible.

Рисунок M.1: Начальное положение Алисы, Боба и тарелок в первом примере.

Примеры

Пример 1

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

9 20

Пример 2

5 1 1 2 3
2
2
5 1 3 3

impossible