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?

Input

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

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

Note

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