Berland Elections

오늘 Berland 의회 선거가 진행되고 있다. 투표가 한창이다!

후보자는 총 n명이며, 1부터 n까지 번호가 매겨져 있다. 선거 결과에 따라 상위 k (1 ≤ k ≤ n)명의 후보자가 의회 의석을 차지한다.

투표가 끝난 뒤 각 후보자가 받은 표의 수를 계산한다. 결과 표에서 후보자는 득표수에 따라 정렬된다. 동률인 경우(득표수가 같은 경우) 마지막 표를 받은 시각에 따라 정렬된다. 마지막 표를 더 일찍 받은 후보자가 결과 표에서 더 높은 순위에 놓인다.

따라서 결과 표에서 후보자는 득표수에 따라 정렬되며(득표수가 많을수록 순위가 높다), 두 후보자의 득표수가 같다면 마지막 표를 받은 시각에 따라 정렬된다(마지막 표를 더 일찍 받았을수록 순위가 높다).

득표수가 영인 후보자는 의회 의석을 차지할 수 없다. 따라서 의석을 차지하는 후보자가 k명보다 적을 수도 있다.

In Berland 투표할 수 있는 시민은 m명이다. 각 시민은 어떤 후보자에게 투표한다. 각 시민은 n명의 후보자 중 정확히 한 명에게 표를 준다. 선거에는 "against everyone"라는 선택지가 없다. 투표용지를 무효로 만들거나 선거에 참여하지 않는 것은 허용되지 않는다. 따라서 m명의 시민 각각은 n명의 후보자 중 정확히 한 명에게 투표한다.

현재 a명의 시민이 이미 투표했다 (1 ≤ a ≤ m). 이 선거는 공개 선거이므로 각 시민이 어느 후보자에게 투표했는지 알려져 있다. 형식적으로, j-th 시민은 후보자 gj에게 투표했다. 이미 투표한 시민들은 시간순으로 번호가 매겨져 있다. 즉, (j + 1)-th 시민은 j-번째 시민보다 나중에 투표했다.

남은 m - a명의 시민은 선거가 끝나기 전에 투표하며, 각자 n명의 후보자 중 한 명에게 투표한다.

여러분의 과제는 n명의 후보자 각각에 대해 다음 세 가지 가능한 결과 중 하나를 판정하는 것이다:

• 남은 m - a명의 시민이 어떻게 투표하든 후보자가 의회에 선출된다;
• n명의 시민이 모두 투표한 뒤 후보자가 의회에 선출될 가능성이 있다;
• 남은 m - a명의 시민이 어떻게 투표하든 후보자가 의회에 선출될 가능성이 없다.

첫째 줄에 네 정수 n, k, m, a (1 ≤ k ≤ n ≤ 100, 1 ≤ m ≤ 100, 1 ≤ a ≤ m)가 주어진다. 이는 각각 후보자 수, 의회 의석 수, Berland 시민 수, 이미 투표한 시민 수이다.

둘째 줄에 a개의 정수로 이루어진 수열 g1, g2, ..., ga (1 ≤ gj ≤ n)가 주어진다. 여기서 gj는 j-th 시민이 투표한 후보자이다. 이미 투표한 시민들은 투표 시각이 빠른 순서대로 번호가 매겨져 있다.

n개의 정수 r1, r2, ..., rn으로 이루어진 수열을 출력한다. 각 값의 의미는 다음과 같다:

• ri = 1은 남은 m - a명의 시민이 어떻게 투표하든 i-th 후보자가 의회 의석을 차지하는 것이 보장됨을 의미한다;
• ri = 2는 i-th 후보자가 의회 의석을 차지할 가능성이 있음을 의미한다. 즉, 남은 m - a명의 시민이 해당 후보자가 의회 의석을 차지하도록 투표하는 방법이 존재한다;
• ri = 3은 남은 m - a명의 시민이 어떻게 투표하든 i-th 후보자가 의회 의석을 차지하지 못함을 의미한다.