Mooyo Mooyo#10398

Mooyo Mooyo

1 secondo

128 megabyte

Facile

Con molto tempo libero a disposizione (o meglio, a zoccoli), le mucche della fattoria di Farmer John passano spesso il tempo giocando a videogiochi. Uno dei loro preferiti è basato su un famoso videogioco umano chiamato Puyo Puyo; la versione bovina, naturalmente, si chiama Mooyo Mooyo.

Mooyo Mooyo si gioca su una griglia alta e stretta, composta da $n$ celle di altezza e $10$ celle di larghezza. Ecco un esempio con $n = 6$ n = 6:

Ogni cella è vuota (indicata da $0$ ) oppure contiene una balla di fieno di uno dei nove colori (indicati dalle cifre da $1$ a $9$ ). La gravità fa cadere le balle di fieno verso il basso, quindi non può mai esserci una cella vuota sotto una balla di fieno.

Due celle appartengono alla stessa regione connessa se sono adiacenti orizzontalmente o verticalmente e hanno lo stesso colore non nullo. Ogni volta che esiste una regione connessa di almeno $k$ celle, tutte le sue balle di fieno scompaiono e le celle diventano vuote. Se esistono più regioni di questo tipo contemporaneamente, scompaiono tutte simultaneamente. Dopodiché, la gravità può far cadere le balle di fieno in alcune delle celle appena svuotate. La configurazione risultante può di nuovo contenere regioni connesse di almeno $k$ celle. In tal caso, anch'esse scompaiono (simultaneamente, se ce ne sono diverse), la gravità fa nuovamente scendere le balle di fieno rimanenti, e il processo si ripete finché non rimane più alcuna regione connessa di almeno $k$ celle.

Dato lo stato iniziale di una tavola di Mooyo Mooyo, stampa lo stato finale della tavola dopo tutte queste operazioni.

Input

La prima riga contiene due interi $n$ e $k (1 \leq n \leq 100, 1 \leq k \leq 10 n)$ k~(1 \le n \le 100, 1 \le k \le 10n). Ciascuna delle successive $n$ righe contiene $10$ cifre e descrive una riga della tavola iniziale.

Output

Stampa $n$ righe che descrivono lo stato finale della tavola nello stesso formato.

Esempi

Nell'esempio precedente, se $k = 3$ k = 3, esiste una regione connessa di almeno $k$ celle di colore $1$ e un'altra di colore $2$ . Dopo che vengono rimosse simultaneamente, la tavola appare temporaneamente così:

Poi la gravità entra in azione, e le balle di fieno cadono formando la seguente configurazione:

Di nuovo, esiste una regione di almeno $k$ celle (di colore $3$ ). Rimuovendola si ottiene la configurazione finale della tavola:

Esempio 1