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