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.


-----Examples-----
Input
3 2
1 2
2 3
1 3
1 2
2 3

Output
3 0 3 
Input
3 3
1 2
2 3
1 3
1 2
2 3
1 3

Output
0 0 0 
Input
5 3
-1 3
2 4
1 1
3 5
2 2
1 4
2 3
3 5

Output
4 14 4 16 10 


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

Difficulty: HARD
Tags: Greedy algorithms

Sorting

Mathematics

Constructive algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
from __future__ import division, print_function
import io
import os
import sys
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from cStringIO import StringIO
	from future_builtins import ascii, filter, hex, map, oct, zip
else:
	from io import BytesIO as StringIO
(sys.stdout, stream) = (io.IOBase(), StringIO())
sys.stdout.flush = lambda : os.write(1, stream.getvalue()) and (not stream.truncate(0)) and stream.seek(0)
sys.stdout.write = stream.write if sys.version_info[0] < 3 else lambda s: stream.write(s.encode())
(input, flush) = (sys.stdin.readline, sys.stdout.flush)
numbers = []
(num, sign) = (0, True)
for char in os.read(0, os.fstat(0).st_size):
	if char >= 48:
		num = 10 * num + char - 48
	elif char == 45:
		sign = False
	elif char != 13:
		numbers.append(num if sign else -num)
		(num, sign) = (0, True)
if char >= 48:
	numbers.append(num if sign else -num)
getnum = iter(numbers).__next__

def main():
	(n, m) = (getnum(), getnum())
	c = [0] * n
	a = [[getnum(), getnum(), i] for i in range(n)]
	for _ in range(m):
		(x, y) = (getnum(), getnum())
		s = min(a[x - 1][0] + a[y - 1][1], a[x - 1][1] + a[y - 1][0])
		c[x - 1] -= s
		c[y - 1] -= s
	a.sort(key=lambda x: x[1] - x[0])
	sum_x = sum((i[0] for i in a))
	sum_y = 0
	for i in range(n):
		sum_x -= a[i][0]
		c[a[i][2]] += sum_x + (n - i - 1) * a[i][1] + sum_y + i * a[i][0]
		sum_y += a[i][1]
	print(*c)
main()


import os
import sys
from atexit import register
from io import BytesIO
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
sys.stdout = BytesIO()
true_write = sys.stdout.write
sys.stdout.write = lambda s: true_write(s.encode())
register(lambda : os.write(1, sys.stdout.getvalue()))

def main():
	(n, m) = map(int, input().split())
	c = [0] * n
	a = [[int(j) for j in input().split()] + [i] for i in range(n)]
	for _ in range(m):
		(x, y) = map(int, input().split())
		s = min(a[x - 1][0] + a[y - 1][1], a[x - 1][1] + a[y - 1][0])
		c[x - 1] -= s
		c[y - 1] -= s
	a.sort(key=lambda x: x[1] - x[0])
	sum_x = sum((i[0] for i in a))
	sum_y = 0
	for i in range(n):
		sum_x -= a[i][0]
		c[a[i][2]] += sum_x + (n - i - 1) * a[i][1] + sum_y + i * a[i][0]
		sum_y += a[i][1]
	print(*c)
main()


import sys, io
BUF_SIZ = 65536
input = iter(io.BufferedReader(io.FileIO(sys.stdin.fileno()), BUF_SIZ).read().splitlines()).__next__
(n, m) = map(int, input().split())
(x, y) = ([0] * n, [0] * n)
for i in range(n):
	(x[i], y[i]) = map(int, input().split())
t = list(range(n))
t.sort(key=lambda i: x[i] - y[i])
pre = [0] * (n + 1)
for i in range(n):
	pre[i] = pre[i - 1] + x[t[i]]
suf = 0
ans = [0] * n
for i in range(n - 1, -1, -1):
	ans[t[i]] = pre[i - 1] + suf + i * y[t[i]] + (n - i - 1) * x[t[i]]
	suf += y[t[i]]
for _ in range(m):
	(u, v) = map(int, input().split())
	d = min(x[u - 1] + y[v - 1], y[u - 1] + x[v - 1])
	ans[u - 1] -= d
	ans[v - 1] -= d
out = b' '.join((str(v).encode() for v in ans))
io.BufferedWriter(io.FileIO(sys.stdout.fileno(), 'w'), BUF_SIZ).write(out)


import sys
(n, m) = [int(x) for x in sys.stdin.buffer.readline().split()]
s = sys.stdin.buffer.read()
inp = []
sign = 1
numb = 0
for i in range(len(s)):
	if s[i] >= 48:
		numb = 10 * numb + s[i] - 48
	elif s[i] == 45:
		sign = -1
	elif s[i] != 13:
		inp.append(sign * numb)
		numb = 0
		sign = 1
if s[-1] >= 48:
	inp.append(sign * numb)
order = sorted(range(n), key=lambda i: inp[2 * i] - inp[2 * i + 1])
score = [0] * n
val = sum(inp[1:2 * n:2])
for ind in range(n):
	i = order[ind]
	score[i] += val + inp[2 * i + 1] * (ind - 1) + inp[2 * i] * (n - ind - 1)
	val += inp[2 * i] - inp[2 * i + 1]
for _ in range(m):
	u = inp[2 * n + 2 * _] - 1
	v = inp[2 * n + 2 * _ + 1] - 1
	s = min(inp[2 * u] + inp[2 * v + 1], inp[2 * v] + inp[2 * u + 1])
	score[u] -= s
	score[v] -= s

def print(*A, sep=' ', end='\n'):
	sys.stdout.buffer.write(sep.encode('ascii').join(((x if x is str else str(x)).encode('ascii') for x in A)))
	sys.stdout.buffer.write(end.encode('ascii'))
print(*score)


