Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
N = [[0, 1], [0, -1], [1, 0], [-1, 0]]
P = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2], [0, -2], [-1, 2], [-1, 1],
     [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for NY, NX in N:
        if 0 <= x + NX < w and 0 <= y + NY < h and S[y + NY][x + NX] != '#':
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count:
                grid[y + NY][x + NX] = count
                que.appendleft((count, y + NY, x + NX))
    for NY, NX in P:
        if 0 <= x + NX < w and 0 <= y + NY < h and S[y + NY][x + NX] != '#':
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count + 1:
                grid[y + NY][x + NX] = count + 1
            que.append((count + 1, y + NY, x + NX))

print(grid[dh][dw])


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [list(input()) for _ in range(h)]

Ch, Cw = Ch - 1, Cw - 1
Dh, Dw = Dh - 1, Dw - 1
d = [[-1] * w for _ in range(h)]
d[Ch][Cw] = 0
walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
warp = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2], [0, -2], [-1, 2], [-1, 1],
        [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]]

que = deque([[0, Ch, Cw]])
while que:
    count, y, x = que.popleft()
    if d[y][x] < count:
        continue
    for NY, NX in walk:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count:
                d[y + NY][x + NX] = count
                que.appendleft([count, y + NY, x + NX])
    for NY, NX in warp:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count + 1:
                d[y + NY][x + NX] = count + 1
                que.append([count + 1, y + NY, x + NX])

print(d[Dh][Dw])
### BUGGY CODE ###

# @author 

import sys

class EVirusTree2:

    def solve(self):
        from collections import defaultdict
        import sys
        sys.setrecursionlimit(10 ** 5 + 5)

        MOD = 10 ** 9 + 7
        n, k  = [int(_) for _ in input().split()]
        adj = defaultdict(list)
        for i in range(n - 1):
            a, b = [int(_) for _ in input().split()]
            a -= 1
            b -= 1
            adj[a].append(b)
            adj[b].append(a)
        done = [0] * n
        def dfs(s, rem):
            done[s] = 1
            if rem < 0:
                return 0
            res = 1
            for x in adj[s]:
                if done[x]:
                    continue
                if rem <= 0:
                    return 0
                res = (res * rem) % MOD
                res = (res * dfs(x, k - 2)) % MOD
                rem -= 1
                if res == 0:
                    return 0
            return res

        print (dfs(0, k - 1) * k) % MOD




solver = EVirusTree2()
input = sys.stdin.readline

solver.solve()


### FIXED CODE ###

# @author 

import sys

class EVirusTree2:

    def solve(self):
        from collections import defaultdict
        import sys
        sys.setrecursionlimit(10 ** 5 + 5)

        MOD = 10 ** 9 + 7
        n, k  = [int(_) for _ in input().split()]
        adj = defaultdict(list)
        for i in range(n - 1):
            a, b = [int(_) for _ in input().split()]
            a -= 1
            b -= 1
            adj[a].append(b)
            adj[b].append(a)
        done = [0] * n
        def dfs(s, rem):
            done[s] = 1
            if rem < 0:
                return 0
            res = 1
            for x in adj[s]:
                if done[x]:
                    continue
                if rem <= 0:
                    return 0
                res = (res * rem) % MOD
                res = (res * dfs(x, k - 2)) % MOD
                rem -= 1
                if res == 0:
                    return 0
            return res

        print((dfs(0, k - 1) * k) % MOD)




solver = EVirusTree2()
input = sys.stdin.readline

solver.solve()
### BUGGY CODE ###

import sys
INFTY=sys.maxsize

def readinput():
    n,k=list(map(int,input().split()))
    h=list(map(int,input().split()))
    return n,k,h

def main(n,k,h):
    dp=[INFTY]*n
    dp[0]=0
    for i in range(n):
        for j in range(1,k+1):
            if i+j<n:
                dp[i+j]=min(dp[i+j],dp[i]+abs(h[i]-h[i+j]))
    return dp[n-1]

