미신을 믿는 헬리콥터 조종사

헬리콥터 조종사는 보수적이고 미신을 믿는다. 조종사마다 선호하는 이동이 목록으로 정해져 있고(동쪽으로 10 km, 북쪽으로 20 km 같은 식이다), 목록은 선호도가 높은 순서대로 나열되어 있다. 또 절대 착륙하지 않으려는 지점도 있다. 여기서 동쪽으로 20 km, 북쪽으로 50 km 떨어진 양돈장 같은 곳이다.

출발 지점을 $(0, 0)$, 목적지를 동쪽으로 $E$, 북쪽으로 $N$ 떨어진 $(E, N)$이라고 하자. 비행 계획은 선호하는 이동만 이어 붙여서 정확히 $(E, N)$에서 끝나는 이동 순서다. 조종사가 착륙하는 지점은 마지막 목적지까지 모두 금지 지점이 아니어야 한다. 출발 지점은 착륙으로 치지 않으므로 검사하지 않는다.

여기에 미신에서 나온 규칙이 하나 더 붙는다. 이동을 고를 때마다, 남은 여정을 끝까지 마칠 수 있는 이동 중에서 가장 선호하는 것을 골라야 한다.

예를 들어 목적지가 동쪽 30 km, 북쪽 40 km이고 선호하는 이동이 순서대로 $(10, 10)$과 $(0, 10)$이며 $(30, 30)$이 금지 지점이라고 하자. 북쪽으로 한 번 간 다음 북동쪽으로 세 번 가는 (0,10) 3*(10,10)도 목적지에 닿지만, 규칙에 맞는 비행 계획은 2*(10,10) (0,10) (10,10)이다. 북동쪽으로 두 번, 북쪽으로 한 번, 마지막으로 북동쪽으로 한 번 가는 계획이다. 반대로 $(20, 30)$까지 금지 지점이라면 어떤 비행 계획도 세울 수 없다.

모든 여정에서 동쪽으로 가야 하는 거리와 북쪽으로 가야 하는 거리는 양의 정수다. 선호하는 이동은 동쪽 거리와 북쪽 거리가 모두 0 이상인 정수이고, 두 값이 동시에 0이지는 않다.

입력은 여러 개의 여정으로 이루어진다. 각 여정은 네 정수 $E$, $N$, $H$, $F$가 있는 줄로 시작한다. 차례대로 동쪽으로 가야 하는 거리, 북쪽으로 가야 하는 거리, 선호하는 이동의 개수, 금지 지점의 개수다. 이어서 선호하는 이동 $H$개가 선호도가 높은 순서대로 주어지고, 그 뒤에 금지 지점 $F$개가 주어진다. 둘 다 한 줄에 동쪽 거리와 북쪽 거리를 적는 형식이다. 쓰이지 않는 이동이 있을 수 있고, 목적지보다 멀리 떨어진 금지 지점도 있을 수 있다. 입력의 마지막 줄은 0이 네 개인 줄 0 0 0 0이다.

여정마다 한 줄씩 출력한다. 각 줄은 Trip 으로 시작해서 1부터 세는 여정 번호, 콜론, 공백 하나를 적고, 그 뒤에 이동으로 쓴 비행 계획을 적는다. 같은 이동이 연달아 $k$번 나오면 k*(동쪽 거리,북쪽 거리)로 묶어서 적고, 한 번만 나오면 (동쪽 거리,북쪽 거리)로 적는다. 괄호 안에는 공백을 넣지 않고, 묶음과 묶음 사이는 공백 하나로 구분한다. 여정을 마칠 수 없으면 비행 계획 자리에 impossible을 적는다.