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

• $1 \le k \le 1000$
• $1 \le n \le 10^5$
• $1 \le y,x \le k$

Esimerkki

Syöte:

4 5
1 2 2
2 2 2
2 4 4
1 3 4
2 4 4

Tuloste:

0
4
1