import sys
(n, m) = [int(x) for x in sys.stdin.readline().split()]
s = sys.stdin.read()
inp = []
sign = 1
numb = 0
for i in range(len(s)):
	if ord(s[i]) >= 48:
		numb = 10 * numb + ord(s[i]) - 48
	elif ord(s[i]) == 45:
		sign = -1
	elif ord(s[i]) != 13:
		inp.append(sign * numb)
		numb = 0
		sign = 1
if ord(s[-1]) >= 48:
	inp.append(sign * numb)
order = sorted(range(n), key=lambda i: inp[2 * i] - inp[2 * i + 1])
score = [0] * n
val = sum(inp[1:2 * n:2])
for ind in range(n):
	i = order[ind]
	score[i] += val + inp[2 * i + 1] * (ind - 1) + inp[2 * i] * (n - ind - 1)
	val += inp[2 * i] - inp[2 * i + 1]
for _ in range(m):
	u = inp[2 * n + 2 * _] - 1
	v = inp[2 * n + 2 * _ + 1] - 1
	s = min(inp[2 * u] + inp[2 * v + 1], inp[2 * v] + inp[2 * u + 1])
	score[u] -= s
	score[v] -= s
sys.stdout.write(' '.join((str(x) for x in score)))


from __future__ import division, print_function
import itertools
import os
import sys
from atexit import register
if sys.version_info[0] < 3:
	from cStringIO import StringIO
	range = xrange
	filter = itertools.ifilter
	map = itertools.imap
	zip = itertools.izip
else:
	from io import BytesIO as StringIO
input = StringIO(os.read(0, os.fstat(0).st_size)).readline
sys.stdout = StringIO()
register(lambda : os.write(1, sys.stdout.getvalue()))
if sys.version_info[0] >= 3:
	_write = sys.stdout.write
	sys.stdout.write = lambda s: _write(s.encode())

def main():
	(n, m) = map(int, input().split())
	c = [0] * n
	a = [[int(j) for j in input().split()] + [i] for i in range(n)]
	for _ in range(m):
		(x, y) = map(int, input().split())
		s = min(a[x - 1][0] + a[y - 1][1], a[x - 1][1] + a[y - 1][0])
		c[x - 1] -= s
		c[y - 1] -= s
	a.sort(key=lambda x: x[1] - x[0])
	sum_x = sum((i[0] for i in a))
	sum_y = 0
	for i in range(n):
		sum_x -= a[i][0]
		c[a[i][2]] += sum_x + (n - i - 1) * a[i][1] + sum_y + i * a[i][0]
		sum_y += a[i][1]
	print(*c)
main()


import os
import sys
from _io import BytesIO

class FastI:

	def __init__(self):
		self.stream = BytesIO()
		self.newlines = 0

	def read(self, b=b'\n'):
		while b:
			(b, ptr) = (os.read(0, (1 << 13) + os.fstat(0).st_size), self.stream.tell())
			(self.stream.seek(0, 2), self.steram.write(b), self.stream.seek(ptr))
		return self.stream.read() if self.stream.tell() else self.stream.getvalue()

	def readline(self, b=b'\n'):
		while b and self.newlines == 0:
			(b, ptr) = (os.read(0, (1 << 13) + os.fstat(0).st_size), self.stream.tell())
			(self.stream.seek(0, 2), self.stream.write(b), self.stream.seek(ptr))
			self.newlines += b.count(b'\n')
		self.newlines -= bool(b)
		return self.stream.readline()

	def readnumbers(self, var=int):
		(numbers, b) = ([], self.read())
		(num, sign) = (var(0), 1)
		for char in b:
			if char >= b'0'[0]:
				num = 10 * num + char - 48
			elif char == b'-'[0]:
				sign = -1
			elif char != b'\r'[0]:
				if char == b'\n'[0]:
					self.newlines -= 1
				numbers.append(sign * num)
				(num, sign) = (var(0), 1)
		if b and b[-1] >= b'0'[0]:
			numbers.append(sign * num)
		return numbers

	def _readnumbers(self, n, var=int):
		ptr = self.stream.tell()
		self.stream.seek(0, 2)
		buffsize = self.stream.tell()
		self.stream.seek(ptr)
		A = []
		(num, sign) = (var(0), 1)
		while len(A) != n:
			if ptr == buffsize:
				(s, _ptr) = (os.read(0, (1 << 13) + os.fstat(0).st_size), self.stream.tell())
				(self.stream.seek(0, 2), self.stream.write(s), self.stream.seek(_ptr))
				buffsize += len(s)
				self.newlines += s.count(b'\n') + (not s)
				if ptr == buffsize:
					break
			for (i, c) in enumerate(self.stream.read(min(64, buffsize - ptr))):
				if c >= b'0'[0]:
					num = num * 10 + c - 48
				elif c == b'-'[0]:
					sign = -1
				elif c != b'\r'[0]:
					if c == b'\n'[0]:
						self.newlines -= 1
					A.append(sign * num)
					(num, sign) = (var(0), 1)
					if len(A) == n:
						break
			ptr += i + 1
		if ptr == buffsize and (self.stream.seek(-1, 2) or True) and (self.stream.read(1)[0] >= b'0'[0]):
			self.newlines -= 1
			A.append(sign * num)
		assert n == -1 or len(A) == n
		self.stream.seek(ptr)
		return A

class FastO:

	def __init__(self):
		stream = BytesIO()
		self.flush = lambda : os.write(1, stream.getvalue()) and (not stream.truncate(0)) and stream.seek(0)
		self.write = lambda s: stream.write(s.encode())
(sys.stdin, sys.stdout) = (FastI(), FastO())
(input, flush) = (sys.stdin.readline, sys.stdout.flush)

def main():
	(n, m) = map(int, input().split())
	c = [0] * n
	a = [sys.stdin._readnumbers(2) + [i] for i in range(n)]
	for _ in range(m):
		(x, y) = map(int, input().split())
		s = min(a[x - 1][0] + a[y - 1][1], a[x - 1][1] + a[y - 1][0])
		c[x - 1] -= s
		c[y - 1] -= s
	a.sort(key=lambda x: x[1] - x[0])
	sum_x = sum((i[0] for i in a))
	sum_y = 0
	for i in range(n):
		sum_x -= a[i][0]
		c[a[i][2]] += sum_x + (n - i - 1) * a[i][1] + sum_y + i * a[i][0]
		sum_y += a[i][1]
	print(*c)
main()


import io
import os
import sys

class FastI(io.BytesIO):

	def __init__(self):
		self.newlines = 0

	def read(self, b=b'\n'):
		while b:
			(b, ptr) = (os.read(0, (1 << 13) + os.fstat(0).st_size), self.tell())
			(self.seek(0, 2), self.write(b), self.seek(ptr))
		return super(FastI, self).read() if self.stream.tell() else self.getvalue()

	def readline(self, b=b'\n'):
		while b and self.newlines == 0:
			(b, ptr) = (os.read(0, (1 << 13) + os.fstat(0).st_size), self.tell())
			(self.seek(0, 2), self.write(b), self.seek(ptr))
			self.newlines += b.count(b'\n')
		self.newlines -= 1
		return super(FastI, self).readline()

	def readnumbers(self, var=int):
		(numbers, b) = ([], self.read())
		(num, sign) = (var(0), 1)
		for char in b:
			if char >= b'0'[0]:
				num = 10 * num + char - 48
			elif char == b'-'[0]:
				sign = -1
			elif char != b'\r'[0]:
				numbers.append(sign * num)
				(num, sign) = (var(0), 1)
		if b and b[-1] >= b'0'[0]:
			numbers.append(sign * num)
		return numbers
(sys.stdin, sys.stdout, stream) = (FastI(), io.IOBase(), io.BytesIO())
sys.stdout.flush = lambda : os.write(1, stream.getvalue()) and (not stream.truncate(0)) and stream.seek(0)
sys.stdout.write = lambda s: stream.write(s.encode())
(input, flush) = (sys.stdin.readline, sys.stdout.flush)

def main():
	(n, m) = map(int, input().split())
	c = [0] * n
	a = [[int(j) for j in input().split()] + [i] for i in range(n)]
	for _ in range(m):
		(x, y) = map(int, input().split())
		s = min(a[x - 1][0] + a[y - 1][1], a[x - 1][1] + a[y - 1][0])
		c[x - 1] -= s
		c[y - 1] -= s
	a.sort(key=lambda x: x[1] - x[0])
	sum_x = sum((i[0] for i in a))
	sum_y = 0
	for i in range(n):
		sum_x -= a[i][0]
		c[a[i][2]] += sum_x + (n - i - 1) * a[i][1] + sum_y + i * a[i][0]
		sum_y += a[i][1]
	print(*c)
main()


from __future__ import division, print_function
import itertools
import os
import sys
from atexit import register
if sys.version_info[0] < 3:
	from cStringIO import StringIO
	range = xrange
	filter = itertools.ifilter
	map = itertools.imap
	zip = itertools.izip
else:
	from io import BytesIO as StringIO
sys.stdout = StringIO()
register(lambda : os.write(1, sys.stdout.getvalue()))
if sys.version_info[0] >= 3:
	_write = sys.stdout.write
	sys.stdout.write = lambda s: _write(s.encode())
s = os.read(0, os.fstat(0).st_size)
inp = []
sign = 1
numb = 0
for i in range(len(s)):
	if s[i] >= 48:
		numb = 10 * numb + s[i] - 48
	elif s[i] == 45:
		sign = -1
	elif s[i] != 13:
		inp.append(sign * numb)
		numb = 0
		sign = 1
if s[-1] >= 48:
	inp.append(sign * numb)
n = inp[0]
m = inp[1]
for i in range(2, 2 * n + 2):
	inp[i] *= 1.0
order = sorted(range(n), key=lambda i: inp[2 * i + 2] - inp[2 * i + 3])
score = [0.0] * n
val = sum(inp[3:2 * n + 2:2])
for ind in range(n):
	i = order[ind]
	score[i] += val + inp[2 * i + 3] * (ind - 1) + inp[2 * i + 2] * (n - ind - 1)
	val += inp[2 * i + 2] - inp[2 * i + 3]
for _ in range(m):
	u = inp[2 * n + 2 * _ + 2] - 1
	v = inp[2 * n + 2 * _ + 3] - 1
	s = min(inp[2 * u + 2] + inp[2 * v + 3], inp[2 * v + 2] + inp[2 * u + 3])
	score[u] -= s
	score[v] -= s
print(*map(int, score))


from sys import stdin
from operator import add
from itertools import repeat

def main():
	(n, m) = map(int, stdin.readline().split())
	inp = list(map(int, stdin.read().split(), repeat(10, 2 * n + 2 * m)))
	xys = inp[:2 * n]
	exc = list(map(add, inp[2 * n:], repeat(-1)))
	a = list(range(n))
	a.sort(key=lambda i: xys[2 * i] - xys[2 * i + 1])
	(xs, ys) = (0, sum(xys[1::2]))
	res = [0] * n
	for (i, idx) in enumerate(a):
		(x, y) = (xys[2 * idx], xys[2 * idx + 1])
		ys -= y
		res[idx] = i * y + (n - 1 - i) * x + xs + ys
		xs += x
	for i in range(m):
		(u, v) = (exc[2 * i], exc[2 * i + 1])
		dif = min(xys[2 * u] + xys[2 * v + 1], xys[2 * v] + xys[2 * u + 1])
		res[u] -= dif
		res[v] -= dif
	print(' '.join(map(str, res)))
main()


import io
stdin = io.FileIO(0)
(n, m) = [int(x) for x in stdin.readline().split()]
s = stdin.read()
inp = []
sign = 1
numb = 0
for i in range(len(s)):
	if s[i] >= 48:
		numb = 10 * numb + s[i] - 48
	elif s[i] == 45:
		sign = -1
	elif s[i] != 13:
		inp.append(sign * numb)
		numb = 0
		sign = 1