if __name__=='__main__':
    n,k,h=readinput()
    ans=main(n,k,h)
    print(ans)


### FIXED CODE ###

import sys
INFTY=sys.maxsize

def readinput():
    n,k=list(map(int,input().split()))
    h=list(map(int,input().split()))
    return n,k,h

def main(n,k,h):
    dp=[INFTY]*n
    dp[0]=0
    for i in range(n):
        for j in range(1,k+1):
            if i+j<n:
                dp[i+j]=min(dp[i+j],dp[i]+abs(h[i]-h[i+j]))
    return dp[n-1]

if __name__=='__main__':
    n,k,h=readinput()
    ans=main(n,k,h)
    print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
numgcd = [0]*(K+1)
sumgcd = 0
mod = 10**9+7
for i in range(1, K+1)[::-1]:
    r = K//i
    num = r**N
    count = 2
    while count*i <= K:
        num -= numgcd[count*i]
        count += 1
    numgcd[i] = num
    sumgcd += num*i%mod
print(sumgcd%mod)

### FIXED CODE ###

N, K = map(int, input().split())
numgcd = [0]*(K+1)
sumgcd = 0
mod = 10**9+7
for i in range(1, K+1)[::-1]:
    numgcd[i] = pow(K//i, N, mod)
    count = 2
    while count*i <= K:
        numgcd[i] -= numgcd[count*i]
        count += 1
    sumgcd += numgcd[i]*i
print(sumgcd%mod)
### BUGGY CODE ###

#127_C
n, m = map(int, input().split())
s = set(range(1,n+1))

for _ in range(m):
    l, r = map(int, input().split())
    s &= set(range(l, r+1))

print(len(s))

### FIXED CODE ###

#127_C
n, m = map(int, input().split())
L = []
R = []
for _ in range(m):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
print(max(0, min(R)-max(L)+1))
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    A_dict = {}
    for a in A:
        if a in A_dict.keys():
            A_dict[a] += 1
        else:
            A_dict[a] = 1

    A_remain = sorted(A_dict.keys())
    limit = A_remain[-1] / 2
    prime = []
    a = A_remain[0]

    while a<= limit and len(A_remain)>0:
        a = A_remain[0]
        prime.append(a)
        A_remain = [i for i in A_remain[1:] if i%a!=0]

    prime.extend(A_remain)
    print(sum([1 for i in prime if A_dict[i]==1]))

main()

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))

    A_dict = {}
    for a in A:
        if a in A_dict.keys():
            A_dict[a] += 1
        else:
            A_dict[a] = 1

    A_list = sorted(A_dict.keys())
    limit = A_list[-1]

    sieve = {i: True for i in A_dict.keys()}

    for a in A_list:
        if not sieve[a]:
            continue
        for i in range(2*a, limit+1, a):
            if i in sieve:
                sieve[i] = False

    print(sum([1 for i in sieve.keys() if sieve[i] and (A_dict[i]==1)]))
main()
### BUGGY CODE ###

n,x=map(int,input().split())
l=list(map(int,input().split()))

