앨리스와 밥은 회전 초밥 식당에서 식사 중입니다. (마키는 초밥의 일종입니다). 식당의 손님들은 $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$는 서로 다릅니다).

그림 M.1: 예제 입력 1의 앨리스, 밥, 그리고 접시들의 초기 위치.

출력

앨리스와 밥이 식당에서 보내야 하는 최소 시간(초)과 그 최소 시간 내에 만족하기 위해 필요한 최소 비용(코인)을 두 정수로 출력하세요. 두 사람 모두 만족하는 것이 불가능하다면 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