if s[-1] >= 48:
	inp.append(sign * numb)
order = sorted(range(n), key=lambda i: inp[2 * i] - inp[2 * i + 1])
score = [0] * n
val = sum(inp[1:2 * n:2])
for ind in range(n):
	i = order[ind]
	score[i] += val + inp[2 * i + 1] * (ind - 1) + inp[2 * i] * (n - ind - 1)
	val += inp[2 * i] - inp[2 * i + 1]
for _ in range(m):
	u = inp[2 * n + 2 * _] - 1
	v = inp[2 * n + 2 * _ + 1] - 1
	s = min(inp[2 * u] + inp[2 * v + 1], inp[2 * v] + inp[2 * u + 1])
	score[u] -= s
	score[v] -= s
io.FileIO(1, 'w').write(b' '.join((str(x).encode() for x in score)))


import sys
(n, m) = [int(x) for x in sys.stdin.buffer.readline().split()]
inp = [int(x) for x in sys.stdin.buffer.read().split()]
order = sorted(range(n), key=lambda i: inp[2 * i] - inp[2 * i + 1])
score = [0] * n
val = sum(inp[1:2 * n:2])
for ind in range(n):
	i = order[ind]
	score[i] += val + inp[2 * i + 1] * (ind - 1) + inp[2 * i] * (n - ind - 1)
	val += inp[2 * i] - inp[2 * i + 1]
for _ in range(m):
	u = inp[2 * n + 2 * _] - 1
	v = inp[2 * n + 2 * _ + 1] - 1
	s = min(inp[2 * u] + inp[2 * v + 1], inp[2 * v] + inp[2 * u + 1])
	score[u] -= s
	score[v] -= s
sys.stdout.write(' '.join((str(x) for x in score)))


import os
import sys
from io import BytesIO

class FastI:

	def __init__(self):
		self.stream = BytesIO()
		self.newlines = 0

	def read(self, b=b'\n'):
		while b:
			(b, ptr) = (os.read(0, (1 << 13) + os.fstat(0).st_size), self.stream.tell())
			(self.stream.seek(0, 2), self.stream.write(b), self.stream.seek(ptr))
		return self.stream.read() if self.stream.tell() else self.stream.getvalue()

	def readline(self, b=b'\n'):
		while b and (not self.newlines):
			(b, ptr) = (os.read(0, (1 << 13) + os.fstat(0).st_size), self.stream.tell())
			(self.stream.seek(0, 2), self.stream.write(b), self.stream.seek(ptr))
			self.newlines += b.count(b'\n')
		self.newlines -= bool(b)
		return self.stream.readline()

	def readnumbers(self, var=int):
		(numbers, b) = ([], self.read())
		(num, sign) = (var(0), 1)
		for char in b:
			if char >= 48:
				num = 10 * num + char - 48
			elif char == 45:
				sign = -1
			elif char != 13:
				numbers.append(sign * num)
				(num, sign) = (var(0), 1)
		if b and b[-1] >= 48:
			numbers.append(sign * num)
		return numbers

class FastO:

	def __init__(self):
		stream = BytesIO()
		self.flush = lambda : os.write(1, stream.getvalue()) and (not stream.truncate(0)) and stream.seek(0)
		self.write = lambda s: stream.write(s.encode())
(sys.stdin, sys.stdout) = (FastI(), FastO())
(input, flush) = (lambda : sys.stdin.readline().rstrip('\r\n'), sys.stdout.flush)

class readnumbers:
	(numbers, ind) = (sys.stdin.readnumbers(), 0)

	@classmethod
	def getnum(cls):
		cls.ind += 1
		return cls.numbers[cls.ind - 1]
getnum = readnumbers.getnum

def main():
	(n, m) = (getnum(), getnum())
	c = [0] * n
	a = [[getnum(), getnum(), i] for i in range(n)]
	for _ in range(m):
		(x, y) = (getnum(), getnum())
		s = min(a[x - 1][0] + a[y - 1][1], a[x - 1][1] + a[y - 1][0])
		c[x - 1] -= s
		c[y - 1] -= s
	a.sort(key=lambda x: x[1] - x[0])
	sum_x = sum((i[0] for i in a))
	sum_y = 0
	for i in range(n):
		sum_x -= a[i][0]
		c[a[i][2]] += sum_x + (n - i - 1) * a[i][1] + sum_y + i * a[i][0]
		sum_y += a[i][1]
	print(*c)
main()


import sys
(n, m) = [int(x) for x in sys.stdin.buffer.readline().split()]
s = sys.stdin.buffer.read()
inp = []
sign = 1
numb = 0
for i in range(len(s)):
	if s[i] >= 48:
		numb = 10 * numb + s[i] - 48
	elif s[i] == 45:
		sign = -1
	elif s[i] != 13:
		inp.append(sign * numb)
		numb = 0
		sign = 1
if s[-1] >= 48:
	inp.append(sign * numb)
order = sorted(range(n), key=lambda i: inp[2 * i] - inp[2 * i + 1])
score = [0] * n
val = sum(inp[1:2 * n:2])
for ind in range(n):
	i = order[ind]
	score[i] += val + inp[2 * i + 1] * (ind - 1) + inp[2 * i] * (n - ind - 1)
	val += inp[2 * i] - inp[2 * i + 1]
for _ in range(m):
	u = inp[2 * n + 2 * _] - 1
	v = inp[2 * n + 2 * _ + 1] - 1
	s = min(inp[2 * u] + inp[2 * v + 1], inp[2 * v] + inp[2 * u + 1])
	score[u] -= s
	score[v] -= s
dig2byte = [b'0', b'1', b'2', b'3', b'4', b'5', b'6', b'7', b'8', b'9', b'-']

def to_byte(x):
	if x == 0:
		return dig2byte[0]
	if x < 0:
		sign = -1
		x *= -1
	else:
		sign = 1
	bts = []
	while x:
		y = x // 10
		bts.append(dig2byte[x - y * 10])
		x = y
	if sign < 0:
		bts.append(dig2byte[-1])
	return b''.join(reversed(bts))
