Петя ходит по ориентированному графу, состоящему из $$$n$$$ вершин и $$$m$$$ рёбер, и несёт в кармане неотрицательное целое число рублей. Если до прохода по ребру у Пети $$$x$$$ рублей, то за проход возьмётся плата в размере $$$\lfloor \sqrt{x} \rfloor$$$ рублей, где записью $$$\lfloor a \rfloor$$$ обозначается целая часть числа $$$a$$$.
В некоторых вершинах графа есть выходы: находясь в вершине $$$e$$$ и потратив $$$c_e$$$ рублей, Петя может закончить движение и покинуть граф. Для каждой из вершин графа определите минимальную сумму денег, стартовав с которой, Петя сможет добраться от этой вершины до какого-нибудь из выходов и покинуть граф.
В первой строке входных данных содержится три целых числа $$$n$$$, $$$m$$$ и $$$t$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le m \le 10^5$$$, $$$0 \le t \le n$$$) — количество вершин и рёбер в графе, а также количество выходов.
В следующих $$$m$$$ строках входных данных содержатся по два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$), означающих, что существует ребро из вершины $$$u$$$ в вершину $$$v$$$. Гарантируется, что в графе нет петель и кратных рёбер.
В следующих $$$t$$$ строках входных данных содержатся по два целых числа $$$e$$$ и $$$c_e$$$ ($$$1 \le e \le n$$$, $$$0 \le c_e \le 10^9$$$), означающих, что в вершине $$$e$$$ находится выход, требующий платы $$$c_e$$$ рублей. Гарантируется, что в каждой вершине находится не более одного выхода.
Выведите $$$n$$$ целых чисел на одной строке — минимальные суммы, нужные для покидания графа, начиная с каждой из его вершин, в порядке возрастания номеров вершин. Если из некоторой вершины покинуть граф невозможно, выведите для неё $$$-1$$$.
5 4 33 23 45 35 41 12 103 100
1 10 13 -1 17
4 4 21 22 33 11 41 02 1
0 0 0 -1
В первом примере из условия:
Во втором примере из условия: