Train Hard, Win Easy

题意翻译

题目描述 你是一个教练，现在有一场重要的比赛，有$n$个选手希望好好准备这一场比赛，所以你给他们安排了多场训练。训练中$2$个人组一队，有$2$道种类不同的题目，$2$个人一人选择其中的一道，但不能两个人选择同一道。对于每一个人，选择第一类题目会扣除$x_i$分数，选择第二类题目会扣除$y_i$分数，而最后的比赛成绩为$x_i+y_i$。$x_i,y_i$可能小于$0$。我们认为在训练开始前每一个人都知道所有人的$x,y$，所以当两个人$i,j$组队训练时，一定会选择扣分和较少的方案。 你现在希望每两个人之间组队进行训练，但是你又得知：有$m$对选手，它们不希望组队一起训练。那么，请你求出：在所有训练完成之后，每一个人参与过的训练的扣分分数之和。 输入数据 第一行两个正整数$n,m(2 \leq n \leq 300000,0 \leq m \leq 300000)$表示选手数量与不希望一起训练的选手对数 接下来$n$行每行两个整数$x,y(-10^9 \leq x,y \leq 10^9)$描述一个选手 接下来$m$行每行两个正整数$u,v(1 \leq u,v \leq n , u \neq v)$表示选手$u$和选手$v$之间不愿意一起训练。数据保证$1$对选手只会在输入中至多出现$1$次。 输出数据 一行$n$个整数，第$i$个数表示选手$i$参与的所有训练的扣分分数之和。

题目描述

Zibi is a competitive programming coach. There are $ n $ competitors who want to be prepared well. The training contests are quite unusual – there are two people in a team, two problems, and each competitor will code exactly one of them. Of course, people in one team will code different problems. Rules of scoring also aren't typical. The first problem is always an implementation problem: you have to implement some well-known algorithm very fast and the time of your typing is rated. The second one is an awful geometry task and you just have to get it accepted in reasonable time. Here the length and difficulty of your code are important. After that, Zibi will give some penalty points (possibly negative) for each solution and the final score of the team is the sum of them (the less the score is, the better). We know that the $ i $ -th competitor will always have score $ x_i $ when he codes the first task and $ y_i $ when he codes the second task. We can assume, that all competitors know each other's skills and during the contest distribute the problems in the way that minimizes their final score. Remember that each person codes exactly one problem in a contest. Zibi wants all competitors to write a contest with each other. However, there are $ m $ pairs of people who really don't like to cooperate and they definitely won't write a contest together. Still, the coach is going to conduct trainings for all possible pairs of people, such that the people in pair don't hate each other. The coach is interested for each participant, what will be his or her sum of scores of all teams he trained in?

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 2 \le n \le 300\,000 $ , $ 0 \le m \le 300\,000 $ ) — the number of participants and the number of pairs of people who will not write a contest together. Each of the next $ n $ lines contains two integers $ x_i $ and $ y_i $ ( $ -10^9 \le x_i, y_i \le 10^9 $ ) — the scores which will the $ i $ -th competitor get on the first problem and on the second problem. It is guaranteed that there are no two people having both $ x_i $ and $ y_i $ same. Each of the next $ m $ lines contain two integers $ u_i $ and $ v_i $ ( $ 1 \le u_i, v_i \le n $ , $ u_i \ne v_i $ ) — indices of people who don't want to write a contest in one team. Each unordered pair of indices will appear at most once.

输出格式

Output $ n $ integers — the sum of scores for all participants in the same order as they appear in the input.

输入输出样例

输入样例 #1

3 2
1 2
2 3
1 3
1 2
2 3

输出样例 #1

3 0 3 

输入样例 #2

3 3
1 2
2 3
1 3
1 2
2 3
1 3

输出样例 #2

0 0 0 

输入样例 #3

5 3
-1 3
2 4
1 1
3 5
2 2
1 4
2 3
3 5

输出样例 #3

4 14 4 16 10 

说明

In the first example, there will be only one team consisting of persons $ 1 $ and $ 3 $ . The optimal strategy for them is to assign the first task to the $ 3 $ -rd person and the second task to the $ 1 $ -st person, this will lead to score equal to $ 1 + 2 = 3 $ . In the second example, nobody likes anyone, so there won't be any trainings. It seems that Zibi won't be titled coach in that case...