F. Выборы в Берляндии
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сегодня — выборы в парламент Берляндии. Голосование в самом разгаре!

Всего в выборах принимают участие n кандидатов; будем считать, что они занумерованы числами от 1 до n. По результатам выборов k (1 ≤ k ≤ n) кандидатов, показавших наилучший результат на выборах, будут избраны в парламент.

Результаты выборов определяются следующим образом. По окончании голосования для каждого кандидата подсчитывается количество отданных за него голосов. Чем больше голосов набрал кандидат, тем выше место он займет в таблице результатов. Если два или более кандидатов набрали одинаковое количество голосов, то выше место в таблице результатов занимает кандидат, последний голос за которого был отдан раньше.

Таким образом, при формировании таблицы результатов кандидаты упорядочиваются по невозрастанию количества отданных за них голосов, а при равном количестве отданных за них голосов — по возрастанию времени, в которое был отдан последний голос за этого кандидата.

Если за кандидата не отдан ни один голос, то он не считается избранным ни при каких условиях. Таким образом, возможно что менее чем k кандидатов будут избраны в парламент.

В Берляндии m жителей имеют право голоса, и каждый из них обязательно примет участие в голосовании. Каждый из жителей отдаст свой голос за одного из n кандидатов. Варианта «против всех» в бюллетене нет, портить бюллетени или не ходить на выборы в Берляндии не принято. Таким образом, каждый из m жителей должен проголосовать за одного из n кандидатов.

К настоящему моменту уже проголосовали a (1 ≤ a ≤ m) жителей Берляндии. Бюллетени в Берляндии именные и мгновенно обрабатываются в момент голосования, поэтому для j-го проголосовавшего уже известен номер кандидата gj, за которого он отдал свой голос. Проголосовавшие жители нумеруются в хронологическом порядке; то есть (j + 1)-й житель голосовал позже j-го.

Оставшиеся m - a жителей проголосуют до окончания выборов, каждый из них отдаст голос за какого-то из n кандидатов.

Ваша задача — определить для каждого из n кандидатов один из трёх возможных исходов:

  • кандидат уже может считаться избранным в парламент независимо от распределения голосов оставшихся m - a жителей;
  • кандидат имеет возможность быть избранным в парламент после подведения итогов выборов;
  • кандидат не может быть избранным в парламент независимо от распределения голосов оставшихся m - a жителей.
Входные данные

В первой строке содержатся четыре целых числа n, k, m и a (1 ≤ k ≤ n ≤ 100, 1 ≤ m ≤ 100, 1 ≤ a ≤ m) — количество кандидатов, количество мест в парламенте, количество жителей Берляндии и количество уже проголосовавших жителей.

Во второй строке содержится последовательность из a целых чисел g1, g2, ..., ga (1 ≤ gj ≤ n), где gj — номер кандидата, за которого отдал голос j-й из уже проголосовавших жителей. Проголосовавшие жители нумеруются в порядке возрастания времени голосования.

Выходные данные

Выведите последовательность из n целых чисел r1, r2, ..., rn, где:

  • ri = 1, если i-й кандидат гарантированно будет избран в парламент независимо от распределения голосов оставшихся m - a жителей;
  • ri = 2, если i-й кандидат имеет шанс быть избранным в парламент, то есть оставшиеся m - a жителей могут проголосовать таким образом, что он будет избран в парламент;
  • ri = 3, если i-й кандидат не будет избран в парламент независимо от распределения голосов оставшихся m - a жителей.
Примеры
Входные данные
3 1 5 4
1 2 1 3
Выходные данные
1 3 3
Входные данные
3 1 5 3
1 3 1
Выходные данные
2 3 2
Входные данные
3 2 5 3
1 3 1
Выходные данные
1 2 2