다친 웜홀은 하나도 없었습니다...

당신은 인과율 위반 단속국(Causality Infraction Agency)의 국장으로서, 역사의 흐름을 바꾸려는 자들을 추적하고 체포하는 일을 맡고 있습니다.

임무 지시서에는 시간 요원이 도달해야 하는 정확한 연도가 적혀 있지만, 시간 여행은 그렇게 간단하지 않습니다. 요원은 오직 웜홀을 통해서만 이동할 수 있으며, 각 웜홀은 특정한 두 연도를 연결합니다. 목적지 연도에 도달하려면 보통 여러 개의 웜홀을 순서대로 통과해야 하고, 다음 웜홀이 나타날 때까지 과거나 미래에서 기다려야 할 수도 있습니다. 웜홀 통과 역시 공짜가 아닙니다. 시간상 앞으로 이동하면 즉시 나이를 먹고, 뒤로 이동하면 조금 젊어집니다.

단속국은 요원이 입사 이후 먹은 나이만큼 급여를 지급하므로, 당신은 모든 요원의 노화를 최대한 줄여야 합니다. 노화를 최소화하는 웜홀 이동 경로를 찾아, 각 요원이 임무를 마친 뒤 몇 년을 나이 들게 되는지 출력하는 프로그램을 작성하세요.

노화량은 다음과 같이 계산합니다.

• 기다리기. 출발 연도에서 그보다 뒤인 목적 연도까지 기다리면 다음만큼 나이를 먹습니다.

  $$\text{목적 연도} - \text{출발 연도}$$

  예를 들어 1785년에서 1793년까지 기다리면 8년을 나이 듭니다. (기다리기는 시간을 앞으로만 흐르게 하며, 기다려서 과거로 갈 수는 없습니다.)

• 도착 연도가 출발 연도보다 늦은 웜홀을 통해 앞으로 이동하면 다음만큼 나이를 먹습니다.

  $$\left\lfloor \frac{\text{도착 연도} - \text{출발 연도}}{2} \right\rfloor$$

  즉, 그냥 기다렸을 때 먹었을 나이의 절반(내림)입니다. 차이가 충분히 작으면 0으로 내림될 수 있습니다.

• 도착 연도가 출발 연도보다 이른 웜홀을 통해 뒤로 이동하면 젊어지며, 다음만큼 나이를 되돌려 받습니다.

  $$\left\lfloor \frac{\text{출발 연도} - \text{도착 연도}}{4} \right\rfloor$$

  즉 두 연도 차이의 4분의 1(내림)입니다. 차이가 충분히 작으면 0으로 내림될 수 있습니다.

• 출발 연도와 도착 연도가 같은 웜홀도 존재할 수 있지만, 이 경우 노화도 이동도 일어나지 않습니다.

각 데이터셋에는 모든 요원이 출발하는 하나의 시작 연도와, 요원마다 하나씩 주어지는 임무 목록이 포함됩니다. 각 임무에는 최종 목적지 연도가 명시됩니다. 임무는 왕복이 가능할 때에만 완료할 수 있습니다. 즉 시작 연도에서 목적지 연도로 갔다가 다시 시작 연도로 돌아와야 합니다. 이러한 왕복이 불가능하면 그 임무는 무효입니다. 요원의 최대 수명은 고려하지 않아도 됩니다. 총 노화량이 아무리 크더라도 왕복만 가능하면 유효한 임무입니다.

첫 줄에는 데이터셋의 개수를 나타내는 정수 $N$ ($1 \le N \le 100$)이 주어집니다. 각 데이터셋의 형식은 다음과 같습니다.

• 이 데이터셋의 웜홀 개수를 나타내는 정수 $W$ ($1 \le W \le 100$)가 한 줄에 주어집니다.
• 이어서 D A 형식의 줄이 $W$개 주어지며 ($1 \le D, A \le 9999$), 각 줄은 출발 연도가 $D$, 도착 연도가 $A$인 웜홀 하나를 나타냅니다. 웜홀은 단방향으로, 연도 $D$에서 연도 $A$로만 이동할 수 있고 그 반대는 불가능합니다.
• 모든 요원의 시작 연도를 나타내는 정수 $S$ ($1 \le S \le 9999$)가 한 줄에 주어집니다.
• 분석할 임무의 개수를 나타내는 정수 $M$ ($1 \le M \le 100$)이 한 줄에 주어집니다.
• 이어서 각 임무의 최종 목적지 연도를 나타내는 정수 $F$ ($1 \le F \le 9999$)가 한 줄에 하나씩, 총 $M$개 주어집니다.

각 데이터셋에 대해 먼저 DATA SET #k 줄을 출력합니다. 여기서 $k$는 첫 번째 데이터셋이면 $1$, 두 번째면 $2$ 등입니다. 그런 다음 입력과 같은 순서로 임무마다 한 줄씩, 총 $M$줄을 출력합니다. 각 줄에는 해당 요원이 나이 드는 햇수(정수)를 출력하거나, 임무를 완료할 수 없는 경우(목적지에 도달할 수 없거나 돌아오는 여정이 불가능한 경우) IMPOSSIBLE을 출력합니다.