Alice 和 Bob 正在一家传送带寿司店用餐。（Maki 是一种寿司）。餐厅的食客围坐在一圈传送带旁，传送带上有 $N$ 个位置，按顺时针方向编号为 $1$ 到 $N$。Alice 坐在位置 $p_A$，Bob 坐在位置 $p_B$。

餐厅供应 $M$ 种不同的 maki。传送带上放置了 $K$ 个不同的盘子。第 $i$ 个盘子包含 $x_i$ 个同种 maki，每块 maki 的价格为 $c_i$ 个硬币。同种 maki 可能出现在多个盘子上，且在不同盘子上的价格可能不同。传送带上不会再增加新的盘子，餐厅里也没有其他顾客（也许他们选了一家评价很差的寿司店……）。

每个位置最多只能放一个盘子。传送带每秒顺时针旋转一次。形式化地说，如果位置 $N$ 上有一个盘子，它会移动到位置 $1$；其他所有盘子都从位置 $i$ 移动到位置 $i+1$。当盘子到达食客面前时，他们可以立即从盘中拿走任意数量的 maki，也可以选择不拿。例如，如果 Alice 面前的盘子里有 $5$ 块 maki，她可以选择只拿 $2$ 块。食客可以在传送带第一次旋转前从面前的盘子中拿取 maki。

Alice 和 Bob 想尽快回家观看他们最喜欢的寿司纪录片。他们了解餐厅的完整布局，并且每个人都有他们想要食用的每种 maki 的期望数量，以达到满足感。请帮助他们确定他们需要在餐厅花费的最短时间（以秒为单位），以及在最短时间内达到满足感所需的最少花费（以硬币为单位）。

输入格式

第一行包含五个空格分隔的整数 $N, M, K, p_A$ 和 $p_B$，其中 $N$ ($2 \le N \le 10^9$) 是传送带的位置数，$M$ ($1 \le M \le 10^5$) 是 maki 的种类数，$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$ 种 maki 的数量。

第三行包含 $M$ 个空格分隔的整数 $b_i$ ($0 \le b_i \le 10^6$)，其中 $b_i$ 是 Bob 想要食用的第 $i$ 种 maki 的数量。

接下来的 $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$) 是盘子上 maki 的种类，$x_j$ ($1 \le x_j \le 10^6$) 是盘子上的 maki 数量，$c_j$ ($1 \le c_j \le 10^6$) 是每块 maki 的价格。所有盘子的起始位置都不同（所有 $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