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.*;

public class Main
{
	private InputStream is;
	private PrintWriter out;
	int time = 0, DP[], start[], end[], dist[], black[], MOD = (int) (1e9 + 7),
			arr[], weight[][], x[], y[], parent[];
	int MAX = 100000, N, K;
	long red[],ans = Long.MAX_VALUE;
	
	ArrayList<Character>[] amp;
	ArrayList<Pair>[] pmp;
	boolean b[], boo[][];
	Pair prr[];
	HashMap<Pair, Integer> hm = new HashMap();
	long Dp[][][][] = new long[110][110][12][12];

	void soln()
	{
		is = System.in;
		out = new PrintWriter(System.out);
		long s = System.currentTimeMillis();
		solve();
		
		// out.close();
		out.flush();
		// tr(System.currentTimeMillis() - s + "ms");
	}

	public static void main(String[] args) throws Exception 
	{
		new Thread(null, new Runnable() 
		{
			public void run() 
			{
				try
				{
					// new CODEFORCES().soln();
				} catch (Exception e)
				{
					System.out.println(e);
				}
			}
		}, "1", 1 << 26).start();
		new Main().soln();
	}

	int  cost = 0, D[][];
	char ch[], ch1[];
	int hash = 29;
	TreeSet<Cell> ts;
	int x2, y2;
	HashSet<Integer>[] hs = (HashSet<Integer>[]) new HashSet[110];
	void solve()
	{
		int n = ni(), k = ni(), m = ni(), a = ni();
		int arr[] = na(a);
		int cnt[] = new int[n+1];
		int time[] = new int[n+1];
		Arrays.fill(time, 100000);
		for(int i = 0;i<a;i++) {
			cnt[arr[i]]++;
			time[arr[i]] = i;
		}
		int r = m-a;
		if(n==k){
			for(int i = 1; i<=n; i++){
				if(cnt[i]>0)
				System.out.print(1+" ");
				else if(r>0) System.out.println(2+" ");
				else System.out.println(3+" ");
			}
			return;
		}
		Pair prr[] = new Pair[n];
		for(int i = 0; i< n; i++) prr[i] = new Pair(cnt[i+1],time[i+1],i);
		Arrays.sort(prr);
		int ans[] = new int[n];
		Arrays.fill(ans, 3);
		for(int i = 0;i<k;i++){
			int sum = 0;
			//System.out.println(prr[i]);
			if(prr[i].u>0){
			for(int j = i+1;j<=k;j++){
				 sum += prr[j].u;
			}
			if(!(((k-i)*(prr[i].u+1)-sum)<=r)) ans[prr[i].i] = 1;
			}
		}
		for(int i = 0; i< n; i++){
			if(ans[prr[i].i]!=1){
				int x = prr[i].u+r;
				for(int j = 0;j<k;j++){
					if(x>prr[j].u){
						ans[prr[i].i] = 2;
					}
				}
			}
		}
		for(int i : ans) System.out.print(i+" ");
	}
	void ternary_search(int l,int r)
	{ 
		//System.out.println(l+" "+r+" "+ans);
	//	for(int i : arr) System.out.print(i+" ");
	//	System.out.println();
	    if(r>=l)
	    {
	        int mid1 = l + (r-l)/3;
	        int mid2 = r -  (r-l)/3;
	        long cnt1 = 0, cnt2 = 0;
	        cnt1 = compute(mid1);
	        cnt2 = compute(mid2);
	       // System.out.println(mid1+" "+ cnt1+" "+mid2+" "+cnt2);
	        ans = Math.min(cnt1,cnt2);
	        if(cnt1<cnt2){
	        	ternary_search(l, mid2-1);
	        }
	        else{
	        	ternary_search(mid1+1, r);
	        }
	    }
	    return;
	}
	long compute(int x){
		long ans = 0;
		int c = arr[0];
		for(int i = 1; i<=x;i++){
			ans += max(c+1-arr[i],0);
			c = max(c+1,arr[i]);
		}
		int temp = arr[x];
		arr[x] = max(c+1,arr[x]);
		//SSystem.out.println(arr[x]+" "+ans);
		c = arr[arr.length-1];
		for(int i = arr.length-1;i>x;i--){
			ans += max(c+1-arr[i-1],0);
			c = max(c+1,arr[i-1]);
		}
		arr[x] = temp;
		return ans;
	}
	public int getParent(int x) {
		while (parent[x] != x) {
			parent[x] = parent[parent[x]];
			x = parent[x];
		}
		return x;
	}
	void getFactors(int n,int x){
		for(int i = 1;i*i<=n;i++){
			if(n%i==0){
				hs[x].add(i);
				hs[x].add(n/i);
			}
		}
	}
	void recur(int a, int b, int k){
		if(k==0){
			if(a==x2 && b==y2) ans++;
			return;
		}
		recur(a,b+1,k-1);
		recur(a,b-1,k-1);
		recur(a+1,b,k-1);
		recur(a-1,b,k-1);
	}
	int min(int a, int b)
	{
		return (a<b)?a:b;
	}
	private class Cell implements Comparable<Cell>
	{
		int u, v, s;
		public Cell(int u, int v, int s) 
		{	
			this.u = u;
			this.v = v;
			this.s = s;
		}
		public int hashCode() 
		{
			return Objects.hash();
		}
		public int compareTo(Cell other) 
		{
			return (Long.compare(s, other.s) != 0 ? (Long.compare(s, other.s)):(Long.compare(v, other.v)!=0?Long.compare(v, other.v):Long.compare(u, other.u)))
					&((Long.compare(s, other.s) != 0 ? (Long.compare(s, other.s)):(Long.compare(u, other.v)!=0?Long.compare(u, other.v):Long.compare(v, other.u))));
		}
		public String toString()
		{
			return this.u + " " + this.v;
		}
	}

