Fişierul intrare/ieşire:	harta3.in, harta3.out	Sursă	.com 2009, runda 2
Autor	Teodor Anton Pripoae	Adăugată de	Radu Zernoveanu •raduzer
Timp execuţie pe test	0.05 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Harta3

Considerăm N puncte pe axa OX având coordonate întregi. Se dau M relaţii de forma X Y D semnificând faptul că X se află la stânga lui Y cu D unitaţi. Se mai dau punctele speciale A şi B, care fac parte din cele N.

Cerinţa

Atribuiţi coordonate diferite celor N puncte astfel încat să se respecte cele M relaţii, iar distanţa între A şi B să fie cât mai mică.

Date de intrare

Fişierul de intrare harta3.in conţine pe prima linie numerele N şi M, cu semnificaţia din enunţ. Pe a doua linie se află punctele A şi B. Urmatoarele M linii conţin câte 3 numere X, Y şi D.

Date de iesire

Fişierul de ieşire harta3.out conţine pe prima linie N numere reprezentând coordonatele pe axa OX a celor N puncte.

Restricţii şi precizari

2 ≤ N ≤ 10 000
0 ≤ M ≤ 10 000
Pentru fiecare X, Y, D, 1 ≤ D ≤ 100.
Atenţie! Se garantează că distanţa minimă între A şi B ≤ 2 400.
Coordonatele punctelor trebuie să aparţina intervalului [-1 000 000, 1 000 000].
În cazul în care exista mai multe soluţii, se poate afişa oricare dintre acestea.
Se garanteaza ca exista soluţie!