CF1043E.Train Hard, Win Easy

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?

齐比是一名竞赛编程教练。共有 $n$ 名选手希望得到充分的训练。训练赛的形式十分特别——每支队伍由两人组成，共有两道题目，且每名选手恰好编写其中一道题目的代码。当然，同一支队伍中的两名选手必须编写不同的题目。

评分规则也同样非同寻常：第一题总是一道实现题——你需要非常快速地实现某个众所周知的算法，评分依据是你敲代码所用的时间；第二题则是一道糟糕的几何题，你只需在合理的时间内通过即可，此时代码的长度和难度至关重要。之后，齐比会为每份解答额外给予若干罚分（可能为负），而一支队伍的最终得分即为这两份解答罚分之和（得分越低越好）。

已知第 $i$ 名选手在编写第一题时的得分为 $x_i$，在编写第二题时的得分为 $y_i$。我们假设所有选手彼此了解对方的能力，并且在比赛中会以使队伍最终得分最小化的方式分配题目。注意，每名选手在一次比赛中恰好编写一道题。

齐比希望让所有选手两两组队参加比赛。然而，其中有 $m$ 对选手彼此极度反感，绝不会组队参赛。尽管如此，教练仍会为所有彼此不反感的选手对安排训练赛。教练关心的是：对每一名选手而言，他/她所参与的所有训练赛队伍的得分之和是多少？

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.

第一行包含两个整数 $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$）—— 表示不愿在同一队中参赛的两名参赛者的编号。每个无序索引对至多出现一次。

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

输出 $n$ 个整数——即所有参赛者的得分总和，顺序与输入中出现的顺序一致。

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...

在第一个例子中，将只有一支由第 $1$ 号和第 $3$ 号人员组成的队伍。他们的最优策略是将第一项任务分配给第 $3$ 号人员，第二项任务分配给第 $1$ 号人员，这样得到的总分为 $1 + 2 = 3$。

在第二个例子中，没有人喜欢其他人，因此不会有任何训练。看来在这种情况下，Zibi 将无法获得教练头衔……