등산객 안전 거리

한 산악회가 코스 하나에서 기록 경기를 연다. 코스에는 표지점이 $P$개 있고, $i$번 표지점은 출발점에서 $d_i$미터 떨어져 있으며 $d_1 = 0$이다. 이 종목에서 오래 걸리는 일은 길을 찾는 작업뿐이라, 다음에 어디로 갈지만 알면 이동 자체는 순식간에 끝난다.

지금 코스에는 등산객이 $K$명 있다. $i$번 등산객은 $V_i$번 표지점에 서 있고, 개인 공간으로 $A_i$미터가 필요하다. 어느 순간에나 다음 두 규칙이 성립한다.

• 코스에서 이웃한 두 등산객, 즉 사이에 다른 등산객이 없는 두 사람의 거리는 $B$미터 이하다.
• $i$번 등산객은 나머지 모두를 $A_i$미터 이상 떨어뜨려 놓는다. 따라서 $i$번과 $j$번의 거리는 $\max(A_i, A_j)$ 이상이다.

등산객은 한 번에 한 명씩 움직인다. 한 번의 이동은 한 사람을 지금 서 있는 표지점에서 다음 표지점으로 옮기고 순식간에 끝나므로, 표지점 사이에 머무는 사람은 없다. 이동이 끝날 때마다 두 규칙이 다시 성립해야 한다.

$P$번 표지점에 닿은 등산객은 코스를 완주하고 곧바로 빠져나간다. 그 순간부터 두 규칙은 그 사람을 무시하므로, $P$번 표지점으로 가는 이동은 언제나 허용된다. 처음부터 $P$번 표지점에 서 있는 등산객은 이미 완주한 상태이고 한 번도 움직이지 않는다.

모두가 코스를 완주하도록 움직이는 순서를 구하라.

• 첫째 줄에 정수 $B$ ($1 \le B \le 50000$)가 주어진다. 이웃한 두 등산객 사이에 허용되는 가장 먼 거리다.
• 둘째 줄에 표지점의 개수 $P$ ($3 \le P \le 1000$)가 주어진다.
• 셋째 줄에 정수 $P$개 $d_1, d_2, \ldots, d_P$ ($0 = d_1 < d_2 < \cdots < d_P \le 10^6$)가 주어진다. 각 표지점의 출발점에서의 거리다.
• 넷째 줄에 등산객의 수 $K$ ($2 \le K \le 1000$)가 주어진다.
• 이어지는 $K$개 줄 중 $i$번째 줄에 $i$번 등산객의 개인 공간 $A_i$와 현재 표지점 번호 $V_i$가 공백으로 구분되어 주어진다 ($1 \le A_i \le 10^6$, $1 \le V_i \le P$). 등산객은 출발점에서 가까운 순서로 주어지므로 $V_1 < V_2 < \cdots < V_K$이다.

처음 배치는 두 규칙을 모두 만족한다. $P$번 표지점에서 시작하는 등산객은 이미 완주했으므로 이 판정에서 빠진다.

규칙을 어기지 않고는 모든 등산객을 $P$번 표지점까지 보낼 수 없으면 impossible을 출력한다.

보낼 수 있으면 움직이는 순서대로 등산객 번호를 한 줄에 공백 하나로 구분해 출력한다. 올바른 답의 길이는 항상 $\sum_{i=1}^{K} (P - V_i)$로 같으니, 그중 사전순으로 가장 작은 답을 출력한다. 두 답은 앞에서부터 한 자리씩 비교하고, 처음으로 달라지는 자리의 번호가 작은 쪽이 사전순으로 앞선다.