sys.stdout.buffer.write(b' '.join((to_byte(x) for x in score)))


import os
import sys
from io import BytesIO

class FastI:

	def __init__(self):
		self.stream = BytesIO()
		self.newlines = 0

	def read(self, b=b'\n'):
		while b:
			(b, ptr) = (os.read(0, (1 << 13) + os.fstat(0).st_size), self.stream.tell())
			(self.stream.seek(0, 2), self.stream.write(b), self.stream.seek(ptr))
		return self.stream.read() if self.stream.tell() else self.stream.getvalue()

	def readline(self, b=b'\n'):
		while b and (not self.newlines):
			(b, ptr) = (os.read(0, (1 << 13) + os.fstat(0).st_size), self.stream.tell())
			(self.stream.seek(0, 2), self.stream.write(b), self.stream.seek(ptr))
			self.newlines += b.count(b'\n')
		self.newlines -= bool(b)
		return self.stream.readline()

	def readnumbers(self, var=int):
		(numbers, b) = ([], self.read())
		(num, sign) = (var(0), 1)
		for char in b:
			if char >= 48:
				num = 10 * num + char - 48
			elif char == 45:
				sign = -1
			elif char != 13:
				numbers.append(sign * num)
				(num, sign) = (var(0), 1)
		if b and b[-1] >= 48:
			numbers.append(sign * num)
		return numbers

class FastO:

	def __init__(self):
		stream = BytesIO()
		self.flush = lambda : os.write(1, stream.getvalue()) and (not stream.truncate(0)) and stream.seek(0)
		self.write = lambda s: stream.write(s.encode())
(sys.stdin, sys.stdout) = (FastI(), FastO())
(readline, readnumbers) = (sys.stdin.readline, sys.stdin.readnumbers)
(input, flush) = (lambda : sys.stdin.readline().rstrip('\r\n'), sys.stdout.flush)
inp = sys.stdin.readnumbers(float)
n = int(inp[0])
m = int(inp[1])
order = sorted(range(n), key=lambda i: inp[2 * i + 2] - inp[2 * i + 3])
score = [0.0] * n
val = sum(inp[3:2 * n + 2:2])
for ind in range(n):
	i = int(order[ind])
	score[i] += val + inp[2 * i + 3] * (ind - 1) + inp[2 * i + 2] * (n - ind - 1)
	val += inp[2 * i + 2] - inp[2 * i + 3]
for _ in range(m):
	u = int(inp[2 * n + 2 * _ + 2] - 1.0)
	v = int(inp[2 * n + 2 * _ + 3] - 1.0)
	s = min(inp[2 * u + 2] + inp[2 * v + 3], inp[2 * v + 2] + inp[2 * u + 3])
	score[u] -= s
	score[v] -= s
print(*map(int, score))


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

class FastI(BytesIO):

	def __init__(self, fd=0, bufsize=8192):
		self.newlines = 0
		self.fd = fd
		self.bufsize = bufsize

	def readline(self):
		while self.newlines == 0:
			(b, ptr) = (os.read(self.fd, self.bufsize + os.fstat(self.fd).st_size), self.tell())
			(self.seek(0, 2), self.write(b), self.seek(ptr))
			self.newlines += b.count(b'\n') + (not b)
		self.newlines -= 1
		return super(FastI, self).readline()

class FastO(IOBase):

	def __init__(self, fd=1):
		stream = BytesIO()
		self.flush = lambda : os.write(fd, stream.getvalue()) and (not stream.truncate(0)) and stream.seek(0)
		self.write = stream.write if sys.version_info[0] < 3 else lambda b: stream.write(b.encode())

class ostream:

	def __lshift__(self, a):
		if a == endl:
			sys.stdout.write('\n')
			sys.stdout.flush()
		else:
			sys.stdout.write(str(a))
		return self

class istream:
	inp = []

	def cin(self):
		while not self.inp:
			self.inp = sys.stdin.readline().split()[::-1]
		return self.inp.pop()
(sys.stdin, sys.stdout) = (FastI(), FastO())
(input, flush) = (sys.stdin.readline, sys.stdout.flush)
(cin, cout, endl) = (istream().cin, ostream(), object())

def main():
	(n, m) = (int(cin()), int(cin()))
	c = [0] * n
	a = [[int(cin()), int(cin()), i] for i in range(n)]
	for _ in range(m):
		(x, y) = (int(cin()), int(cin()))
		s = min(a[x - 1][0] + a[y - 1][1], a[x - 1][1] + a[y - 1][0])
		c[x - 1] -= s
		c[y - 1] -= s
	a.sort(key=lambda x: x[1] - x[0])
	sum_x = sum((i[0] for i in a))
	sum_y = 0
	for i in range(n):
		sum_x -= a[i][0]
		c[a[i][2]] += sum_x + (n - i - 1) * a[i][1] + sum_y + i * a[i][0]
		sum_y += a[i][1]
	for i in range(n):
		cout << c[i] << ' '
main()


import os
import sys
from io import BytesIO
sys.stdout = BytesIO()
_write = sys.stdout.write
sys.stdout.write = lambda s: _write(s.encode())
s = os.read(0, os.fstat(0).st_size)
inp = []
sign = 1
numb = 0
for i in range(len(s)):
	if s[i] >= 48:
		numb = 10 * numb + s[i] - 48
	elif s[i] == 45:
		sign = -1
	elif s[i] != 13:
		inp.append(sign * numb)
		numb = 0
		sign = 1
if s[-1] >= 48:
	inp.append(sign * numb)
n = inp[0]
m = inp[1]
for i in range(2, 2 * n + 2):
	inp[i] *= 1.0
