Daycare Matching

問題

みーとみ市には保育園が $M$ 園あり，保育園への入園を希望する児童が $N$ 人います．

児童 $i ~(=1,\dots, N)$ には入園希望順序があり，第 $1$ 希望が園 $d_{i,1}$，…，第 $M$ 希望が園 $d_{i,M}$ です．

保育園 $j~(=1,\dots, M)$ には児童の優先順序があり，第 $1$ 優先が 児童 $c_{j,1}$,…，第 $N$ 優先が児童 $c_{j,N}$ です．

また，各保育園 $j$ は受入人数が $q_{j} ~(>0)$ 決まっており，$q_1 + \dots + q_M = N$ となっています．

各児童 $i$ に入園させる保育園 $\mu_i$ を決めた組み合わせ $\mu = (\mu_1, \dots, \mu_N)$ をマッチングと呼びます． また，良いマッチングとは，以下の２条件が成り立つことを言います：

1. 各保育園 $j$ について入園する児童の人数は $q_j$ 人である．
2. 不満を持つ児童 $i$ が存在しない．
   • 児童 $i$ が不満を持つとは，入園する園 $\mu_i$ より希望の高い別の園 $j$ があり，かつ園 $j$ に入園する別の児童 $i'$ で園 $j$ の優先基準において児童 $i$ より低いものがいる状況のことをいう．

良いマッチングを１つ出力してください．なお，この問題設定において少なくとも１つ以上良いマッチングが存在することを証明できます．

制約

• $2\le N \le 2000$
• $2 \le M \le \min(N, 200)$
• $1 \le d_{i,j} \le M, ~~ j \ne j' \Rightarrow d_{i,j} \ne d_{i,j'}$
• $1 \le c_{j, i} \le N, ~~ i \ne i' \Rightarrow c_{j, i} \ne c_{j, i'}$
• $1 \le q_j \le N-1$
• $q_1+\dots + q_M = N$
• 与えられる入力はすべて整数

入力

入力は以下の形式で与えられます．

出力

以下のように，良いマッチング $\mu = (\mu_1, \dots, \mu_N)$ を1行に半角スペース区切りで出力してください．

入出力例

4 3
2 1 3
2 1 3
1 2 3
3 1 2
1 2 4 3
4 3 1 2
3 2 4 1
2 1 1

2 1 1 3

• 保育園 $1, 2, 3$ とも定められた受入人数を入園させています．
• 児童 $1, 3, 4$ は第 $1$ 希望の保育園に入園できているので不満を持ちません．また，児童 $2$ は第 $2$ 希望の園に入園していますが，第 $1$ 希望の保育園 $2$ はより優先順序の高い児童 $1$ で定員が埋まっているので，児童 2 も不満を持ちません．よって，このマッチングは良いマッチングです．
• これ以外に 1 1 3 2も良いマッチングであるため，こちらを出力しても正答となります．