joc

Pentru un concurs de design de jocuri, Gigel vrea să construiască un joc. La joc participă $n$ concurenţi numerotaţi de la $1$ la $n$.

Fiecare concurent are la dispoziţie câte un şir de $m$ încăperi, numerotate de la $1$ la $m$. Scopul jocului este de a găsi o comoară ascunsă în una din aceste încăperi.

Fiecare încăpere conţine un cod, număr natural, fie egal cu $0$, fie având cel puţin $2$ cifre. Ultima cifră indică numărul de etape de penalizare, adică numărul de etape în care concurentul nu are voie să părăsească încăperea. Numărul obţinut prin eliminarea ultimei cifre a codului indică numărul încăperii în care se va deplasa acesta la următoarea etapă sau la expirarea penalizării. Există două excepţii de la regula de definire a codului: numărul $9 \ 999$ codifică o încăpere conţinând o comoară, iar numărul $0$ o încăpere conţinând o capcana.

În etapa $1$ fiecare jucător intră în încăperea $1$ din şirul său de încăperi. În funcţie de codul găsit în încăpere sunt posibile următoarele situaţii:

• codul găsit este $9 \ 999$ ceea ce înseamnă că jucătorul este câştigător şi jocul se încheie la finalul acestei etape
• codul găsit este $0$ ceea ce duce la eliminarea sa din joc
• pentru celelalte coduri, după efectuarea etapelor de penalizare, jucătorul efectuează o deplasare în încăperea indicată de cod. De exemplu la întâlnirea codul $157$, după efectuarea celor $7$ etape de penalizare jucătorul se va deplasa în camera $15$

Trecerea de la o etapă la alta se realizează simultan pentru toţi concurenţii.

Cerință

Fiind dat numărul $n$ de concurenţi, numărul $m$ de încăperi alocate fiecărui concurent, şi codurile din cele $n \cdot m$ încăperi să se determine câştigătorul jocului, numărul încăperii în care a găsit comoara, numărul de etape parcurse până când câştigătorul găseşte comoara precum şi numărul de concurenţi eliminaţi din joc până la etapa respectivă (inclusiv).

Date de intrare

Prima linie a fişierului de intrare joc.in conţine două numere naturale $n$ şi $m$, separate printr-un spaţiu, reprezentând numărul concurenţilor, respectiv numărul încăperilor.
Următoarele $n$ linii conţin câte m numere naturale, separate prin câte un spaţiu, reprezentând codurile din fiecare încăpere.

Date de ieșire

Prima linie a fişierului de ieşire joc.out va conţine patru numere naturale separate prin câte un spaţiu, reprezentând indicele câştigătorului, numărul încăperii unde a găsit comoara, numărul etapei în care a câştigat şi respectiv numărul de concurenţi eliminaţi din joc.

Restricții și precizări

• $1 \leq n \leq 400$
• $1 \leq m \leq 900$
• Pentru toate testele de intrare se garantează că există exact un câştigător

Exemplu

joc.in

4 8
0 9999 41 50 61 70 80 30
30 80 60 60 9999 21 40 50
20 30 40 50 61 71 81 9999
20 30 50 0 61 71 9999 41

joc.out

2 5 7 1

Explicație

Câştigă jucătorul al $2$-lea, după $7$ etape, iar încăperea în care a găsit comoara este încăperea $5$. În cele $7$ etape a fost eliminat un singur concurent şi anume primul concurent.

Încăperile prin care trece jucătorul câştigător până la final sunt:

$1 \rightarrow 3 \rightarrow 6 \rightarrow 2 \rightarrow 8 \rightarrow 5$