The elections to Berland parliament are happening today. Voting is in full swing!

Totally there are n candidates, they are numbered from 1 to n. Based on election results k (1 ≤ k ≤ n) top candidates will take seats in the parliament.

After the end of the voting the number of votes for each candidate is calculated. In the resulting table the candidates are ordered by the number of votes. In case of tie (equal number of votes) they are ordered by the time of the last vote given. The candidate with ealier last vote stands higher in the resulting table.

So in the resulting table candidates are sorted by the number of votes (more votes stand for the higher place) and if two candidates have equal number of votes they are sorted by the time of last vote (earlier last vote stands for the higher place).

There is no way for a candidate with zero votes to take a seat in the parliament. So it is possible that less than k candidates will take a seat in the parliament.

In Berland there are m citizens who can vote. Each of them will vote for some candidate. Each citizen will give a vote to exactly one of n candidates. There is no option "against everyone" on the elections. It is not accepted to spoil bulletins or not to go to elections. So each of m citizens will vote for exactly one of n candidates.

At the moment a citizens have voted already (1 ≤ a ≤ m). This is an open election, so for each citizen it is known the candidate for which the citizen has voted. Formally, the j-th citizen voted for the candidate gj. The citizens who already voted are numbered in chronological order; i.e. the (j + 1)-th citizen voted after the j-th.

The remaining m - a citizens will vote before the end of elections, each of them will vote for one of n candidates.

Your task is to determine for each of n candidates one of the three possible outcomes:

  * a candidate will be elected to the parliament regardless of votes of the remaining m - a citizens; 
  * a candidate has chance to be elected to the parliament after all n citizens have voted; 
  * a candidate has no chances to be elected to the parliament regardless of votes of the remaining m - a citizens. 

Input

The first line contains four integers n, k, m and a (1 ≤ k ≤ n ≤ 100, 1 ≤ m ≤ 100, 1 ≤ a ≤ m) — the number of candidates, the number of seats in the parliament, the number of Berland citizens and the number of citizens who already have voted.

The second line contains a sequence of a integers g1, g2, ..., ga (1 ≤ gj ≤ n), where gj is the candidate for which the j-th citizen has voted. Citizens who already voted are numbered in increasing order of voting times.

Output

Print the sequence consisting of n integers r1, r2, ..., rn where:

  * ri = 1 means that the i-th candidate is guaranteed to take seat in the parliament regardless of votes of the remaining m - a citizens; 
  * ri = 2 means that the i-th candidate has a chance to take a seat in the parliament, i.e. the remaining m - a citizens can vote in such a way that the candidate will take a seat in the parliament; 
  * ri = 3 means that the i-th candidate will not take a seat in the parliament regardless of votes of the remaining m - a citizens. 

Examples

Input

3 1 5 4
1 2 1 3


Output

1 3 3 

Input

3 1 5 3
1 3 1


Output

2 3 2 

Input

3 2 5 3
1 3 1


Output

1 2 2 
import java.io.*;
import java.util.*;
import java.util.stream.IntStream;

public class Solution {


    static MyScanner sc;
    private static PrintWriter out;
    static long M = 1000000007;


    public static void main(String[] s) throws Exception {
        StringBuilder stringBuilder = new StringBuilder();
//
//        stringBuilder.append("250 250 1000000 1 ");
//
//        for (int i = 0; i < 250; i++) {
//            for (int j = 0; j < 250; j++) {
//                stringBuilder.append('Z');
//            }
//            stringBuilder.append('\n');
//        }


        if (stringBuilder.length() == 0) {
            sc = new MyScanner(System.in);
        } else {
            sc = new MyScanner(new BufferedReader(new StringReader(stringBuilder.toString())));
        }

        out = new PrintWriter(new OutputStreamWriter(System.out));

        initData();
        solve2();
        out.flush();
    }


    private static void initData() {
    }

