Задача №114152. Честное столовластие
После разработки закона о введении налога на постройку зданий выше двух этажей у N чиновников короля Маркеля Весёлого осталось K бюджетных золотых монет. Эти деньги они решили частично поделить между собой. Поскольку на службе у Короля состоят лишь честные чиновники, делить их они решили справедливо. Они знают, какой вклад w i внес в законопроект i -й чиновник. Деньги должны быть распределены так, что если i -й чиновник получил c i монет, а j -й — c j монет, то числа c i и c j должны иметь такой же результат сравнения, как числа w i и w j . Это значит, что c i < c j должно быть верно тогда и только тогда, когда w i < w j . В частности, из этого следует, что при равенстве вкладов чиновники должны получить одинаковое количество монет.
Среди чиновников у короля Маркеля Весёлого есть некоторое количество фаворитов. Он хочет, чтобы фаворит с минимальным вкладом в законопроект получил в итоге как можно больше денег. Помогите честным госслужащим разделить деньги по справедливости, соблюдая требование короля Маркеля. Заметьте, что в задачу не входит максимизация прибыли чиновников, не являющихся фаворитами Маркеля Весёлого.
В первой строке следуют целое положительное число N и два целых неотрицательных числа M и K , разделённых пробелами — количество чиновников, количество фаворитов Маркеля и количество монет для раздела соответственно ( M ≤ N ≤ 10 5 , K ≤ 10 18 ).
Во второй строке находятся N целых положительных чисел w i , разделённых пробелами ( 1 ≤ w i ≤ 10 9 ). i -е из них обозначает вклад, который привнес i -й чиновник.
В третьей строке записаны M различных натуральных чисел f i — номера чиновников, являющихся фаворитами короля ( 1 ≤ f i ≤ N ).
Если справедливое распределение монет существует, первой строкой выведите слово « POSSIBLE » (без кавычек). Второй же строкой выведите N целых неотрицательных чисел через пробел. i -е из них должно равняться количеству монет, которые получит i -й чиновник.
Помните, что раздавать все монеты не обязательно, а Маркель Весёлый волнуется только о том, чтобы фаворит с минимальным вкладом (а значит и минимальным количеством монет) получил как можно больше, а в остальном чиновники вольны распределять монеты как угодно. Это значит, что и вы можете вывести любой правильный ответ.
Если же поделить деньги справедливо невозможно, выведите слово « IMPOSSIBLE » (без кавычек).
Обратите внимание, что некоторая часть денег может остаться неподелённой. В первом примере входных данных излишек монет можно было бы также раздать второму и пятому чиновнику, но, так как они не являются фаворитами короля, делать это не обязательно.
Во втором примере входных данных корректный делёж потребует не менее четырёх монет, тогда как их осталось всего три.
Тесты к этой задаче состоят из четырёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп .
5 2 15 15 2 33 12 8 3 4
POSSIBLE 4 0 5 3 1
4 2 3 1 2 3 2 1 2
IMPOSSIBLE