アリスとボブは回転寿司店で食事をしています（マキは寿司の一種です）。店内の客は、$1$ から $N$ までの番号が時計回りに振られた円形のコンベアベルトの周りに座っています。アリスは位置 $p_A$ に、ボブは位置 $p_B$ に座っています。

この店では $M$ 種類のマキが提供されています。コンベアベルト上には $K$ 枚の皿が置かれています。$i$ 番目の皿には $x_i$ 個の単一種類のマキが載っており、各ピースの価格は $c_i$ コインです。同じ種類のマキが複数の皿に載っていることもあり、皿によって価格が異なる場合もあります。コンベアベルト上に既に置かれている皿以外に新しい皿が追加されることはなく、店内に他の客はいません（おそらく、彼らは評判の悪い寿司店を選んでしまったのでしょう……）。

各位置には最大で $1$ 枚の皿しか置けません。毎秒、コンベアベルトは時計回りに回転します。厳密には、位置 $N$ に皿がある場合、それは位置 $1$ に移動し、それ以外のすべての皿は位置 $i$ から位置 $i+1$ へ移動します。皿が客の目の前に来たとき、客はそこから好きな数だけピースを取るか、あるいは何も取らないかを選択できます。例えば、アリスの目の前に $5$ ピース載った皿がある場合、彼女は $2$ ピースだけ取ることを選択できます。客はベルトが最初に回転する前に、目の前にある皿からマキを取ることができます。

アリスとボブは、お気に入りの寿司ドキュメンタリーを見るために、できるだけ早く帰宅したいと考えています。彼らは店の全レイアウトを把握しており、それぞれが満足するために必要な各マキの個数を決めています。彼らが店で過ごす必要のある最小時間（秒）と、その時間内に満足するために必要な最小コスト（コイン）を求めてください。

入力

入力の最初の行には、$5$ つのスペース区切りの整数 $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$) はそれぞれアリスとボブの位置です。

2行目には $M$ 個のスペース区切りの整数 $a_i$ ($0 \le a_i \le 10^6$) が含まれます。ここで、$a_i$ はアリスが食べたいマキの種類 $i$ の個数です。

3行目には $M$ 個のスペース区切りの整数 $b_i$ ($0 \le b_i \le 10^6$) が含まれます。ここで、$b_i$ はボブが食べたいマキの種類 $i$ の個数です。

続く $K$ 行の各行は皿を表します。$j$ 番目の行には $4$ つのスペース区切りの整数 $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$ は互いに異なります）。

図 M.1: サンプル入力 1 におけるアリス、ボブ、および皿の初期位置。

出力

アリスとボブが店で過ごす必要のある最小時間（秒）と、その最小時間内に満足するために必要な最小コスト（コイン）の2つの整数を出力してください。もし二人が満足することが不可能である場合は、impossible と出力してください。

入出力例

入力 1

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

出力 1

9 20

入力 2

5 1 1 2 3
2
2
5 1 3 3

出力 2

impossible