    private static void solve() throws IOException {
        int n = sc.nextInt();
        int l = sc.nextInt();
        int[][] k = new int[l][3];

        int[] ct = new int[n];
        for (int i = 0; i < l; i++) {
            k[i][0] = sc.nextInt() - 1;
            k[i][1] = sc.nextInt() - 1;
            ct[k[i][0]]++;
            ct[k[i][1]]++;
        }
        if (l == 0) {
            out.println(0);
            return;
        }
        int left = 0;
        int right = l;

        while (left + 1 < right) {
            int m = (left + right) / 2;
            if (valid(m, k, n)) {
                right = m;
            } else {
                left = m;
            }
        }
        out.println(right);
        boolean [] vis = new boolean[n];
        for (int i = 0; i < n; i++) {
            int cur = -1;
            for (int rt = 0; rt < n; rt++) {
                if (ct[rt] == 0|| vis[rt]) continue;

                if (cur == -1 || ct[rt] > ct[cur]) cur = rt;
            }


            if (cur == -1) break;
            vis[cur] = true;
            int kk = 0;
            for (int [] p : k) {
                if (kk >= right) break;
                if (p[2] == 1) continue;

                if (p[0] == cur || p[1] == cur) {
                    p[2] = 1;
                    kk++;
                    out.print(cur + 1);
                    out.print(' ');
                    out.print(p[0] + p[1] - cur + 1);
                    out.println();
                }
            }
        }



    }

    private static boolean valid(int m, int[][] k, int n) {
        Node s = new Node();
        Node t = new Node();

        Node[][] tr = new Node[n][2];
        for (int l = 0; l < n; l++) {
            tr[l][0] = new Node();
            tr[l][1] = new Node();
            tr[l][1].next.put(tr[l][0], 1);
            tr[l][1].next.put(t, m);
            s.next.put(tr[l][0], m);
        }

        for (int[] r : k) {
            tr[r[0]][0].next.put(tr[r[1]][1], 1);
            tr[r[1]][0].next.put(tr[r[0]][1], 1);
        }

        return Path.res(s, t) >= k.length;
    }

    private static void solve2() throws IOException {
        int n = sc.nextInt();
        int k = sc.nextInt();
        int m = sc.nextInt();
        int a = sc.nextInt();
        int[][] r = new int[n][3];
        for (int i = 0; i < n; i++) {
            r[i][0] = i;
            r[i][2] = -1;
        }
        for (int p = 0; p < a; p++) {
            int x = sc.nextInt();
            r[x - 1][1]++;
            r[x - 1][2] = p;
        }
        Arrays.sort(r, (t1, t2) -> t1[1] == t2[1] ? t1[2] - t2[2] : t2[1] - t1[1]);

        int[] res = new int[n];
        Arrays.fill(res, 3);
        if (m == a) {
            for (int tt = 0; tt < k; tt++) {
                if (r[tt][1] == 0) break;
                res[r[tt][0]] = 1;
            }
        } else {
            int i = 0;
            for (; i < k; i++) {
                if (r[i][1] == 0)break;
                int x = i + 1;
                int cur = m - a;
                for (; x < n; x++) {
                    cur -= r[i][1] - r[x][1];
                    if (r[i][1] > 0) cur--;
                    if (cur < 0) {
                        break;
                    }
                }
                x--;
                if (x >= k) {
                    break;
                }
                res[r[i][0]] = 1;
            }
            for (; i < n; i++) {
                int x = i - 1;

                while (x >= 0) {
                    int cur = m - a;
                    cur -= r[x][1] - r[i][1] ;
                    if (r[x][1] > 0) cur--;
                    if (cur < 0) {
                        break;
                    }
                    x--;
                }
                x++;
                if (x >= k) {
                    break;
                }
                res[r[i][0]] = 2;
            }

        }
        for (int i : res) {
            out.print(i);
            out.print(" ");
        }

//        System.out.println(Arrays.deepToString(r));
    }