order = sorted(range(n), key=lambda i: inp[2 * i + 2] - inp[2 * i + 3])
score = [0.0] * n
val = sum(inp[3:2 * n + 2:2])
for ind in range(n):
	i = order[ind]
	score[i] += val + inp[2 * i + 3] * (ind - 1) + inp[2 * i + 2] * (n - ind - 1)
	val += inp[2 * i + 2] - inp[2 * i + 3]
for _ in range(m):
	u = inp[2 * n + 2 * _ + 2] - 1
	v = inp[2 * n + 2 * _ + 3] - 1
	s = min(inp[2 * u + 2] + inp[2 * v + 3], inp[2 * v + 2] + inp[2 * u + 3])
	score[u] -= s
	score[v] -= s
print(*map(int, score))
os.write(1, sys.stdout.getvalue())


import sys
import os
sys.stdin = sys.stdin.detach()
s = sys.stdin.read()
n = m = -1
numb = 0
for i in range(len(s)):
	if s[i] >= 48:
		numb = 10 * numb + s[i] - 48
	elif s[i] != 13:
		if n == -1:
			n = numb
		elif m == -1:
			m = numb
		else:
			break
		numb = 0
inp = []
sign = 1
j = 0
for i in range(i, len(s)):
	if s[i] >= 48:
		numb = 10 * numb + s[i] - 48
	elif s[i] == 45:
		sign = -1
	elif s[i] != 13:
		inp.append(sign * numb)
		numb = 0
		sign = 1
if s[-1] >= 48:
	inp.append(sign * numb)
order = sorted(range(n), key=lambda i: inp[2 * i] - inp[2 * i + 1])
score = [0] * n
val = sum(inp[1:2 * n:2])
for ind in range(n):
	i = order[ind]
	score[i] += val + inp[2 * i + 1] * (ind - 1) + inp[2 * i] * (n - ind - 1)
	val += inp[2 * i] - inp[2 * i + 1]
for _ in range(m):
	u = inp[2 * n + 2 * _] - 1
	v = inp[2 * n + 2 * _ + 1] - 1
	s = min(inp[2 * u] + inp[2 * v + 1], inp[2 * v] + inp[2 * u + 1])
	score[u] -= s
	score[v] -= s
sys.stdout.write(' '.join((str(x) for x in score)))


from __future__ import division, print_function
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import BytesIO, IOBase

class FastI(BytesIO):
	bufferedlines = 0

	def __init__(self, fd=0, buffersize=2 ** 14):

		def read2buffer():
			(curpos, s) = (self.tell(), os.read(fd, buffersize + os.fstat(fd).st_size))
			return [s, self.seek(0, 2), self.write(s), self.seek(curpos)][0]
		self.read2buffer = read2buffer

	def read(self):
		while self.read2buffer():
			pass
		return self.getvalue() if self.tell() == 0 else super(FastI, self).read()

	def readline(self):
		while self.bufferedlines == 0:
			s = self.read2buffer()
			self.bufferedlines += s.count(b'\n') + (not s)
		self.bufferedlines -= 1
		return super(FastI, self).readline()

	def input(self):
		return self.readline().rstrip(b'\r\n')

class FastO(IOBase):

	def __init__(self, fd=1):
		stream = BytesIO()
		self.flush = lambda : os.write(fd, stream.getvalue()) + stream.truncate(0)
		self.write = stream.write if py2 else lambda s: stream.write(s.encode())
(sys.stdin, sys.stdout) = (FastI(), FastO())
input = sys.stdin.input

def main():
	(n, m) = map(int, input().split())
	c = [0] * n
	a = [[int(j) for j in input().split()] + [i] for i in range(n)]
	for _ in range(m):
		(x, y) = map(int, input().split())
		s = min(a[x - 1][0] + a[y - 1][1], a[x - 1][1] + a[y - 1][0])
		c[x - 1] -= s
		c[y - 1] -= s
	a.sort(key=lambda x: x[1] - x[0])
	sum_x = sum((i[0] for i in a))
	sum_y = 0
	for i in range(n):
		sum_x -= a[i][0]
		c[a[i][2]] += sum_x + (n - i - 1) * a[i][1] + sum_y + i * a[i][0]
		sum_y += a[i][1]
	print(*c)
main()


import sys, io
input = iter(sys.stdin.buffer.read().splitlines()).__next__
(n, m) = map(int, input().split())
(x, y) = ([0] * n, [0] * n)
for i in range(n):
	(x[i], y[i]) = map(int, input().split())
t = list(range(n))
t.sort(key=lambda i: x[i] - y[i])
pre = [0] * (n + 1)
for i in range(n):
	pre[i] = pre[i - 1] + x[t[i]]
suf = 0
ans = [0] * n
for i in range(n - 1, -1, -1):
	ans[t[i]] = pre[i - 1] + suf + i * y[t[i]] + (n - i - 1) * x[t[i]]
	suf += y[t[i]]
for _ in range(m):
	(u, v) = map(int, input().split())
	d = min(x[u - 1] + y[v - 1], y[u - 1] + x[v - 1])
	ans[u - 1] -= d
	ans[v - 1] -= d
out = b' '.join((str(v).encode() for v in ans))
sys.stdout.buffer.write(out)


import os, sys, atexit

def fast3():
	import os, sys, atexit
	from io import BytesIO
	sys.stdout = BytesIO()
	_write = sys.stdout.write
	sys.stdout.write = lambda s: _write(s.encode())
	atexit.register(lambda : os.write(1, sys.stdout.getvalue()))
	return BytesIO(os.read(0, os.fstat(0).st_size)).readline

def arr_sum(arr):
	(tem, tem1) = ([0], [0])
	for i in range(len(arr)):
		tem.append(tem[i] + arr[i][1][0])
		tem1.append(tem1[i] + arr[i][1][1])
	return (tem, tem1)