def make_divisor_list(num):
    if num < 1:
        return []
    elif num == 1:
        return [1]
    else:
        divisor_list = []
        divisor_list.append(1)
        for i in range(2, num // 2 + 1):
            if num % i == 0:
                divisor_list.append(i)
        divisor_list.append(num)

        return divisor_list

if n==1:
    print(abs(x-l[0]))
else:
    l.append(x)
    minimum=min(l)
    maximum=max(l)
    delta=maximum-minimum
    if delta==1:
        print(1)
    else:
        kouho=make_divisor_list(delta)
        ans=1
        for num in kouho:
            signal=1
            for j in range(n):
                if (l[j]-minimum)%num!=0:
                    signal=0
            if signal==1:
                ans=num
        print(ans)

### FIXED CODE ###

n,x=map(int,input().split())
l=list(map(int,input().split()))

def gcd(a, b):
  while b > 0:
    a, b = b, a%b
  return a

kouho=[abs(l[i]-x) for i in range(n)]

ans=kouho[0]

for i in range(n-1):
  ans = gcd(ans,kouho[i+1])
  
print(ans)
### BUGGY CODE ###

import sys
N, M = map(int, sys.stdin.readline().split())
a = [int(sys.stdin.readline()) for _ in range(M)]

MOD = 10 ** 9 + 7

list = [0] * N

for i in range(N):
    if i == 0:
        if (i + 1) in a:
            list[i] = 0
        else:
            list[i] = 1
    elif i == 1:
        if (i + 1) in a:
            list[i] = 0
        elif i in a:
            list[i] = 1
        else:
            list[i] = 2
    else:
        if (i + 1) in a:
            list[i] = 0
        else:
            list[i] = (list[i - 1] + list[i - 2]) % MOD
            
ans = list[N - 1]
print(ans)

### FIXED CODE ###

import sys
N, M = map(int, sys.stdin.readline().split())
a = [int(sys.stdin.readline()) for _ in range(M)]

MOD = 10 ** 9 + 7

list = [0] * N

if M > 0:
    j = 0
    for i in range(N):
        if i == 0:
            if a[j] == 1:
                list[i] = 0
            else:
                list[i] = 1
        elif i == 1:
            if a[j] == 2:
                list[i] = 0
            elif a[0] == 1:
                list[i] = 1
            else:
                list[i] = 2
        else:
            if a[j] == i + 1:
                list[i] = 0
            else:
                list[i] = (list[i - 1] + list[i - 2]) % MOD
        if i + 1 == a[j] and j < M - 1:
            j += 1

else:
    for i in range(N):
        if i == 0:
            list[i] = 1
        elif i == 1:
            list[i] = 2
        else:
            list[i] = (list[i - 1] + list[i - 2]) % MOD
            
ans = list[N - 1]
print(ans)
### BUGGY CODE ###

N = int(input())
S = []
count = 0
for i in range(N):
    S.append(sorted(input()))
for j in range(N-1):
    for k in range(j+1,N):
        if S[j] == S[k]:
            count += 1
print(count)

### FIXED CODE ###

N = int(input())
S = []
count = 0
for i in range(N):
    S.append(sorted(input()))
S = sorted(S)
a = 'sing'
for j in range(N):
    if a != S[j]:
        f = 0
        a = S[j]
    else:
        f += 1
        count += f
print(count)
### BUGGY CODE ###

import bisect
n, k = map(int, input().split())
a = list(map(int, input().split()))

pl = []
mi = []
ze = 0

for x in a:
    if x > 0:
        pl.append(x)
    elif x < 0:
        mi.append(x)
    else:
        ze += 1

p, m = len(pl), len(mi)
res1 = p * m
res2 = (p + m) * ze + ze * (ze - 1) // 2
if res1 >= k:
    pl.sort()
    l, r = 0, 10 ** 20
    while r - l > 1:
        x = (l + r) // 2
        tmp = 0
        for mm in mi:
            mm = abs(mm)
            y = -(-x // mm)
            tmp += p - bisect.bisect_left(pl, y)

        if tmp < k:
            r = x
        else:
            l = x
    print(-l)

elif res1 + res2 >= k:
    print(0)
else:
    k = k - res1 - res2
    pl.sort()
    mi = [abs(mi[i]) for i in range(m)]
    mi.sort()
    l, r = 0, 10 ** 20
    while r - l > 1:
        x = (l + r) // 2
        tmp = 0
        for i in range(p):
            y = x // pl[i]
            tmp += max(0, bisect.bisect_right(pl, y) - i - 1)
        for i in range(m):
            y = x // mi[i]
            tmp += max(0, bisect.bisect_right(mi, y) - i - 1)

        if tmp < k:
            l = x
        else:
            r = x
    print(r)

### FIXED CODE ###

import bisect, sys
input = sys.stdin.readline
n, k = map(int, input().split())
a = list(map(int, input().split()))

pl = []
mi = []
ze = 0

for x in a:
    if x > 0:
        pl.append(x)
    elif x < 0:
        mi.append(-x)
    else:
        ze += 1

p, m = len(pl), len(mi)
res1 = p * m
res2 = (p + m) * ze + ze * (ze - 1) // 2

#K番目が負
if res1 >= k:
    pl.sort(reverse=True)
    mi.sort()
    l, r = 0, 10 ** 20
    while r - l > 1:
        x = (l + r) // 2
        cnt = p * m
        tmp = 0
        for i in range(p):
            while tmp < m and pl[i] * mi[tmp] < x:
                tmp += 1
            cnt -= tmp
        if cnt < k:
            r = x
        else:
            l = x
    print(-l)

#K番目が0
elif res1 + res2 >= k:
    print(0)

#K番目が正
else:
    k = k - res1 - res2
    pl.sort(reverse=True)
    pl2 = pl[::-1]
    mi.sort(reverse=True)
    mi2 = mi[::-1]
    l, r = 0, 10 ** 20
    while r - l > 1:
        x = (l + r) // 2
        cnt = 0
        tmp = 0
        for i in range(p):
            if pl[i] ** 2 <= x:
                cnt -= 1
            while tmp < p and pl[i] * pl2[tmp] <= x:
                tmp += 1
            cnt += tmp
        tmp = 0
        for i in range(m):
            if mi[i] ** 2 <= x:
                cnt -= 1
            while tmp < m and mi[i] * mi2[tmp] <= x:
                tmp += 1
            cnt += tmp

        cnt //= 2
        if cnt < k:
            l = x
        else:
            r = x
    print(r)
### BUGGY CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N, W = map(int, input().split())
    w = [0]
    v = [0]
    for i in range(N):
        weight, value = map(int, input().split())
        w.append(weight)
        v.append(value)

    dp = [[0] * (W + 1) for _ in range(N + 1)]


    for i in range(1, N + 1):
        for j in range(1, W + 1):
            if j - w[i] < 0:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
    # print(w, v, dp)
    print(dp[N][W])


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N, W = map(int, input().split())
    w = [0]
    v = [0]
    for i in range(N):
        weight, value = map(int, input().split())
        w.append(weight)
        v.append(value)

    dp = [[0] * (W + 1) for _ in range(N + 1)]


    for i in range(1, N + 1):
        for j in range(1, W + 1):
            if j - w[i] < 0:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
    # print(w, v, dp)
    print(dp[N][W])


if __name__ == "__main__":
    main()
### BUGGY CODE ###

A, B = map(int, input().split())
ans = 0
for i in range(40):
    # 含まれる1の数を数える
    tmp = (B-A) // 2**(i+1) * 2**i
    p = A%(2**(i+1))
    q = (B-A)%(2**(i+1))
    for j in range(p, p + q + 1):
        if j % (2**(i+1)) >= 2**i:
            tmp += 1
    ans += (tmp%2) * 2**i
print(ans)

### FIXED CODE ###

A, B = map(int, input().split())
ans = 0
for i in range(40):
    # 含まれる1の数を数える
    tmp = (B-A) // 2**(i+1) * 2**i
    p = A%(2**(i+1))
    q = (B-A)%(2**(i+1))
    # p から p+qの中で余りが2**i ~ 2**(i+1)-1になる個数を求める
    tmp += max(min(p+q,2**(i+1)-1) - max(p,2**i)+1,0)
    tmp += max(min(p+q,2**(i+1)-1 + 2**(i+1)) - max(p,2**i + 2**(i+1))+1,0)
    ans += (tmp%2) * 2**i
print(ans)
### BUGGY CODE ###

S=input()[::-1]
B='BW';A='WB'
a=0
L=len(S)
i=0
while i<=L-2:
  if S[i:i+2]==A:
    S=S[0:i]+B+S[i+2:]
    a+=1
    i=0
  i+=1
print(a)

### FIXED CODE ###

S=input()[::-1]
ans,tmp=0,0
for i in S:
  if i=='W':
    tmp+=1
  else:
    ans+=tmp
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split(' ')]

A.sort(reverse=True)
ring = []
max_value = A.pop(0)
ring.append(max_value)
ring.append(max_value)
ans = 0
for i in A:
    n = []
    for j in range(0, len(ring) - 1):
        check = min(ring[j:j + 2])
        n.append(check)
        if check == max(ring):
            break
    ans = ans + max(n)
    ring.insert(n.index(max(n)) + 1, i)

print(ans)

### FIXED CODE ###

import sys
from collections import deque

N = int(sys.stdin.readline())
A = [int(i) for i in sys.stdin.readline().split(' ')]

A.sort(reverse=True)
max_value = A.pop(0)
diff = deque([max_value])
ans = 0
for i in A:
    ans = ans + diff.popleft()
    diff.append(i)
    diff.append(i)

print(ans)
### BUGGY CODE ###

n = int(input())
nums = list(map(int, input().split()))
ans = 1
for i in nums:
    ans*= i
    if(ans > int(1e18) and 0 not in nums):
        break
if(ans > int(1e18)):
    print(-1)
else:
    print(ans)


### FIXED CODE ###

n = int(input())
nums = list(map(int, input().split()))
ans = 1
ok = True
if(0 in nums):
    print(0)
else:
    for i in nums:
        ans *= i
        if(ans > int(1e18)):
            ok = False
            break
    if(not ok):
        print(-1)
    else:
        print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))