    private static final class Path {
        Node to;
        int val = Integer.MAX_VALUE;
        private Path prev;

        public Path() {
        }

        public Path(Path value, Node key, int curVal) {
            val = Math.min(value.val, curVal);
            prev = value;
            to = key;
        }

        static Path find(Node sn, Node tn) {
            Set<Node> visited = new HashSet<>();
            LinkedList<NodePath> toVisit = new LinkedList<>();
            toVisit.add(new NodePath(sn, new Path()));
            while (!toVisit.isEmpty()) {
                NodePath next = toVisit.removeLast();
                for (Map.Entry<Node, Integer> val : next.node.next.entrySet()) {
                    if (val.getKey() == tn) {
                        return new Path(next.path, val.getKey(), val.getValue());
                    }
                    if (visited.contains(val.getKey())) {
                        continue;
                    }
                    visited.add(val.getKey());
                    toVisit.add(new NodePath(val.getKey(), new Path(next.path, val.getKey(), val.getValue())));
                }
            }
            return null;
        }

        private static final class NodePath {
            Node node;
            Path path;

            public NodePath(Node node, Path path) {
                this.node = node;
                this.path = path;
            }
        }

        static int res(Node sn, Node tn) {
            int result = 0;
            Path path = null;
            while ((path = find(sn, tn)) != null) {

                result += path.getValue();
                path.affect(sn);

            }
            return result;
        }

        public int getValue() {
            return val;
        }

        public void affect(Node sn) {
            affect(sn, val);
        }

        private void affect(Node sn, int val) {
            Node prev1 = prev.to;
            if (prev1 == null) {
                prev1 = sn;
            }
            int prevVal = prev1.next.get(to);
            if (prevVal > val) {
                prev1.next.put(to, prevVal - val);
            } else {
                prev1.next.remove(to);
            }
            to.next.put(prev1, to.next.getOrDefault(prev1, 0) + val);

            if (prev.to != null) {
                prev.affect(sn, val);
            }
        }
    }

    private static final class Node {
        private final String name;
        private HashMap<Node, Integer> next = new HashMap<>();

        public Node() {
            this.name = null;
        }

        public Node(String s) {
            this.name = s;
        }
    }


    private static void solveT() throws IOException {
        int t = sc.nextInt();
        while (t-- > 0) {
            solve();
        }
    }


    private static long gcd(long l, long l1) {
        if (l > l1) return gcd(l1, l);
        if (l == 0) return l1;
        return gcd(l1 % l, l);
    }

    private static long pow(long a, long b, long m) {
        if (b == 0) return 1;
        if (b == 1) return a;
        long pp = pow(a, b / 2, m);
        pp *= pp;
        pp %= m;
        return (pp * (b % 2 == 0 ? 1 : a)) % m;
    }


    static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        MyScanner(BufferedReader br) {
            this.br = br;
        }

        public MyScanner(InputStream in) {
            this(new BufferedReader(new InputStreamReader(in)));
        }

        void findToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
        }

        String next() {
            findToken();
            return st.nextToken();
        }

        Integer[] nab(int n) {
            Integer[] k = new Integer[n];
            for (int i = 0; i < n; i++) {
                k[i] = sc.fi();
            }
            return k;
        }

        int[] na(int n) {
            int[] k = new int[n];
            for (int i = 0; i < n; i++) {
                k[i] = sc.fi();
            }
            return k;
        }

        long[] nl(int n) {
            long[] k = new long[n];
            for (int i = 0; i < n; i++) {
                k[i] = sc.nextLong();
            }
            return k;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int fi() {
            String t = next();
            int cur = 0;
            boolean n = t.charAt(0) == '-';
            for (int a = n ? 1 : 0; a < t.length(); a++) {
                cur = cur * 10 + t.charAt(a) - '0';
            }
            return n ? -cur : cur;
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }

}