---------- Times are hard at the Association of Chartered Mountaineers. The growth of their pedestrian sport has slowed to a crawl. Instead of taking up mountaineering, younger potentials are gravitating towards warmer indoor activities such as snooker, musical chairs, and programming contests. To win over more members, the Association is going to organise a series of new time trial orienteering events next year. The route for the first race will be a short run through the Cairngorms, with every contestant following the same route designated by marker points but all starting at different times. Because hiking can be dangerous, and many of the contestants will be inexperienced, the competition committee drew up two rules: - Every contestant needs to keep a specific maximum distance away from the next-closest contestant, in either direction, at all times. - Every contestant should be given personal space. If a contestant needs a personal space of $D$ metres, nobody else should ever come closer than that at any time. This distance varies according to level of experience. The hardest part of orienteering is the pathfinding; once a contestant knows where to go next, they can get there in almost no time (for the purposes of this problem, instantaneously). In fact, while the inaugural ACM "Icy-Cold Peak Contest" is already underway, pathfinding is turning out to be a problem: nobody is sure whether they can move next without breaking any of the conditions on minimum and maximum distance. Help the runners reach the end of their route by computing a list of who should move to the next goal point, and at what time. # Input - One line containing an integer $B$ ($1 \le B \le 50000$), the maximum separation allowed between any two runners. - One line containing an integer $P$ ($3 \le P \le 1000$), the number of marker points along the route. - One line containing $P$ unique space-separated integers $d_1 ... d_P$ ($0 \le d_i \le 10^6$), with $d_i$ being the distance of the $i$-th vertex from the starting point $d_1 = 0$. - One line containing an integer $K$ ($2 \le K \le 1000$), the number of hikers on the landscape. - $K$ further lines, each containing the pair of space-separated integers $A_i$ and $V_i$ ($1 \le A_i \le 10^6; 1 \le V_i \le P$), the minimum separation distance and current marker position respectively for the $i$-th person. The initial configuration of hikers will be legal according to the minimum and maximum distance rules. The hikers will be given in increasing order of distance from the start. # Output If it is not possible to get everyone to the end of the route without breaking minimum or maximum distance requirements, output impossible. Otherwise, output a space-separated list of moves on one line, each describing which person should make the next move. If anyone falls off the landscape, your answer will not be judged as correct. However, once someone has arrived at the end of their journey they cease to count towards any rule violations. ## Sample Input 1 ``` 3 8 0 1 2 3 4 5 6 7 2 2 1 2 4 ``` ## Sample Output 1 ``` 1 2 1 2 1 2 1 2 1 1 1 ``` ## Sample Input 2 ``` 10 10 0 1 3 6 10 14 17 19 20 21 3 3 1 1 3 3 5 ``` ## Sample Output 2 ``` 2 1 1 3 2 1 3 2 1 3 3 2 1 3 2 2 1 2 1 1 1 ``` ## Sample Input 3 ``` 5 5 0 2 5 9 14 2 2 1 2 2 ``` ## Sample Output 3 ``` impossible ```

حل سؤال در بانک سؤالات