B. Build a Contest

Arkady coordinates rounds on some not really famous competitive programming platform. Each round features nn problems of distinct difficulty, the difficulties are numbered from 11 to nn.

To hold a round Arkady needs nn new (not used previously) problems, one for each difficulty. As for now, Arkady creates all the problems himself, but unfortunately, he can't just create a problem of a desired difficulty. Instead, when he creates a problem, he evaluates its difficulty from 11 to nn and puts it into the problems pool.

At each moment when Arkady can choose a set of nn new problems of distinct difficulties from the pool, he holds a round with these problems and removes them from the pool. Arkady always creates one problem at a time, so if he can hold a round after creating a problem, he immediately does it.

You are given a sequence of problems' difficulties in the order Arkady created them. For each problem, determine whether Arkady held the round right after creating this problem, or not. Initially the problems pool is empty.

Input

The first line contains two integers nn and mm (1≤n,m≤1051≤n,m≤105) — the number of difficulty levels and the number of problems Arkady created.

The second line contains mm integers a1,a2,…,ama1,a2,…,am (1≤ai≤n1≤ai≤n) — the problems' difficulties in the order Arkady created them.

Output

Print a line containing mm digits. The ii-th digit should be 11 if Arkady held the round after creation of the ii-th problem, and 00 otherwise.

Examples

input

3 11
2 3 1 2 2 2 3 2 2 3 1

output

00100000001

input

4 8
4 1 3 3 2 3 3 3

output

00001000

题意： 输入n和m，第二行有m个数字，分别由1~n这几种数字组成。

输入数字时进行判断，如果当前已输入的数字数组中1~n均包含，则输出1，否则输出0；

已使用过的数字不能再次被使用。

 

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define closeio std::ios::sync_with_stdio(false)
 
int a[100005],b[100005];
 
int main()
{
	int n,m,i,j,sum=0;
	mem(b,0);
	cin>>n>>m;
	for(i=0;i<m;i++)
		cin>>a[i];
	for(i=0;i<m;i++)
	{
		b[a[i]]++;
		if(b[a[i]]==1)
			sum++;
		if(sum==n)
		{
			cout<<"1";
			for(j=1;j<=n;j++)
			{
				b[j]--;
				if(b[j]==0)
					sum--;
			}
		}
		else
			cout<<"0";
	}
	return 0;
}