Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Ruudukko

Ruudukko


View task | Model solution | Statistics


Ruudukko

Time limit:1.50 s
Memory limit:128 MB

Ruudukon koko on $k \times k$ ruutua, ja jokainen ruutu on aluksi valkoinen. Ruutujen $(y_1,x_1)$ ja $(y_2,x_2)$ etäisyys on $|y_1-y_2|+|x_1-x_2|$.

Tehtäväsi on toteuttaa seuraavat operaatiot:
  1. muuta ruudun $(y,x)$ väri valkoisesta mustaksi
  2. laske etäisyys ruudusta $(y,x)$ lähimpään mustaan ruutuun
Syöte

Syötteessä on ensin kaksi kokonaislukua $k$ ja $n$: ruudukon koko ja operaatioiden määrä.

Tämän jälkeen syötteessä on $n$ riviä, jotka kuvaavat operaatiot. Jokaisella rivillä on kolme lukua $t$, $y$ ja $x$.

Jos $t=1$, on kyseessä tyypin 1 operaatio, joka muuttaa ruudun $(y,x)$ mustaksi. Voit olettaa, että ruutu $(y,x)$ on valkoinen ennen operaatiota.

Jos $t=2$, on kyseessä tyypin 2 operaatio, jossa täytyy laskea etäisyys ruudusta $(y,x)$ lähimpään mustaan ruutuun.

Ensimmäinen operaatioista on aina tyypin 1 operaatio.

Tuloste

Tulosta jokaisen tyypin 2 operaation vastaus omalle rivilleen.

Rajat
Esimerkki

Syöte:
4 5
1 2 2
2 2 2
2 4 4
1 3 4
2 4 4


Tuloste:
0
4
1