Alice 和 Bob 正在一家迴轉壽司店用餐（Maki 是一種壽司）。店內的顧客坐在一個圓形的輸送帶周圍，輸送帶上有 $N$ 個位置，以順時針方向編號為 $1$ 到 $N$。Alice 坐在位置 $p_A$，Bob 坐在位置 $p_B$。

餐廳提供 $M$ 種不同的壽司。輸送帶上放置了 $K$ 個不同的盤子。第 $i$ 個盤子包含 $x_i$ 個單一種類的壽司，每塊壽司的價格為 $c_i$。同一種壽司可能會出現在多個盤子上，且在不同盤子上的價格可能不同。輸送帶上不會再增加額外的盤子，店內也沒有其他顧客（也許他們選了一家評價很差的壽司店……）。

每個位置最多放置一個盤子。輸送帶每秒會順時針旋轉一次。正式地說，如果位置 $N$ 上有一個盤子，它會移動到位置 $1$；所有其他盤子則從位置 $i$ 移動到位置 $i + 1$。當盤子移動到顧客面前時，他們可以立即從盤子上拿取任意數量的壽司，或者選擇不拿。例如，如果 Alice 面前的盤子上有 $5$ 塊壽司，她可以選擇只拿 $2$ 塊。顧客可以在輸送帶第一次旋轉前，先從面前的盤子上拿取壽司。

Alice 和 Bob 希望儘快回家觀看他們最喜歡的壽司紀錄片。他們知道餐廳的完整佈局，並且每個人都有他們想要吃掉的每種壽司的數量，以達到滿足。請幫助他們確定他們在餐廳需要花費的最短時間（以秒為單位），以及在該時間內達到滿足所需的最少花費（以硬幣為單位）。

輸入格式

第一行包含五個以空格分隔的整數 $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$) 分別是 Alice 和 Bob 的位置。

第二行包含 $M$ 個以空格分隔的整數 $a_i$ ($0 \le a_i \le 10^6$)，其中 $a_i$ 是 Alice 想要吃的第 $i$ 種壽司的數量。

第三行包含 $M$ 個以空格分隔的整數 $b_i$ ($0 \le b_i \le 10^6$)，其中 $b_i$ 是 Bob 想要吃的第 $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$ 均相異）。

輸出格式

輸出兩個整數：Alice 和 Bob 在餐廳需要花費的最短時間（以秒為單位），以及在該最短時間內達到滿足所需的最少花費（以硬幣為單位）。如果他們兩人永遠無法達到滿足，則輸出 impossible。

圖 M.1：範例輸入 1 中 Alice、Bob 和盤子的初始位置。

範例

範例輸入 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