	class Pair implements Comparable<Pair>
	{
		int u, v, i;

		Pair(int u, int v) 
		{
			this.u = u;
			this.v = v;
		}

		Pair(int u, int v, int i) 
		{
			this.u = u;
			this.v = v;
			this.i = i;
		}

		public int hashCode()
		{
			return Objects.hash();
		}

		public boolean equals(Object o)
		{
			Pair other = (Pair) o;
			return ((u == other.u && v == other.v));
		}

		public int compareTo(Pair other)
		{
			// return Integer.compare(val, other.val);
			return Long.compare(other.u, u) != 0 ? (Long.compare(other.u, u)): (Long.compare(v, other.v));//((Long.compare(u, other.u) != 0 ? (Long.compare(u, other.u)): (Long.compare(v, other.v)))
					//&(Long.compare(u, other.v) != 0 ? (Long.compare(u, other.v)): (Long.compare(v, other.u))));
		}

		public String toString()
		{
			return this.u + " " + this.v;
		}
	}

	int max(int a, int b) 
	{
		if (a > b)
			return a;
		return b;
	}

	/*public static class FenwickTree 
	{

		int[] array; // 1-indexed array, In this array We save cumulative
						// information to perform efficient range queries and
						// updates

		public FenwickTree(int size) 
		{
			array = new int[size + 1];
		}

		public int rsq(int ind)
		{
			assert ind > 0;
			int sum = 0;
			while (ind > 0)
			{
				sum += array[ind];
				// Extracting the portion up to the first significant one of the
				// binary representation of 'ind' and decrementing ind by that
				// number
				ind -= ind & (-ind);
			}
			return sum;
		}

		public int rsq(int a, int b) 
		{
			assert b >= a && a > 0 && b > 0;
			return rsq(b) - rsq(a - 1);
		}

		public void update(int ind, int value)
		{
			assert ind > 0;
			while (ind < array.length) 
			{
				array[ind] += value;
				// Extracting the portion up to the first significant one of the
				// binary representation of 'ind' and incrementing ind by that
				// number
				ind += ind & (-ind);
			}
		}

		public int size() 
		{
			return array.length - 1;
		}
	}
*/
	void buildGraph(int n) 
	{
		for (int i = 0; i < n; i++) 
		{
			int x1 = ni(), y1 = ni(), z = ni();
			pmp[x1].add(new Pair(y1,z));
		}
	}

	long modInverse(long a, long mOD2) 
	{
		return power(a, mOD2 - 2, mOD2);
	}

	long power(long x, long y, long m) 
	{
		if (y == 0)
			return 1;
		long p = power(x, y / 2, m) % m;
		p = (p * p) % m;

		return (y % 2 == 0) ? p : (x * p) % m;
	}

	public long gcd(long a, long b) 
	{
		if (b == 0)
			return a;
		return gcd(b, a % b);
	}

	static class ST1 
	{
		int arr[], st[], size;

		
		ST1(int a[]) 
		{
			arr = a.clone();
			size = 10 * arr.length;
			st = new int[size];
			build(0, arr.length - 1, 1);
		}

		void build(int ss, int se, int si) 
		{
			if (ss == se)
			{
				st[si] = arr[ss];
				return;
			}
			int mid = (ss + se) / 2;
			int val = 2 * si;
			build(ss, mid, val);
			build(mid + 1, se, val + 1);
			st[si] = Math.min(st[val], st[val + 1]);
		}

