---------- 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 ``` ---------------------------------- <details class="blue"> <summary> راهنمایی ۱ </summary> حل این مسئله به ایده‌ی تئوری سختی نیاز ندارد و صرفا حریصانه عمل می‌کنیم. در هر مرحله همه‌ی افراد را چک می‌کنیم و اگر کسی بود که می‌توانستیم او را یک ایستگاه به جلو ببریم، این کار را انجام می‌دهیم و افراد دیگر را چک نمی‌کنیم. تعداد بارهایی که ما یک نفر را جلو می‌بریم حداکثر ${p^2}$ مرحله است و هر دفعه هم برای پیدا کردن فردا داریم یک فور $O(p)$ می‌زنیم. تا این‌جا تایم برنامه خیلی بد نیست چون احتمالا برای جلو بردن یک فرد نباید در هر مرحله هر $p$ نفر را چک نخواهیم کرد ولی خب در صورت پیاده‌سازی بد ممکن است این راه تایم شود. ایده‌ای می‌زنیم تا تایم برنامه‌ را بهبود بخشیم. به این صورت عمل می‌کنیم که در هر مرحله همه‌ی افراد را چک می‌کنیم و هر کسی که می‌توانست جلو برود را جلو می‌بریم. در واقع در هر مرحله دقیقا هر $p$ نفر را چک می‌کنیم ولی احتمالا به جای یک نفر چند نفر به جلو خواهند رفت. اثبات خوب بودن این بهینه‌سازی در تئوری ممکن نیست یا خیلی سخت است اما همه‌ی ما شهود داریم که در هر مرحله واقعا ممکن است تعداد بیشتر از یک نفر بتوانند یک ایستگاه به جلو بروند و این موضوع در عمل هم مشاهده می‌شود (اگر به اندازه‌ي کافی شهود ندارید برای خود چند مثال بزنید تا متوجه خوب بودن الگوریتممان شوید). بنابراین قسمت اصلی این سوال پیاده‌سازی کد آن است ولی این ایده که در هر مرحله هر چند نفری که می‌توانستند را به جلو حرکت دهید، تایم برنامه‌ی شما را بسیار بهبود خواهد بخشید. </details>

H: Hiker

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🔗

Sample Output 3🔗

impossible

راهنمایی ۱

حل این مسئله به ایده‌ی تئوری سختی نیاز ندارد و صرفا حریصانه عمل می‌کنیم. در هر مرحله همه‌ی افراد را چک می‌کنیم و اگر کسی بود که می‌توانستیم او را یک ایستگاه به جلو ببریم، این کار را انجام می‌دهیم و افراد دیگر را چک نمی‌کنیم. تعداد بارهایی که ما یک نفر را جلو می‌بریم حداکثر ${p^2}$ مرحله است و هر دفعه هم برای پیدا کردن فردا داریم یک فور $O(p)$ می‌زنیم. تا این‌جا تایم برنامه خیلی بد نیست چون احتمالا برای جلو بردن یک فرد نباید در هر مرحله هر $p$ نفر را چک نخواهیم کرد ولی خب در صورت پیاده‌سازی بد ممکن است این راه تایم شود.

ایده‌ای می‌زنیم تا تایم برنامه‌ را بهبود بخشیم. به این صورت عمل می‌کنیم که در هر مرحله همه‌ی افراد را چک می‌کنیم و هر کسی که می‌توانست جلو برود را جلو می‌بریم. در واقع در هر مرحله دقیقا هر $p$ نفر را چک می‌کنیم ولی احتمالا به جای یک نفر چند نفر به جلو خواهند رفت. اثبات خوب بودن این بهینه‌سازی در تئوری ممکن نیست یا خیلی سخت است اما همه‌ی ما شهود داریم که در هر مرحله واقعا ممکن است تعداد بیشتر از یک نفر بتوانند یک ایستگاه به جلو بروند و این موضوع در عمل هم مشاهده می‌شود (اگر به اندازه‌ي کافی شهود ندارید برای خود چند مثال بزنید تا متوجه خوب بودن الگوریتممان شوید).

بنابراین قسمت اصلی این سوال پیاده‌سازی کد آن است ولی این ایده که در هر مرحله هر چند نفری که می‌توانستند را به جلو حرکت دهید، تایم برنامه‌ی شما را بسیار بهبود خواهد بخشید.