fromLeft = [-1]*n

for i in range(n):
    fromLeft[i] = a[i] - i

ans = 0

for i in range(n):
    ans += fromLeft[i:].count(-1*a[i]-i)

print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))

fromLeft = [-1]*n

for i in range(n):
    fromLeft[i] = a[i] - i

ans = 0

ldList = [0]*(n*2+5)

for i in reversed(range(n)):
    if 0 <= fromLeft[i]+n+1 and fromLeft[i]+n+1 < n*2+5:
        ldList[fromLeft[i]+n+1] += 1
    if 0 <= -1*a[i]-i+n+1 and -1*a[i]-i+n+1 < n*2+5:
        ans += ldList[-1*a[i]-i+n+1]

print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)

def dfs(i):
	if i in use:
		return 
	use.add(i)
	for e in edges_r[i]:
		dfs(e)

def bf():
	d = [float('inf') for _ in range(n + 1)]
	d[1] = 0
	for _ in range(n):
		f = False
		for e in edges_f:
			if d[e[1]] > d[e[0]] + e[2]:
				d[e[1]] = d[e[0]] + e[2]
				f = True	
		if not f:
			return max(0, -1 * d[n])
	return -1

n, m, p = list(map(int, input().split()))

edges_f = []
edges_r = [[] for i in range(n + 1)]
for _ in range(m):
	a, b, c = list(map(int, input().split()))
	edges_f.append([a, b, -1 * (c - p)])
	edges_r[b].append(a)

