Primera fila diferent després X89861

Statement

Donada una matriu de naturals positius, per a cada fila volem saber quina és la primera fila que trobem després d’ella i diferent d’ella. Per exemple, considereu la següent matriu:

La fila $2$ (indexant començant per $0$ ) conté els valors $4,1,5,3$ en aquest ordre. Resulta que les files $3$ i $4$ contenen els mateixos valors en el mateix ordre. En canvi, la fila $5$ conté els valors $2,6,8,1$ . Per tant, $5$ seria la primera fila després de la fila $2$ que és diferent de la fila $2$ .

Entrada

La primera línia de l’entrada té dos valors positius $n,m$ separats per un espai que representen les mides de la matriu. A continuació venen $n$ línies amb $m$ valors positius separats per espais, el contingut de la matriu.

Sortida

La sortida conté $n$ línies. La $i$ -esima línia (indexant des de $0$ ) conté o bé un número major que $i$ , que és l’índex de la primera fila que trobem després de la fila $i$ que és diferent de la fila $i$ , o bé un $-1$ si tal fila diferent no existeix.

Observació

Per a superar uns quants jocs de proves i obtenir una nota acceptable podeu fer un programa senzill. Però per a superar tots els jocs de proves convindrà pensar en alguna optimització raonable.

Public test cases

Input

Output

Input

Output

-1
-1
-1

Input

20 20
8 11 52 43 72 61 49 96 69 15 33 53 64 16 91 86 2 90 54 99
95 55 18 60 34 83 75 90 26 57 1 85 20 4 27 91 16 28 86 84
42 71 88 5 38 31 42 39 20 47 89 66 53 6 25 86 88 100 75 13
42 71 88 5 38 31 42 39 20 48 89 66 53 6 25 86 88 100 75 13
91 44 38 43 50 63 28 37 14 54 2 73 32 3 52 13 78 24 61 33
82 45 80 62 16 32 27 17 76 34 89 67 78 26 9 79 40 89 67 53
94 20 78 26 22 81 90 52 4 3 84 38 47 15 99 62 46 78 78 22
11 18 88 40 43 48 70 83 36 89 87 82 8 16 7 82 48 48 33 52
11 18 88 40 43 48 70 83 36 89 87 82 8 16 7 82 48 48 33 52
12 18 88 40 43 48 70 83 36 89 87 82 8 16 7 82 48 48 33 52
12 18 88 40 43 48 70 83 36 89 87 82 8 16 7 82 48 48 33 51
25 13 82 48 89 87 4 7 53 87 92 57 22 8 63 96 45 18 60 73
56 99 84 11 92 33 56 3 54 81 22 79 93 3 78 33 41 81 91 46
67 83 2 40 90 64 87 34 33 46 58 88 44 41 50 88 73 5 90 27
37 63 57 82 17 34 66 9 14 57 54 32 39 55 71 28 70 9 13 54
37 63 57 82 17 34 66 9 14 57 54 32 39 55 71 28 70 9 13 54
94 18 49 32 24 71 11 46 31 23 51 85 44 44 34 5 38 70 91 88
47 2 75 86 22 95 41 26 33 4 44 26 73 44 10 49 67 20 46 97
47 2 75 86 22 95 41 26 33 4 44 26 73 44 10 49 67 20 46 97
14 80 46 38 75 7 86 41 79 31 90 25 79 22 14 17 88 60 45 74

Output

Information

Author
Language: Catalan
Official solutions: C++
User solutions: C++