問題 D 列の構成

問題文

1 から N までの相異なる整数が N / 2 個書かれたカードがいくつか与えられるので，次の条件を満たすような長さ N の数列 seq を 1 つ作って出力して欲しい．

• seq の各要素は 0 か 1 である．
• すべてのカードについて以下が成り立つ： カードに書かれた数字をcard[1], ..., card[N/2]とする．このときカードに書かれた部分の和: seq[card[1]] + ... + seq[card[N/2]] が N / 8 以上かつ 3N / 8 以下になっている．

例えば，N = 8 でカードが 2 枚渡され，カードに書かれている数字がそれぞれ [1, 2, 7, 8]，[4, 5, 7, 8] であったとする．このとき seq=[0, 1, 0, 1, 0, 1, 0, 1] や seq=[0, 0, 0, 0, 1, 1, 1, 1] とおくと条件を満たすようにできている．

入力形式

N K
card1[1] card1[2] ... card1[N/2]
card2[1] card2[2] ... card2[N/2]
...
cardK[1] cardK[2] ... cardK[N/2]

1 行目において N は構成するべき数列の長さ，K はカードの枚数である． 続く K 行には各カードの情報が与えられる．card_i[1], ..., card_i[N/2] が i 番目のカードに書かれている数字である．

出力形式

seq の i 番目の要素が i 文字目に対応するように数列 seq を 1 行に出力せよ．

なお，どの入力に対しても解は必ず少なくとも 1 つは存在する．

制約

• 8 ≤ N ≤ 1,000, 1≤ K ≤ N / 2
• N は 8 の倍数
• 1 ≤ card_i[1] < card_i[2] < ... < card_i[N/2] ≤ N

入出力例

入力例 1

8 2
1 2 7 8
4 5 7 8

出力例 1

01010101

入力例 2

8 3
2 3 4 6
3 4 5 8
3 4 6 8

出力例 2

01110011