Alice và Bob đang ăn tại một nhà hàng sushi băng chuyền. (Maki là một loại sushi). Các thực khách trong nhà hàng ngồi xung quanh một băng chuyền hình tròn với $N$ vị trí được đánh số từ 1 đến $N$ theo chiều kim đồng hồ. Alice ngồi ở vị trí $p_A$ và Bob ngồi ở vị trí $p_B$.

Nhà hàng phục vụ $M$ loại maki khác nhau. Có $K$ đĩa thức ăn được đặt trên băng chuyền. Đĩa thứ $i$ bao gồm $x_i$ miếng của một loại maki duy nhất và mỗi miếng có giá $c_i$ đồng. Cùng một loại maki có thể xuất hiện trên nhiều đĩa và có giá khác nhau trên các đĩa khác nhau. Sẽ không có thêm đĩa nào được đặt lên băng chuyền ngoài những gì đã có và không có thực khách nào khác trong nhà hàng (có lẽ họ đã chọn một nhà hàng sushi được đánh giá thấp...).

Mỗi vị trí có tối đa một đĩa. Mỗi giây, băng chuyền quay theo chiều kim đồng hồ. Cụ thể, nếu có một đĩa ở vị trí $N$, nó sẽ di chuyển đến vị trí 1; và tất cả các đĩa khác di chuyển từ vị trí $i$ đến vị trí $i + 1$. Khi một đĩa ở trước mặt thực khách, họ có thể lấy ngay lập tức bất kỳ số lượng miếng nào từ đĩa đó, hoặc chọn không lấy miếng nào. Ví dụ, nếu có một đĩa với 5 miếng maki trước mặt Alice, cô ấy có thể chọn chỉ lấy 2 miếng. Các thực khách có thể lấy maki từ các đĩa trước mặt họ trước khi băng chuyền bắt đầu quay lần đầu tiên.

Alice và Bob muốn về nhà càng sớm càng tốt để xem bộ phim tài liệu về sushi yêu thích của họ. Họ biết toàn bộ sơ đồ của nhà hàng, và mỗi người có một số lượng miếng maki mong muốn của từng loại để cảm thấy hài lòng. Hãy giúp họ xác định thời gian tối thiểu (tính bằng giây) họ cần dành ra tại nhà hàng và chi phí tối thiểu (tính bằng đồng) để họ trở nên hài lòng trong khoảng thời gian đó.

Dữ liệu vào

Dòng đầu tiên chứa năm số nguyên cách nhau bởi dấu cách $N, M, K, p_A$ và $p_B$, trong đó $N$ ($2 \le N \le 10^9$) là số vị trí trên băng chuyền, $M$ ($1 \le M \le 10^5$) là số loại maki, $K$ ($1 \le K \le \min(2 \cdot 10^5, N)$) là số lượng đĩa, và $p_A$ và $p_B$ ($1 \le p_A, p_B \le N, p_A \neq p_B$) lần lượt là vị trí của Alice và Bob.

Dòng thứ hai chứa $M$ số nguyên cách nhau bởi dấu cách $a_i$ ($0 \le a_i \le 10^6$), trong đó $a_i$ là số miếng maki loại $i$ mà Alice muốn ăn.

Dòng thứ ba chứa $M$ số nguyên cách nhau bởi dấu cách $b_i$ ($0 \le b_i \le 10^6$), trong đó $b_i$ là số miếng maki loại $i$ mà Bob muốn ăn.

Mỗi dòng trong $K$ dòng tiếp theo mô tả một đĩa. Dòng thứ $j$ chứa bốn số nguyên cách nhau bởi dấu cách $s_j, t_j, x_j$ và $c_j$, trong đó $s_j$ ($1 \le s_j \le N$) là vị trí bắt đầu của đĩa, $t_j$ ($1 \le t_j \le M$) là loại maki trên đĩa, $x_j$ ($1 \le x_j \le 10^6$) là số miếng trên đĩa, và $c_j$ ($1 \le c_j \le 10^6$) là giá mỗi miếng. Tất cả các đĩa có vị trí bắt đầu khác nhau (tất cả $s_j$ đều phân biệt).

Dữ liệu ra

In ra hai số nguyên: thời gian tối thiểu tính bằng giây mà Alice và Bob cần dành ra tại nhà hàng và chi phí tối thiểu tính bằng đồng để họ trở nên hài lòng trong khoảng thời gian tối thiểu đó. Nếu cả hai không thể cùng hài lòng, hãy in ra impossible.

Ví dụ

Ví dụ 1

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

9 20

Ví dụ 2

5 1 1 2 3
2
2
5 1 3 3

impossible