== include(page="template/taskheader" task_id="trasee") ==

Poveste şi cerinţă...

Transportul local în oraşul ISANOTOB este rezolvat optim cu ajutorul microbuzelor. Traseele au fost concepute în aşa fel încât două microbuze să nu aibă nicio porţiune comună de drum, în afară de intersecţii. Orice traseu poate fi reprezentat ca un segment sau o linie frântă formată din mai multe segmente perpendiculare. Linia frântă poate fi deschisă sau închisă.
Traseele sunt memorate pe o hartă dreptunghiulară formată din $n x m$  pătrate identice. Aceste pătrate le vom nota cu $a{~ij~}$ ({$1≤i≤n$},{$1≤j≤m$}). Vom atribui hărţii şi un sistem de coordonate cu $n x m$ puncte, cu axele de coordonate Ox orientată spre dreapta, şi axa Oy orientată în jos. La intersecţia axelor se găseşte punctul de coordonate $(0, 0)$, astfel colţul dreapta-jos al fiecărui pătrat $a{~ij~}$ are coordonatele ({$i$}, {$j$}) {$1≤i≤n$} şi {$1≤j≤m$}.
Două trasee se pot intersecta, dar *nu pot avea niciun segment comun*.
În _figura 1_, pe o hartă de dimensiuni $4 x 3$, vedem patru trasee:
1. Primul traseu, desenat cu linie dublă, are pornirea din punctul de coordonate $(1,2)$, şi sosirea în punctul de coordonate $(1,2)$, Adică este un traseu închis (ciclu). La fel de corect ar fi dacă punctul de pornire ar fi punctul $(2,2)$ şi oprirea $(2,2)$, harta nu s-ar schimba.
2. Traseul al doilea, desenat cu linie triplă porneşte din punctul de coordonate $(3,1)$ şi se termină în punctul de coordonate $(3,3)$.
3. Traseul al treilea, desenat cu linie punctată, are ca puncte de pornire, respectiv de sosire, punctele de coordonate $(4,1)$ respectiv $(2,2)$.
4. Traseul al patrulea, desenat cu linie întreruptă, are ca puncte de pornire, respectiv de sosire, punctele de coordonate $(4,1)$ respectiv $(2,2)$.
 
În continuare ne vor interesa segmentele de pe hartă, fără să ştim cărui traseu îi aparţin. De aceea vom desena toate traseele cu linie îngroşată. Această hartă este memorată ca o matrice de dimensiuni $n x m$ şi o vom numi _matricea traseelor_, în care fiecare element $a{~i,j~}$ este egal cu numărul de segmente ce fac parte din vreun traseu, deci valorile posibile pot fi $0,1,2,3$ sau $4$.  Matricea traseelor din _figura 2_ corespunde hărţii traseelor din _figura 1_.
_Matricea-hartă_ de dimensiuni $3n x 3m$ este o altă metodă de afişare a hărţii traseelor, în care orice nod de coordonate $(i,j)$ va fi înlocuit cu o _matrice-nod_ de dimensiuni $3 x 3$. Orice element matrice-nod poate avea $16$ valori distincte în funcţie de legăturile existente spre Nord, Sud, Est sau Vest:
!problema/trasee?types.png!
 
Matricea-hartă din _figura 3_ corespunde hărţii traseelor din _figura 1_.
 
!problema/trasee?poza1.png!   !problema/trasee?poza2.png!   !problema/trasee?poza3.png!
 
                 _figura 1_                                   _figura 2_                                          _figura 3_
              harta traseelor                   matricea traseelor                              matricea-hartă
 
h2. Cerinţă
 
Cunoscând matricea traseelor şi toate punctele de pornire şi de sosire ale traseelor, se cere matricea-hartă corespunzătoare.

h2. Date de intrare

Fişierul de intrare $trasee.in$ ...

Fişierul de intrare $trasee.in$ conţine pe prima linie numerele $n m k$ separate prin spaţiu, $n$ şi $m$ cu semnificaţiile din enunţ, iar $k$, numărul traseelor de pe hartă. Următoarele $n$ linii conţin câte $m$ numere separate prin spaţiu, reprezentând matricea traseelor. Următoarele $k$ linii conţin câte patru numere naturale $x y u v$ separate cu câte un spaţiu, reprezentând pe harta traseelor, coordonatele punctelor de pornire şi sosire ale celor $k$ trasee, $(x,y)$ respectiv $(u,v)$.

h2. Date de ieşire

În fişierul de ieşire $trasee.out$ ...

Fişierul de ieşire $trasee.out$ va conţine $3n$ linii cu câte $3m$ cifre $0$ sau $1$ *neseparate prin spaţii*, reprezentând matricea-hartă corespunzătoare hărţii traseului.

h2. Restricţii

h2. Restricţii şi precizări

* $... ≤ ... ≤ ...$

* $3 ≤ m,n ≤ 500$
* $1 ≤ k ≤ 350 000$
* se acceptă orice soluţie corectă
* fiecare traseu are *cel puţin un* segment, fiecare segment aparţine *unui singur* traseu
* pentru 25% din teste $m,n < 10$
* pentru alte 25% din teste $m,n < 40$

h2. Exemplu

table(example). |_. trasee.in |_. trasee.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

table(example). |_. trasee.in |_. trasee.out |_. Explicaţie |
| 4 3 4
0 0 1
0 2 4
1 4 3
1 4 2
1 2 1 2
3 3 3 1
2 2 4 1
4 1 2 2
| 000000000
000011110
000010010
000010010
011111110
010010000
010010000
011111110
010010000
010010000
011110000
000000000
| n=4, m=3, k=4
Matricea traseelor de dimensiuni 4x3 este cea din _figura 2_.
Avem 4 trasee evidenţiate în _figura 1_ între punctele de coordonate
(1,2) şi  (1,2),
(3,3) şi  (3,1),
(2,2) şi  (4,1), respectiv
(4,1) şi  (2,2).
Matricea-hartă din fişierul de ieşire este cea din _figura 3_.
|

== include(page="template/taskfooter" task_id="trasee") ==
 

== include(page="template/taskfooter" task_id="trasee") ==

7907