Tarkastellaan n \times n -ruudukkoa, jossa jokainen ruutu voi olla valkoinen tai musta. Aluksi kaikki ruudut ovat valkoisia.

Suoritetaan m operaatiota, jossa muutetaan tietyn aliruudukon kaikkien ruutujen väri käänteiseksi. Millainen on lopullinen ruudukko?

Syöte

Ensimmäisellä rivillä on kaksi kokonaislukua n ja m: ruudukon koko ja operaatioiden määrä. Ruudukon rivit ja sarakkeet on numeroitu 1,2,\dots,n.

Seuraavat m riviä kuvaavat operaatiot. Jokaisella rivillä on neljä kokonaislukua y_1, x_1, y_2 ja x_2: aliruudukon vasen yläkulma on (y_1,x_1) ja oikea alakulma on (y_2,x_2).

Tuloste

Tulosta lopullinen ruudukko käyttäen merkkejä . (valkoinen) ja # (musta).

Esimerkki

Syöte:

5 2
1 1 2 3
1 3 4 5

Tuloste:

##.##
##.##
..###
..###
.....

Osatehtävä 1 (16 pistettä)

• 1 \le n \le 10
• 1 \le m \le 100

Osatehtävä 2 (42 pistettä)

• 1 \le n \le 500
• 1 \le m \le 10^5

Osatehtävä 3 (42 pistettä)

• 1 \le n \le 2000
• 1 \le m \le 10^5