Tehtäväsi on muodostaa $n\times m$ kokoinen ruudukko, jonka jokainen ruutu on lattiaa (.) tai seinää (#). Ruudukossa pystyy kulkemaan liikkumalla vaaka- ja pystysuuntaisesti lattiaruutuja pitkin.

Ruudukon tulee toteuttaa seuraavat vaatimukset:

• mitkään kaksi seinäruutua eivät ole vierekkäin vaaka- tai pystysuunnassa
• jokaisen kahden lattiaruudun välillä on tasan yksi reitti, jossa mikään lattiaruutu ei toistu (eli lattiaruudut muodostavat verkon, joka on puu)

Syöte

Syötteenä on kaksi kokonaislukua $n$ ja $m$.

Tuloste

Tulosta jokin mahdollinen ratkaisu. On mahdollista osoittaa, että kaikille syötteille on olemassa ratkaisu.

Esimerkki

Syöte:

5 8

Tuloste:

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

Osatehtävä 1 (11 pistettä)

• $1\le n,m\le4$

Osatehtävä 2 (25 pistettä)

• $1\le n\le1000$, $1\le m\le4$

Osatehtävä 3 (64 pistettä)

• $1\le n,m\le1000$