Il y a $n$ paquets de cartes sur la table. Le $i$-ème paquet contient $a_i$ cartes et la $j$-ème carte de haut en bas est $s_{i,j}$. Pour simplifier le problème, on ne considère que des cartes hautes et basses. Si une carte est haute, alors $s_{i,j}=1$. Si elle est basse, alors $s_{i,j}=0$.

Il y a $m$ joueurs assis autour de la table qui attendent une partie de cartes. Vous êtes le donneur et votre tâche est d’empiler tous les paquets pour former une grande pile. Vous ne pouvez contrôler que l’ordre entre les paquets. Vous ne pouvez ni insérer ni retirer de carte, ni changer l’ordre des cartes à l’intérieur d’un paquet.

Une fois la pile constituée, les cartes seront distribuées aux joueurs. Le $i$-ème joueur recevra les cartes aux positions $i$, $m+i$, $2m+i$, $\ldots$, $km+i$, $\ldots$, de haut en bas. Ce que les autres joueurs ignorent, c’est que le $b$-ème joueur est en réalité votre patron. Pour assurer sa victoire, toutes les cartes données à votre patron doivent être hautes et toutes celles données aux autres joueurs doivent être basses.

Trouvez un ordre d’empilement des paquets satisfaisant cette exigence ou indiquez que c’est impossible. Si une réponse valide existe, donnez la plus petite dans l’ordre lexicographique.

La réponse, si elle existe, est évidemment une permutation de longueur $n$. On dit que la permutation $P=p_1,p_2,\ldots,p_n$ est lexicographiquement plus petite que la permutation $Q=q_1,q_2,\ldots,q_n$ s’il existe un entier $t$ tel que $p_i=q_i$ pour tout $1\le i<t$ et $p_t<q_t$.

Entrée

Chaque fichier de test ne contient qu’un seul cas de test.

La première ligne de l’entrée contient trois entiers $n$, $m$ et $b$ ($1\le n\le2\times10^5$, $2\le m\le2\times10^5$, $1\le b\le m$), indiquant le nombre de paquets, le nombre de joueurs et l’indice du patron.

Parmi les $n$ lignes suivantes, la $i$-ème contient une chaîne $s_{i,1}s_{i,2}\cdots s_{i,a_i}$ ($s_{i,j}\in\{0,1\}$, $1\le a_i\le10^6$) décrivant le $i$-ème paquet.

Il est garanti que :

• Chaque paquet contient au moins une carte haute.

• Le nombre total de cartes est divisible par $m$.

• Le nombre total de cartes ne dépasse pas $10^6$.

Sortie

Si une réponse valide existe, affichez $n$ entiers $d_1,d_2,\ldots,d_n$ séparés par des espaces, donnant la plus petite réponse dans l’ordre lexicographique, où $d_i$ est l’indice du $i$-ème paquet dans la pile de haut en bas.

Si aucune réponse valide n’existe, affichez simplement « -1 » (sans les guillemets).

Exemples

Entrée 1

5 4 3
0100010
00100
001000100
0010
0100010

Sortie 1

2 1 3 5 4

Entrée 2

4 2 1
010
10101
010
10101

Sortie 2

2 1 4 3

Entrée 3

1 5 3
001000010000100

Sortie 3

1

Entrée 4

2 5 3
01000
00010

Sortie 4

-1

Entrée 5

1 5 3
11111

Sortie 5

-1