Задача №2818. Подтасовка результатов
В городе Н. олимпиада по информатике состоит из двух туров, каждый из которых оценивается из 400 баллов. Для удобства все её участники занумерованы числами от 1 до N.
Сразу после проведения олимпиады курьер принёс жюри пренеприятнейшее известие: «сверху» пришло указание о том, что некто Вася, выступавший в олимпиаде под номером 1, должен по итогам олимпиады занять место A, то есть ровно A - 1 участников должны набрать по сумме двух туров больше баллов, чем Вася. При этом места, занятые школьниками в каждом из туров в отдельности, уже опубликованы, и их менять нельзя. Для каждого тура дан список номеров участников в порядке занятого места — перестановка чисел от 1 до N. Теперь задача жюри заключается в том, чтобы расставить целые баллы от 1 до 400 каждому участнику в первом и втором турах таким образом, чтобы в итоговой таблице Вася занял место A, а места участников в каждом из туров не изменились.
Никакие два участника не должны получить в одном туре одинаковые баллы. Одинаковые баллы в итоговой таблице возможны.
Ваша задача — проделать за жюри такую работу или определить, что это невозможно.
В первой строке вводятся два целых числа N, A (1 ≤ N ≤ 200, 1 ≤ A ≤ N) — соответственно количество участников олимпиады и требуемое Васино место. Во второй строке перечислены номера участников в порядке занятых мест в первом туре (от первого места до N-го). В третьей строке в таком же формате следует описание второго тура. Номера участников во второй и третьей строках разделены пробелами.
В случае, если невозможно расставить баллы требуемым образом, выведите единственное слово Impossible. Иначе в первой строке выведите Possible, во второй строке выведите N целых чисел от 1 до 400, соответствующих расстановке баллов участникам первого тура, где i-ое число — балл в первом туре участника, занявшего на нём i-е место, в третьей аналогично выведите N целых чисел, соответствующих расстановке баллов во втором туре. Числа в строках разделяйте пробелами.
Никакие два участника не должны получить одинаковые баллы в одном и том же туре. Если существует несколько способов расставить баллы требуемым образом, выведите любой.
3 1 2 1 3 3 1 2
Possible 3 2 1 3 2 1
3 1 2 3 1 3 1 2
Impossible
5 3 2 3 4 5 1 2 3 1 4 5
Possible 5 4 3 2 1 400 399 398 2 1