use = set()
dfs(n)

edges_f = [e for e in edges_f if e[0] in use and e[1] in use]
print(bf())

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)

def dfs(i):
	if i in use:
		return 
	use.add(i)
	for e in edges_r[i]:
		dfs(e)

def bf():
	d = [float('inf') for _ in range(n + 1)]
	d[1] = 0
	for _ in range(n):
		f = False
		for e in edges_f:
			if d[e[1]] > d[e[0]] + e[2]:
				d[e[1]] = d[e[0]] + e[2]
				f = True	
		if not f:
			return max(0, -1 * d[n])
	return -1

n, m, p = list(map(int, input().split()))

edges_f = []
edges_r = [[] for i in range(n + 1)]
for _ in range(m):
	a, b, c = list(map(int, input().split()))
	edges_f.append([a, b, -1 * (c - p)])
	edges_r[b].append(a)

use = set()
dfs(n)

edges_f = [e for e in edges_f if e[0] in use and e[1] in use]
print(bf())
### BUGGY CODE ###

from sys import stdin
import sys
sys.setrecursionlimit(10**7)


class DFS():
    def __init__(self,N,S):
        self.N = N
        self.S = S
        self.seen = [False] * self.N
        self.cnt = [0] * self.N

    def dfs(self, i):
        if i == self.N-1:
            return 1
        elif i > self.N-1:
            return 0
        elif self.seen[i]:
            return self.cnt[i]
        else:
            cnt = 0
            for s in self.S:
                cnt += self.dfs(i+s)
            else:
                self.cnt[i] = cnt % 998244353
                self.seen[i] = True
            return self.cnt[i]


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, K = list(map(int, _in[0].split(' ')))  # type:list(int)
    L_R_arr = []
    for i in range(K):
        _ = list(map(int, _in[i+1].split(' ')))  # type:list(int)
        L_R_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    ans = 0
    S = []
    for L, R in L_R_arr:
        S.extend([i for i in range(L, R+1)])
    S = sorted(set(S))

    dfs = DFS(N, S)
    dfs.dfs(0)
    ans = dfs.cnt[0] % 998244353
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from sys import stdin
import sys
sys.setrecursionlimit(10**7)


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, K = list(map(int, _in[0].split(' ')))  # type:list(int)
    L_R_arr = []
    for i in range(K):
        _ = list(map(int, _in[i+1].split(' ')))  # type:list(int)
        L_R_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    dp = [0] * N
    sdp = [0] * (N+1)
    dp[0] = 1
    for i in range(N):
        for L, R in L_R_arr:
            right = max(0, i-L+1)
            left  = max(0, i-R)
            dp[i] += sdp[right] - sdp[left]
        else:
            sdp[i+1] = (sdp[i] + dp[i]) % 998244353
    ans = dp[-1] % 998244353
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())
g = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

