Hiker Safety

A hiking club runs a time trial along a single route. The route has $P$ marker points, marker $i$ sits $d_i$ metres from the start, and $d_1 = 0$. The slow part of this sport is the pathfinding, so once a hiker knows where to go next, the walk itself takes no time at all.

$K$ hikers are on the route. Hiker $i$ stands on marker $V_i$ and needs $A_i$ metres of personal space. Two rules hold at every moment.

• Two hikers that are neighbours on the route, meaning no other hiker stands between them, are at most $B$ metres apart.
• Hiker $i$ keeps everyone else at least $A_i$ metres away, so the distance between hiker $i$ and hiker $j$ is at least $\max(A_i, A_j)$.

The hikers move one at a time. A single move takes one hiker from the marker they stand on to the next marker and finishes instantly, so nobody is ever between two markers. Both rules hold again after every move.

A hiker who reaches marker $P$ has finished the route and leaves it at once. From that moment the two rules ignore that hiker, so a move onto marker $P$ is always allowed. A hiker who stands on marker $P$ at the start has already finished and never moves.

Work out the order in which the hikers move so that all of them finish the route.

• One line with the integer $B$ ($1 \le B \le 50000$), the largest distance allowed between two neighbouring hikers.
• One line with the integer $P$ ($3 \le P \le 1000$), the number of marker points.
• One line with $P$ integers $d_1, d_2, \ldots, d_P$ ($0 = d_1 < d_2 < \cdots < d_P \le 10^6$), the distance of each marker from the start.
• One line with the integer $K$ ($2 \le K \le 1000$), the number of hikers.
• $K$ lines, the $i$-th of which holds two integers $A_i$ and $V_i$ ($1 \le A_i \le 10^6$, $1 \le V_i \le P$), the personal space and the current marker of hiker $i$. The hikers are listed from the start of the route onwards, so $V_1 < V_2 < \cdots < V_K$.

The starting arrangement obeys both rules. A hiker who starts on marker $P$ has already finished and is left out of that check.

If the hikers cannot all reach marker $P$ without breaking a rule, print impossible.

Otherwise print the hiker numbers in the order they move, separated by single spaces, on one line. Every correct answer has the same length $\sum_{i=1}^{K} (P - V_i)$, so print the lexicographically smallest one. Compare two answers one position at a time; the answer with the smaller number at the first position where they differ comes first.