E. Тренируйcя усердно, выигрывай легко
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Зиби является тренером команд по спортивному программированию. Всего есть $$$n$$$ участников, которые хотят хорошо подготовиться к соревнованиям. Тренировочные контесты весьма необычны: в каждой команде есть ровно два человека, две задачи, и каждый участник будет писать ровно одну из них. Разумеется, два человека в одной команде будут писать разные задачи.

Правила оценки тоже весьма необычны. Первая задача всегда задача на реализацию: нужно реализовать один весьма известный алгоритм и оценивается время и скорость его написания. Вторая задача — ужасная задача на геометрию, которую нужно сдать хотя бы за какое-нибудь разумное время. Здесь оценивается длина и сложность кода. После этого Зиби даёт некоторые штрафные очки каждому решению (возможно, отрицательные) и итоговый результат команды равен их сумме (чем меньше сумма, тем лучше).

Мы знаем, что $$$i$$$-й участник наберёт ровно $$$x_i$$$ очков, если будет писать первую задачу, и ровно $$$y_i$$$, если будет писать вторую. Можно считать, что все участники знают способности друг друга и во время контеста распределят задачи таким образом, чтобы минимизировать их итоговый счёт. Напомним, каждый участник напишет ровно одну задачу за контест.

Зиби хочет, чтобы все участники написали тренировочный контест друг с другом. Однако есть $$$m$$$ пар участников, которые ни за что не хотят писать контест вместе. Тем не менее, тренер собирается провести тренировочный контест для всех возможных пар участников, которые не ненавидят друг друга. Для каждого участника тренеру интересно, какова будет сумма очков команд, в которых он примет участие.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 300\,000$$$, $$$0 \le m \le 300\,000$$$) — количество участников и количество пар людей, которые не будут писать контест вместе.

Каждая из следующих $$$n$$$ строк содержит два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) — очки, которые $$$i$$$-й участник наберёт на первой задаче и на второй. Гарантируется, что у никаких двух участников не совпадает одновременно и $$$x_i$$$, и $$$y_i$$$.

Каждая из следующих $$$m$$$ строк содержит два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$) — номера людей, которые не будут писать контест вместе. Каждая неупорядоченная пара людей встречает не более одного раза.

Выходные данные

Выведите $$$n$$$ целых чисел — суммарное количество очков для всех участников в том порядке, в котором они перечислены во входных данных.

Примеры
Входные данные
3 2
1 2
2 3
1 3
1 2
2 3
Выходные данные
3 0 3
Входные данные
3 3
1 2
2 3
1 3
1 2
2 3
1 3
Выходные данные
0 0 0
Входные данные
5 3
-1 3
2 4
1 1
3 5
2 2
1 4
2 3
3 5
Выходные данные
4 14 4 16 10
Примечание

В первом примере может быть только одна команда, состоящая из участников $$$1$$$ и $$$3$$$. В данной команде оптимальное стратегией будет отдать первую задачу участнику $$$3$$$, а вторую задачу участнику $$$1$$$, это приведёт к сумме очков равной $$$1 + 2 = 3$$$.

Во втором примере все друг друга ненавидят, а значит не будет ни одной тренировки. Наверное в таком случае Зиби не станет почётным тренером...