input = fast3()
rints = lambda : [int(x) for x in input().split()]
rints_2d = lambda n: [rints() for _ in range(n)]
rints_enu = lambda n: [(i + 1, rints()) for i in range(n)]
(n, m) = rints()
(a, edges, ans) = (rints_enu(n), rints_2d(m), [0] * n)
for (u, v) in edges:
	cost = min(a[u - 1][1][0] + a[v - 1][1][1], a[u - 1][1][1] + a[v - 1][1][0])
	ans[u - 1] -= cost
	ans[v - 1] -= cost
a.sort(key=lambda x: x[1][0] - x[1][1])
(cumx, cumy) = arr_sum(a)
for i in range(n):
	ans[a[i][0] - 1] += cumy[-1] - cumy[i + 1] + cumx[i] + a[i][1][0] * (n - i - 1) + a[i][1][1] * i
print(' '.join(map(str, ans)))


import os
from io import BytesIO
if os.name == 'nt':
	input = BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main():
	(n, m) = map(int, input().split())
	a = list(enumerate((tuple(map(int, input().split())) for _ in range(n))))
	b = (tuple(map(int, input().split())) for _ in range(m))
	c = a.copy()
	a.sort(key=lambda x: x[1][0] - x[1][1])
	sum_y = sum((x[1][1] for x in a))
	sum_x = 0
	res = [0] * n
	cnt = n - 1
	for (i, (x, y)) in a:
		sum_y -= y
		res[i] = x * cnt + y * (n - cnt - 1) + sum_x + sum_y
		sum_x += x
		cnt -= 1
	for (x, y) in b:
		(x, y) = (x - 1, y - 1)
		cost = min(c[x][1][0] + c[y][1][1], c[x][1][1] + c[y][1][0])
		res[x] -= cost
		res[y] -= cost
	print(*res, sep=' ')
main()


import sys
import io
(n, m) = [int(x) for x in sys.stdin.buffer.readline().split()]
s = sys.stdin.buffer.read()
inp = []
sign = 1
numb = 0
for i in range(len(s)):
	if s[i] >= 48:
		numb = 10 * numb + s[i] - 48
	elif s[i] == 45:
		sign = -1
	elif s[i] != 13:
		inp.append(sign * numb)
		numb = 0
		sign = 1
if s[-1] >= 48:
	inp.append(sign * numb)
order = sorted(range(n), key=lambda i: inp[2 * i] - inp[2 * i + 1])
score = [0] * n
val = sum(inp[1:2 * n:2])
for ind in range(n):
	i = order[ind]
	score[i] += val + inp[2 * i + 1] * (ind - 1) + inp[2 * i] * (n - ind - 1)
	val += inp[2 * i] - inp[2 * i + 1]
for _ in range(m):
	u = inp[2 * n + 2 * _] - 1
	v = inp[2 * n + 2 * _ + 1] - 1
	s = min(inp[2 * u] + inp[2 * v + 1], inp[2 * v] + inp[2 * u + 1])
	score[u] -= s
	score[v] -= s
sys.stdout = io.StringIO()
print(*score)
sys.__stdout__.write(sys.stdout.getvalue())


import sys
input = sys.stdin.readline
(n, m) = [int(x) for x in input().split()]
s = sys.stdin.read()
j = 0
inp = []
numb = 0
if s[j] == '-':
	sign = -1
	j += 1
else:
	sign = 1
while j < len(s) - 1:
	numb = 10 * numb + ord(s[j]) - 48
	j += 1
	if s[j] < '-':
		inp.append(sign * numb)
		j += 1
		if j < len(s) and s[j] == '-':
			sign = -1
			j += 1
		else:
			sign = 1
		numb = 0
if j == len(s) - 1:
	numb = 10 * numb + ord(s[j]) - 48
	inp.append(sign * numb)
order = sorted(range(n), key=lambda i: inp[2 * i] - inp[2 * i + 1])
score = [0] * n
val = sum(inp[1:2 * n:2])
for ind in range(n):
	i = order[ind]
	score[i] += val + inp[2 * i + 1] * (ind - 1) + inp[2 * i] * (n - ind - 1)
	val += inp[2 * i] - inp[2 * i + 1]
for _ in range(m):
	u = inp[2 * n + 2 * _] - 1
	v = inp[2 * n + 2 * _ + 1] - 1
	s = min(inp[2 * u] + inp[2 * v + 1], inp[2 * v] + inp[2 * u + 1])
	score[u] -= s
	score[v] -= s
sys.stdout.write(' '.join((str(x) for x in score)))


import os
import sys
from io import BytesIO

class FastI:

	def __init__(self):
		self.stream = BytesIO()
		self.newlines = 0

	def read(self, b=b'\n'):
		while b:
			(b, ptr) = (os.read(0, (1 << 13) + os.fstat(0).st_size), self.stream.tell())
			(self.stream.seek(0, 2), self.stream.write(b), self.stream.seek(ptr))
		return self.stream.read() if self.stream.tell() else self.stream.getvalue()

	def readline(self, b=b'\n'):
		while b and self.newlines == 0:
			(b, ptr) = (os.read(0, (1 << 13) + os.fstat(0).st_size), self.stream.tell())
			(self.stream.seek(0, 2), self.stream.write(b), self.stream.seek(ptr))
			self.newlines += b.count(b'\n')
		self.newlines -= bool(b)
		return self.stream.readline()

	def readnumber(self, var=int):
		(b, num, sign) = (self.read(), var(0), 1)
		for char in b:
			if char >= b'0'[0]:
				num = 10 * num + char - 48
			elif char == b'-'[0]:
				sign = -1
			elif char != b'\r'[0]:
				yield (sign * num)
				(num, sign) = (var(0), 1)
		if b and b[-1] >= b'0'[0]:
			yield (sign * num)

class FastO:

	def __init__(self):
		stream = BytesIO()
		self.flush = lambda : os.write(1, stream.getvalue()) and (not stream.truncate(0)) and stream.seek(0)
		self.write = lambda s: stream.write(s.encode())
(sys.stdin, sys.stdout) = (FastI(), FastO())
(input, flush) = (sys.stdin.readline, sys.stdout.flush)

