Clasa a XII-a
Ziua 1
Problema 2

(Ciocniri) 40 puncte

Īntr-un ring dreptunghiular de dimensiuni m si n (1£m,n£ 250, m,nĪ N) asezat cu coltul din stānga-jos īn originea sistemului de coordonate, se afla k (1£ k£ 250) bile care se pot deplasa cu viteza constanta pe directii paralele cu bisectoarele sistemului de axe de coordonate. Se cunosc coordonatele la momentul initial si directia de deplasare a fiecarei bile. Īn momentul ciocnirii unei bile de marginea ringului aceasta īsi va schimba directia de deplasare dupa principiul reflexiei.

Daca doua bile care se deplaseaza pe directii diferite, se ciocnesc, atunci bila care vine din dreapta sau de sus a ringului (īn aceasta ordine) va distruge cealalta bila si īsi va continua miscarea.

Daca doua bile care se deplaseaza pe aceasi directie, dar īn sensuri opuse, se ciocnesc, atunci acestea se distrug reciproc. Distrugerea se produce cu prioritate.

Din momentul initial, īntr-o unitate de timp, o bila se deplaseaza dintr-o pozitie de coordonate (x,y) īntr-una din pozitiile (x± 1,y± 1), (0£ x£ m, 0£ y£n, x,yĪN).

Se cere sa se determine numarul de bile ramase īn ring si pozitiile acestora dupa un interval de timp t (1£t£65000).

Fisierul de intrare 'input.txt' contine:
m n - dimensiunile ringului
t - intervalul de timp
x₁ y₁ d₁ - pozitia initiala si respectiv directia de deplasare a bilei 1
x₂ y₂ d₂ - pozitia initiala si respectiv directia de deplasare a bilei 2
. . .
x_k y_k d_k - pozitia initiala si respectiv directia de deplasare a bilei k.

Fisierul de iesire 'output.txt' va contine pe prima linie
p - (numarul de bile ramase), urmata de p linii de forma
x y - pozitie bila ramasa, (īn ordinea īn care apar bilele īn fisierul de intrare).

Nota. O pozitie poate fi ocupata de o singura bila. Initial o bila poate fi situata si pe marginea ringului. Doua bile se pot ciocni numai īn puncte de coordonate īntregi.

Directiile de deplasare sunt codificate astfel:

1 - deplasare din pozitia (x,y) īn pozitia (x+1,y+1)
2 - deplasare din pozitia (x,y) īn pozitia (x-1,y+1)
3 - deplasare din pozitia (x,y) īn pozitia (x-1,y-1)
4 - deplasare din pozitia (x,y) īn pozitia (x+1,y-1)

Exemplu.
Pentru fisierul de intrare 'input.txt' ce contine:
4 3
5
1 2 1
3 0 1
4 3 3

Fisierul de iesire 'output.txt' va contine
1
1 2

Timp de executie maxim: 3 secunde pe test.