		int get(int ss, int se, int l, int r, int si) 
		{
			if (l > se || r < ss || l > r)
				return Integer.MAX_VALUE;
			if (l <= ss && r >= se)
				return st[si];
			int mid = (ss + se) / 2;
			int val = 2 * si;
			return Math.min(get(ss, mid, l, r, val),
					get(mid + 1, se, l, r, val + 1));
		}
	}

	static class ST 
	{
		int arr[], lazy[], n;

		ST(int a) 
		{
			n = a;
			arr = new int[10 * n];
			lazy = new int[10 * n];
		}

		void up(int l, int r, int val)
		{
			update(0, n - 1, 0, l, r, val);
		}

		void update(int l, int r, int c, int x, int y, int val)
		{
			if (lazy[c] != 0) {
				lazy[2 * c + 1] += lazy[c];
				lazy[2 * c + 2] += lazy[c];
				if (l == r)
					arr[c] += lazy[c];
				lazy[c] = 0;
			}
			if (l > r || x > y || l > y || x > r)
				return;
			if (x <= l && y >= r) 
			
			{
				lazy[c] += val;
				return;
			}
			int mid = l + r >> 1;
			update(l, mid, 2 * c + 1, x, y, val);
			update(mid + 1, r, 2 * c + 2, x, y, val);
			arr[c] = Math.max(arr[2 * c + 1], arr[2 * c + 2]);
		}

		int an(int ind) 
		{
			return ans(0, n - 1, 0, ind);
		}

		int ans(int l, int r, int c, int ind) 
		{
			if (lazy[c] != 0) 
			{
				lazy[2 * c + 1] += lazy[c];
				lazy[2 * c + 2] += lazy[c];
				if (l == r)
					arr[c] += lazy[c];
				lazy[c] = 0;
			}
			if (l == r)
				return arr[c];
			int mid = l + r >> 1;
			if (mid >= ind)
				return ans(l, mid, 2 * c + 1, ind);
			return ans(mid + 1, r, 2 * c + 2, ind);
		}
	}

	public static int[] shuffle(int[] a, Random gen)
	{
		for (int i = 0, n = a.length; i < n; i++)
		{
			int ind = gen.nextInt(n - i) + i;
			int d = a[i];
			a[i] = a[ind];
			a[ind] = d;
		}
		return a;
	}

	long power(long x, long y, int mod) 
	{
		long ans = 1;
		while (y > 0) 
		{
			if (y % 2 == 0) 
			{
				x = (x * x) % mod;
				y /= 2;
			} else 
			{
				ans = (x * ans) % mod;
				y--;
			}
		}
		return ans;
	}

	// To Get Input
	// Some Buffer Methods
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;

	private int readByte()
	{
		if (lenbuf == -1)
			throw new InputMismatchException();
		if (ptrbuf >= lenbuf) 
		{
			ptrbuf = 0;
			try 
			{
				lenbuf = is.read(inbuf);
			} catch (IOException e)
			{
				throw new InputMismatchException();
			}
			if (lenbuf <= 0)
				return -1;
		}
		return inbuf[ptrbuf++];
	}

	private boolean isSpaceChar(int c) 
	{
		return !(c >= 33 && c <= 126);
	}

	private int skip() 
	{
		int b;
		while ((b = readByte()) != -1 && isSpaceChar(b))
			;
		return b;
	}

	private double nd() 
	{
		return Double.parseDouble(ns());
	}

	private char nc() 
	{
		return (char) skip();
	}

	private String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while (!(isSpaceChar(b)))
		{ // when nextLine, (isSpaceChar(b) && b != '
									// ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	private char[] ns(int n) 
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while (p < n && !(isSpaceChar(b)))
		{
			buf[p++] = (char) b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}

	private char[][] nm(int n, int m)
	{
		char[][] map = new char[n][];
		for (int i = 0; i < n; i++)
			map[i] = ns(m);
		return map;
	}

	private int[] na(int n)
	{
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}

	private int ni() 
	{
		int num = 0, b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-')
		{
			minus = true;
			b = readByte();
		}

		while (true) 
		{
			if (b >= '0' && b <= '9') 
			{
				num = num * 10 + (b - '0');
			} else 
			{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private long nl() 
	{
		long num = 0;
		int b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') 
		{
			minus = true;
			b = readByte();
		}

		while (true) 
		{
			if (b >= '0' && b <= '9') 
			{
				num = num * 10 + (b - '0');
			} else 
			{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private boolean oj = System.getProperty("ONLINE_JUDGE") != null;

	private void tr(Object... o) 
	{
		if (!oj)
			System.out.println(Arrays.deepToString(o));
	}
}