q = int(input())
v = []
d = []
c = []
for _ in range(q):
    V, D, C = map(int, input().split())
    v.append(V-1)
    d.append(D)
    c.append(C)
v = v[::-1]
d = d[::-1]
c = c[::-1]

color = [0] * n

def dfs(node, dist, dist_max, col):
    if dist > dist_max:
        return
    if color[node] == 0:
        color[node] = col
    for next_node in g[node]:
        dfs(next_node, dist+1, dist_max, col)

for i in range(q):
    dfs(v[i], 0, d[i], c[i])

for co in color:
    print(co)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())
g = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

q = int(input())

query = [list(map(int, input().split())) for _ in range(q)]

color = [0] * n
depth = [-1] * n

def dfs(node, dist, col, pre_node):
    if dist <= depth[node]:
        return
    depth[node] = dist
    if color[node] == 0:
        color[node] = col
    if dist == 0:
        return
    for next_node in g[node]:
        if next_node == pre_node:
            continue
        dfs(next_node, dist-1, col, node)

for v, d, c in query[::-1]:
    v -= 1
    dfs(v, d, c, -1)

for co in color:
    print(co)
### BUGGY CODE ###

from operator import itemgetter

N = int(input())
A, B = [], []

for i in range(N):
    a, b = map(int, input().split())
    A.append([a, i])
    B.append([b, i])
A.sort(reverse=True, key=itemgetter(1))
B.sort(reverse=True, key=itemgetter(1))

ate = []
apoint, apos = 0, 0
bpoint, bpos = 0, 0
for i in range(N):
    if i % 2 == 0:
        while True:
            if A[apos][1] not in ate:
                apoint += A[apos][0]
                ate.append(A[apos][1])
                break
            apos += 1
    else:
        while True:
            if B[bpos][1] not in ate:
                bpoint += B[bpos][0]
                ate.append(B[bpos][1])
                break
            bpos += 1
print(apoint - bpoint)


### FIXED CODE ###

N = int(input())
A, B = [], []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a + b)
    B.append(b)

A.sort(reverse=True)
print(sum([ab for i, ab in enumerate(A) if i % 2 == 0]) - sum(B))