Задача №114093. Олимпиада
Все олимпиады, упоминаемые в данном условии, являются вымышленными. Любое совпадение с какой-либо реально существующей олимпиадой является случайным и не умышленным.
Длинный отборочный тур Открытой олимпиады школьников подошёл к концу, и настало время объявить список участников короткого тура.
Как известно, отбор на заключительный этап Открытой олимпиады производится по сумме результатов длинного и короткого отборочных туров: участники сортируются по убыванию суммы баллов, полученных ими на длинном и коротком отборочных турах, и в заключительный этап олимпиады проходят участники, набравшие не меньше баллов, чем участник на \(p\)-м месте по сумме результатов отборочных туров.
Можно заметить, что не всех участников длинного отборочного тура следует приглашать на короткий: некоторые участники пройдут на заключительный этап даже если не будут участвовать в коротком туре (в этом случае их результат в коротком туре равен \(0\) баллам), а некоторые участники не пройдут на заключительный этап даже если наберут на коротком туре полный балл. Остальные участники могут как пройти, так и не пройти на заключительный этап олимпиады в зависимости от своих результатов на коротком туре и результатов других участников на этом туре. Именно таких участников, для которых ещё не определён однозначно статус прохода или не прохода на заключительный этап, хочет пригласить на короткий тур жюри олимпиады.
Помогите жюри олимпиады и сообщите, каких участников следует пригласить на короткий тур.
В первой строке заданы три целых числа \(n\), \(p\) и \(c\) (\(1 \leq p \leq n \leq 100\,000, 1 \leq c \leq 10^9\)) — количество участников длинного тура, номер места участника по сумме баллов, которое определяет границу прохода на заключительный этап, и максимальное количество баллов, которое можно набрать на коротком туре соответственно.
В следующих \(n\) строках описываются результаты участников на длинном туре. В строке с номером \(i + 1\) содержится одно целое число \(a_i\) (\(0 \leq a_i \leq 10^9\)) — количество баллов, которое участник с номером \(i\) набрал на длинном туре.
Выведите \(n\) строк. В строке с номером \(i\) выведите информацию об участнике с номером \(i\).
Выведите « Pass » (без кавычек), если участник с номером \(i\) пройдёт на заключительный этап олимпиады вне зависимости от результатов короткого тура.
Выведите « Short » (без кавычек), если участник с номером \(i\) может как пройти, так и не пройти на заключительный этап олимпиады в зависимости от результатов короткого тура.
Выведите « Fail » (без кавычек), если участник с номером \(i\) не пройдёт на заключительный этап олимпиады вне зависимости от результатов короткого тура.
В первом примере участник набравший \(50\) баллов займёт первое место, даже если наберёт \(0\) баллов на коротком туре, а все остальные участники наберут \(10\) баллов, поэтому он пройдёт на заключительный этап в любом случае. Участник, набравший \(0\) баллов займёт четвёртое место, даже если получит \(10\) баллов на коротком туре, а все остальные участники получат \(0\) баллов. Проход участников, набравших \(30\) и \(29\) баллов зависит от их результатов на коротком туре.
Во втором примере есть две возможные ситуации. Если участник, набравший \(20\) баллов, наберёт менее \(10\) баллов на коротком туре, то он будет ниже двух участников, набравших \(30\) баллов и не пройдёт на заключительный этап. Если же участник, набравший \(20\) баллов, получит \(10\) баллов на коротком туре, а остальные участники получат \(0\) баллов, то все три участника пройдут на заключительный этап.
Тесты к этой задаче состоят из двух групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
4 2 10 30 29 50 0
Short Short Pass Fail
3 2 10 30 20 30
Pass Short Pass