def main():
	inp = sys.stdin.readnumber()
	(n, m) = (next(inp), next(inp))
	c = [0] * n
	a = [[next(inp), next(inp), i] for i in range(n)]
	for _ in range(m):
		(x, y) = (next(inp), next(inp))
		s = min(a[x - 1][0] + a[y - 1][1], a[x - 1][1] + a[y - 1][0])
		c[x - 1] -= s
		c[y - 1] -= s
	a.sort(key=lambda x: x[1] - x[0])
	sum_x = sum((i[0] for i in a))
	sum_y = 0
	for i in range(n):
		sum_x -= a[i][0]
		c[a[i][2]] += sum_x + (n - i - 1) * a[i][1] + sum_y + i * a[i][0]
		sum_y += a[i][1]
	print(*c)
main()


import sys
(n, m) = [int(x) for x in sys.stdin.buffer.readline().split()]
s = sys.stdin.buffer.read()
inp = []
sign = 1
numb = 0
for i in range(len(s)):
	if s[i] >= 48:
		numb = 10 * numb + s[i] - 48
	elif s[i] == 45:
		sign = -1
	elif s[i] != 13:
		inp.append(sign * numb)
		numb = 0
		sign = 1
if s[-1] >= 48:
	inp.append(sign * numb)
order = sorted(range(n), key=lambda i: inp[2 * i] - inp[2 * i + 1])
score = [0] * n
val = sum(inp[1:2 * n:2])
for ind in range(n):
	i = order[ind]
	score[i] += val + inp[2 * i + 1] * (ind - 1) + inp[2 * i] * (n - ind - 1)
	val += inp[2 * i] - inp[2 * i + 1]
for _ in range(m):
	u = inp[2 * n + 2 * _] - 1
	v = inp[2 * n + 2 * _ + 1] - 1
	s = min(inp[2 * u] + inp[2 * v + 1], inp[2 * v] + inp[2 * u + 1])
	score[u] -= s
	score[v] -= s

def bstr(x):
	return bytes(str(x), 'ascii')
sys.stdout.buffer.write(b' '.join((bstr(x) for x in score)))


import sys, io, os
s = os.read(0, os.fstat(0).st_size)
inp = []
sign = 1
numb = 0
for i in range(len(s)):
	if s[i] >= 48:
		numb = 10 * numb + s[i] - 48
	elif s[i] == 45:
		sign = -1
	elif s[i] != 13:
		inp.append(sign * numb)
		numb = 0
		sign = 1
if s[-1] >= 48:
	inp.append(sign * numb)
n = inp[0]
m = inp[1]
order = sorted(range(n), key=lambda i: inp[2 * i + 2] - inp[2 * i + 3])
score = [0] * n
val = sum(inp[3:2 * n + 2:2])
for ind in range(n):
	i = order[ind]
	score[i] += val + inp[2 * i + 3] * (ind - 1) + inp[2 * i + 2] * (n - ind - 1)
	val += inp[2 * i + 2] - inp[2 * i + 3]
for _ in range(m):
	u = inp[2 * n + 2 * _ + 2] - 1
	v = inp[2 * n + 2 * _ + 3] - 1
	s = min(inp[2 * u + 2] + inp[2 * v + 3], inp[2 * v + 2] + inp[2 * u + 3])
	score[u] -= s
	score[v] -= s
out = io.BytesIO()
for x in score:
	out.write(str(x).encode())
	out.write(b' ')
os.write(1, out.getvalue())


import os
import sys
from io import BytesIO, IOBase
(sys.stdout, stream) = (IOBase(), BytesIO())
sys.stdout.flush = lambda : os.write(1, stream.getvalue()) and (not stream.truncate(0)) and stream.seek(0)
sys.stdout.write = lambda s: stream.write(s.encode())
getchar = iter(os.read(0, os.fstat(0).st_size)).__next__

def getnum():
	(num, sign) = (0, True)
	char = getchar()
	while char in [10, 13, 32]:
		char = getchar()
	if char == 45:
		(sign, char) = (False, getchar())
	while 48 <= char <= 57:
		num = 10 * num + char - 48
		try:
			char = getchar()
		except:
			break
	return num if sign else -num

def main():
	(n, m) = (getnum(), getnum())
	c = [0] * n
	a = [[getnum(), getnum(), i] for i in range(n)]
	for _ in range(m):
		(x, y) = (getnum(), getnum())
		s = min(a[x - 1][0] + a[y - 1][1], a[x - 1][1] + a[y - 1][0])
		c[x - 1] -= s
		c[y - 1] -= s
	a.sort(key=lambda x: x[1] - x[0])
	sum_x = sum((i[0] for i in a))
	sum_y = 0
	for i in range(n):
		sum_x -= a[i][0]
		c[a[i][2]] += sum_x + (n - i - 1) * a[i][1] + sum_y + i * a[i][0]
		sum_y += a[i][1]
	print(*c)
main()


import sys
(n, m) = [int(x) for x in input().split()]
inp = []
s = sys.stdin.read()
i = 0
while True:
	while i < len(s) and s[i] < '-':
		i += 1
	if i == len(s):
		break
	j = i
	while j < len(s) and (not s[j] < '-'):
		j += 1
	inp.append(int(s[i:j]))
	i = j
order = sorted(range(n), key=lambda i: inp[2 * i] - inp[2 * i + 1])
score = [0] * n
val = sum(inp[1:2 * n:2])
for ind in range(n):
	i = order[ind]
	score[i] += val + inp[2 * i + 1] * (ind - 1) + inp[2 * i] * (n - ind - 1)
	val += inp[2 * i] - inp[2 * i + 1]
for _ in range(m):
	u = inp[2 * n + 2 * _] - 1
	v = inp[2 * n + 2 * _ + 1] - 1
	s = min(inp[2 * u] + inp[2 * v + 1], inp[2 * v] + inp[2 * u + 1])
	score[u] -= s
	score[v] -= s
sys.stdout.write(' '.join((str(x) for x in score)))