Zibi 是一名竞技编程教练。有 $$$n$$$ 竞争对手希望做好充分准备。训练比赛很不寻常——一个团队中有两个人,两个问题,每个参赛者都会编写其中一个问题。当然,一个团队中的人员会编写不同的问题。
评分规则也不典型。第一个问题始终是实现问题:您必须非常快地实现一些众所周知的算法,并且对您的打字时间进行评级。第二个是一项可怕的几何任务,你只需要在合理的时间内接受它即可。在这里,代码的长度和难度很重要。之后,子笔会对每个解给予一些罚分(可能是负数),而队伍的最终得分就是它们的总和(得分越少越好)。
我们知道,第 $$$i$$$ 个参赛者在编写第一个任务时将始终获得 $$$x_i$$$ 分数,而在编写第二个任务时将始终获得 $$$y_i$$$ 分数。我们可以假设,所有参赛者都知道彼此的技能,并且在比赛期间以最小化最终得分的方式分配问题。请记住,每个人在竞赛中只编写一个问题。
Zibi 希望所有参赛者互相写一篇比赛。不过,也有$$$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$$$ 整数 - 所有参与者的分数总和,按照输入中出现的顺序排列。
示例
输入 #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
注意
在第一个示例中,只有一个团队由 $$$1$$$ 和 $$$3$$$ 组成。他们的最佳策略是将第一个任务分配给第 $$$3$$$-rd 个人,将第二个任务分配给第 $$$1$$$-st 个人,这将导致得分等于 $$$1 + 2 = 3$$$。
在第二个示例中,没有人喜欢任何人,因此不会有任何培训。看来这样子比就不能当教练了……