* $1 ≤ N ≤ 10^9^$
* $0 ≤ M ≤ 2 * 10^5^$
* $1 ≤ C ≤ 5 * 10^5^$

* **Atenţie!** Volum mare de date de intrare, vă recomandăm să optimizaţi citirea folosindu-va de "acest cod":http://pastebin.com/dfEATDDB.

* **Atentie!** Fiecare subtask are testele grupate!
* **Subtask 1 (10 puncte):** $M = 0$ (Feedback testul 1)
* **Subtask 2 (20 puncte):** $N ≤ 1000, M ≤ 2000$ (Feedback testul 2)

* **Subtask 1 (10 puncte):** $M = 0$
* **Subtask 2 (20 puncte):** $N ≤ 1000, M ≤ 2000$

* **Subtask 3 (30 puncte):** $N ≤ 10^5^$

* **Subtask 4 (40 puncte):** Restricţii iniţiale (Feedback testele 7 si 8)

* **Subtask 4 (40 punctE):** Restricţii iniţiale

h2. Exemplu