!>problema/cumainilecurate?miclovan_roman.jpg!

**Atentie!**: Numele fisierelor de intrare si iesire ale problemei s-a schimbat din cmcurate.

**Atentie!**: Numele fisierelor de intrare si iesire ale problemei s-au schimbat din __cmcurate__.

bq. - Gangsterii noştrii nu sunt ca cei americani - ai noştrii nu au tradiţie!
- Sper că n-o să-i lasaăƒm să şi-o formeze!

* 1 ≤ **N** ≤ 300000
* 1 ≤ **M** ≤ 100000

* 1 ≤ _importanta unui mafiot_ ≤ 1000000000

* **Subtask 1 (20 puncte)**: 1 ≤ **N** ≤ 3000 si 1 ≤ **M** ≤ 1000
* **Subtask 2 (20 puncte)**: Se garanteaza ca input vor fi cel mult 10 operatii de _tipul 1_.