Okabe are de descifrat un nou mister. Pentru a realiza acest lucru, el trebuie sa afle riscul de a forma un paradox in fiecare linie a timpului in care acesta se afla.

Mai exact, fie un graf cu $N$ noduri si $M$ muchii ORIENTATE (nodurile reprezinta stari in timp si muchiile relatii intre aceste stari, fapt irelevant). Pentru fiecare nod $X$ se cunoaste o valoare $risc[X]$ la evenimentul $0$. Dupa fiecare eveniment nou, riscul dintr-un nod $X$ se propaga in toti vecinii acestuia (daca exista muchie de la $X$ la $Y$). Deoarece universul este complicat, riscul unui nod devine dupa fiecare moment, maximul valorilor care se propaga in acest nod. Misiunea lui Okabe este sa afle riscul din fiecare nod dupa $K$ evenimente.

Mai exact, fie un graf cu $N$ noduri si $M$ muchii ORIENTATE (nodurile reprezinta stari in timp si muchiile relatii intre aceste stari, fapt irelevant). Pentru fiecare nod $X$ se cunoaste o valoare $risc[X]$ la evenimentul $0$. Dupa fiecare eveniment nou, riscul dintr-un nod $X$ se propaga in toti vecinii acestuia (daca exista muchie de la $X$ la $Y$). Deoarece universul este complicat, riscul unui nod devine dupa fiecare eveniment, maximul valorilor care se propaga in acest nod. Misiunea lui Okabe este sa afle riscul din fiecare nod dupa $K$ evenimente.

h2. Date de intrare

h2. Restricţii
* $1 ≤ N ≤ 200$

* $$ ≤ M ≤ N * N$

* $1 ≤ M ≤ N * N$
* $1 ≤ K ≤ 1.000.000.000$

* $1 ≤ risc[i] ≤ 1.000.000.000$

* Se garanteaza ca pentru fiecare nod $X$, exista cel putin un nod $Y$ astfel incat sa avem muchie de la $Y$ la $X$ (exista cel putin un nod $Y$ care isi propaga riscul in $X$)
* Pentru teste in valoare de *30* de puncte $K ≤ 100.000$

h2. Exemplu
table(example). |_. steinsgate.in |_. steinsgate.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|5 6 3
1 2
2 3
3 4
4 5
5 1
1 4
7 3 9 1 4
|9 1 4 7 4

|

h3. Explicaţie
 
...
 

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