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

import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,Q=map(int,input().split())
    a=[0]*(N-1)
    b=[0]*(N-1)
    cns=[[] for _ in range(N)]
    for i in range(N-1):
        a[i],b[i]=map(lambda x: int(x)-1,input().split())
        cns[a[i]].append(b[i])
        cns[b[i]].append(a[i])
    l_x=[0]*N
    for i in range(Q):
        p,x=map(int,input().split())
        l_x[p-1]+=x
    c=[0]*N
    c[0]+=l_x[0]
    def saiki(pn,ppn,x):
        for cn in cns[pn]:
            if cn != ppn:
                z=x+l_x[cn]
                c[cn]+=z
                saiki(cn,pn,z)
        return
    saiki(0,0,c[0])
    print(*c)
    

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,Q=map(int,input().split())
    a=[0]*(N-1)
    b=[0]*(N-1)
    cns=[[] for _ in range(N)]
    for i in range(N-1):
        a[i],b[i]=map(lambda x: int(x)-1,input().split())
        cns[a[i]].append(b[i])
        cns[b[i]].append(a[i])
    l_x=[0]*N
    for i in range(Q):
        p,x=map(int,input().split())
        l_x[p-1]+=x
    c=[0]*N
    c[0]+=l_x[0]
    def saiki(pn,ppn,x):
        for cn in cns[pn]:
            if cn != ppn:
                z=x+l_x[cn]
                c[cn]+=z
                saiki(cn,pn,z)
        return
    saiki(0,0,c[0])
    print(*c)
    

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

import numpy as np
from collections import deque
H,W = map(int, input().split())
CH,CW = map(lambda x: int(x) - 1, input().split())
DH,DW = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(H)]
INF = 10 ** 9
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]
h = CH
w = CW
Distance = np.ones((H,W)) * INF
Distance[h,w] = 0
q = deque([])
q.append([h,w])
while q:
  h,w = q.popleft()
  if [h,w] == [DH,DW]:
    break
  for i,j in walk:
    hwalk = h + i
    wwalk = w + j
    if 0 <= hwalk < H and 0 <= wwalk < W and S[hwalk][wwalk] == '.' and Distance[h,w] < Distance[hwalk,wwalk]:
      Distance[hwalk,wwalk] = Distance[h,w]
      q.appendleft([hwalk,wwalk])
  for i,j in warp:
    hwalk = h + i
    wwalk = w + j
    if 0 <= hwalk < H and 0 <= wwalk < W and S[hwalk][wwalk] == '.' and Distance[h,w] + 1 < Distance[hwalk,wwalk]:
      Distance[hwalk,wwalk] = Distance[h,w] + 1
      q.append([hwalk,wwalk])
print(int(Distance[DH,DW]) if Distance[DH,DW] != INF else -1)

### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
CH,CW = map(lambda x: int(x) - 1, input().split())
DH,DW = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(H)]
INF = 10 ** 9
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]
h = CH
w = CW
Distance = [[INF] * W for _ in range(H)]
Distance[h][w] = 0
q = deque(())
q.append((h,w))
while q:
  h,w = q.popleft()
  if [h,w] == [DH,DW]:
    break
  for i,j in walk:
    hwalk = h + i
    wwalk = w + j
    if 0 <= hwalk < H and 0 <= wwalk < W and S[hwalk][wwalk] == '.' and Distance[h][w] < Distance[hwalk][wwalk]:
      Distance[hwalk][wwalk] = Distance[h][w]
      q.appendleft((hwalk,wwalk))
  for i,j in warp:
    hwalk = h + i
    wwalk = w + j
    if 0 <= hwalk < H and 0 <= wwalk < W and S[hwalk][wwalk] == '.' and Distance[h][w] + 1 < Distance[hwalk][wwalk]:
      Distance[hwalk][wwalk] = Distance[h][w] + 1
      q.append((hwalk,wwalk))
print(int(Distance[DH][DW]) if Distance[DH][DW] != INF else -1)
### BUGGY CODE ###

H,W,M=map(int,input().split())
l = [ list(map(int,input().split(" "))) for i in range(M)]
h=[0]*H
w=[0]*W
for i in range(M):
    h[l[i][0]-1]+=1
    w[l[i][1]-1]+=1
maxh=max(h)
maxw=max(w)
hlist=[]
wlist=[]
for i in range(H):
    if h[i]==maxh:
        hlist.append(i)
for i in range(W):
    if w[i]==maxw:
        wlist.append(i)
c=0
for i in hlist:
    for j in wlist:
        flag=0
        for k in range(M):
            if (i+1)==l[k][0] and (j+1)==l[k][1]:
                flag=1
                break
        if flag==0:
            print(maxh+maxw)
            c=1
            break
    if c==1:
        break
if c==0:
    print(maxh+maxw-1)


### FIXED CODE ###

H,W,M=map(int,input().split())
l = [ list(map(int,input().split(" "))) for i in range(M)]
h=[0]*H
w=[0]*W
for i in range(M):
    h[l[i][0]-1]+=1
    w[l[i][1]-1]+=1
maxh=max(h)
maxw=max(w)
hlist=[]
wlist=[]
for i in range(H):
    if h[i]==maxh:
        hlist.append(i)
for i in range(W):
    if w[i]==maxw:
        wlist.append(i)
c=0
for i in range(M):
  if h[l[i][0]-1]==maxh and w[l[i][1]-1]==maxw:
    c+=1
if len(hlist)*len(wlist)==c:
  print(maxh+maxw-1)
else:
  print(maxh+maxw)
### BUGGY CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline

N,M,K = list(map(int,input().split()))
fr = [[] for i in range(N+1)]
bl = [[] for i in range(N+1)] 
      
for _ in range(M):
    a,b = map(int,input().split())
    fr[a].append(b)
    fr[b].append(a)
for _ in range(K):
    c,d = map(int,input().split())
    bl[c].append(d)
    bl[d].append(c)

mbf = []
for i in range(1,N+1):
    q = collections.deque([i])
    fl = [-1 for i in range(N+1)]
    fl[i]=0
    cnt = 0
    while q:
        now = q.popleft()
        for f in fr[now]:
            if fl[f] == -1:
                if fl[now]==0:
                    fl[f] = 1
                else:
                    fl[f] = 'a'
                    cnt +=1
                if f in bl[i]:
                    fl[f] = 'b'
                    cnt -=1
                q.append(f)
    
    mbf.append(cnt)
print(*mbf)
                


### FIXED CODE ###

import sys,collections
input = sys.stdin.readline

def main():
    N,M,K = list(map(int,input().split()))
    fr = [[] for i in range(N+1)]
    bl = [[] for i in range(N+1)]

          
    for _ in range(M):
        a,b = map(int,input().split())
        fr[a].append(b)
        fr[b].append(a)
    for _ in range(K):
        c,d = map(int,input().split())
        bl[c].append(d)
        bl[d].append(c)

    fl = [-1 for i in range(N+1)]
    fl[0] = 0
    fl[1] = 1
    nxt = 1
    dic = {}
    s = set(range(1,N+1))
    while nxt != 0:
        q = collections.deque([nxt])
        
        fl[nxt]=nxt
        cnt = 0
        while q:
            now = q.popleft()
            s.discard(now)
            for f in fr[now]:
                if fl[f] == -1:
                    fl[f] = nxt
                    cnt +=1
                    q.append(f)
        dic[nxt] = cnt
        #try:
            #nxt = fl.index(-1)
        #except:
            #nxt = 0
        if len(s) == 0:
            nxt = 0
        else:
            nxt = s.pop()


    mbf = collections.deque()
    for i in range(1,N+1):
        ff = 0
        for j in bl[i]:
            if fl[j] == fl[i]:
                ff -= 1
        
        ff += dic[fl[i]]-len(fr[i])
        mbf.append(ff)
    print(*mbf)

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

from functools import reduce

from operator import mul

N=int(input())

list=list(map(int,input().split()))
a=reduce(mul,list)

if 10**18>=a:
	print(a)
else:
  	print(-1)

### FIXED CODE ###

def main ():
	N = int(input())
	A = list(map(int,input(). split ()))
	if 0 in A:
		print(0)
		return
	prod = 1
	for a in A:
		prod *= a
		if prod > 1000000000000000000:
			print(-1)
			return
	print(prod)

main ()
### BUGGY CODE ###

N=int(input())
LA=list(map(int,input().split()))
ans=[]

def gcd(m,n):
    while n:
        m,n=n,m%n
    return m

from functools import reduce
def multigcd(item):
    return reduce(gcd, item)

for n in range(N):
    L=LA[:n]+LA[n+1:]
    ans.append(multigcd(L))

print(max(ans))

### FIXED CODE ###

N=int(input())
LA=list(map(int,input().split()))
ans=[]

def gcd(m,n):
    if m==0 or n==0:
        return m+n
    while n:
        m,n=n,m%n
    return m

La=[0]
Lb=[0]

for n in range(N-1):
    La.append(gcd(La[n],LA[n]))
    Lb.append(gcd(Lb[n],LA[-(n+1)]))

for n in range(N):
    ans.append(gcd(La[n],Lb[-(n+1)]))
        
print(max(ans))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
dics = {}
for i in range(len(a)):
    if a[i] in dics:
        dics[a[i]] = dics[a[i]]  + 1
    else:
        dics.update({a[i]:1})
    
#dics min max
dicsmin = min(list(dics.keys()))
dicsmax = max(list(dics.keys()))

counter = []
for i in range(dicsmin,dicsmax + 1):
    xcount = 0
    x = i
    for k in range(len(a)):
        if a[k] == x or a[k] == x-1 or a[k] == x + 1:
            xcount = xcount + 1
    counter.append(xcount)

print(max(counter))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
aa = []
amax = max(a) + 100


for i in range(amax + 1):
    aa.append(0)

for i in range(len(a)):
    aa[a[i]] = aa[a[i]] + 1
    
kouho = 1    
for j in range(len(aa) - 2):
    if kouho < aa[j] + aa[j + 1] + aa[j + 2]:
        kouho = aa[j] + aa[j + 1] + aa[j + 2]

print(kouho)
### BUGGY CODE ###

N=int(input())

S=[]
char_num=[[] for i in range(10)]

for i in range(N):
    S.append(input())

for i in S:
    index=len(i)-1
    if not i in char_num[index]:
        char_num[index].append(i)

words=0
for i in range(len(char_num)):
    for j in char_num[i]:
        words+=1

print(words)

### FIXED CODE ###

N=int(input())

S=set()
for i in range(N):
    S.add(input())

print(len(S))
### BUGGY CODE ###

N = int(input())
buttons = [int(input()) for i in range(N)]

pushed = list()
button = 1
count = 0
while(True):
    button = buttons[button - 1]
    count += 1
    if (button == 2):
        print(count)
        break
    elif(button in pushed):
        print(-1)
        break
    else:
        pushed.append(button)

### FIXED CODE ###

N = int(input())
buttons = [int(input()) for i in range(N)]

button = 1
count = 0
while(True):
    button = buttons[button - 1]
    count += 1
    if (button == 2):
        print(count)
        break
    elif(count > N):
        print(-1)
        break
### BUGGY CODE ###

import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
N = int(input())

A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

dp = [N] * (N+1)
for w in range(N+1):
    for a, b in zip(A, B):
        if w >= a:
            dp[w] = max(dp[w], dp[w-a] + b-a)

M = max(dp)
dp = [M] * (M+1)
for w in range(M+1):
    for a, b in zip(A, B):
        if w >= b:
            dp[w] = max(dp[w], dp[w-b] + a-b)

print(max(dp))


### FIXED CODE ###

import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
N = int(input())

A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

dp = [0] * (N+1)
for a, b in ((a, b) for a, b in zip(A, B) if a < b):
    for w in range(a, N+1):
        dp[w] = max(dp[w], dp[w-a] + b-a)

M = max(dp) + N
dp = [0] * (M+1)
for a, b in ((a, b) for a, b in zip(A, B) if a > b):
    for w in range(b, M+1):
        dp[w] = max(dp[w], dp[w-b] + a-b)

print(max(dp) + M)
### BUGGY CODE ###

from itertools import product

def judge(numlist):
    if numlist[2] + numlist[0] == 2 * numlist[1]:
        return False
    else:
        return True

N = int(input())
S = list(input())
R = []
G = []
B = []

for i in range(N):
    if S[i] == 'R':
        R.append(i)
    elif S[i] == 'G':
        G.append(i)
    else:
        B.append(i)

RG = product(R,G)
RGcombs = []
for i in RG:
    RGcombs.append(sorted(list(i)))

ans = 0
for comb in RGcombs:
    for k in B:
        if k < comb[0]:
            if judge([k]+list(comb)):
                ans += 1
        elif k > comb[1]:
            if judge(list(comb)+[k]):
                ans += 1
        else:
            c = list(comb)
            if judge([c[0],k,c[1]]):
                ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())
r = 0
g = 0
b = 0

for i in range(N):
    if S[i] == 'R':
        r += 1
    elif S[i] == 'G':
        g += 1
    else:
        b += 1

allcnt = r * g * b

sub = 0
for i in range(N):
    for j in range(i+1,N):
        if S[i] == S[j]:
            None
        else:
            k = 2*j-i
            if k >= N or S[i] == S[k] or S[j] == S[k]:
                None
            else:
                sub += 1

print(allcnt - sub)
### BUGGY CODE ###

import sys
 
def main():
    N = int(input())
 
    Ss = []
    for x in range(N):
        Ss.append(sorted(input()))
 
    ans = 0
    for i in range(0, N-1):
        for j in range(i+1, N):
            if Ss[i] == Ss[j]:
                ans += 1
 
    print(ans)
 
main()

### FIXED CODE ###

import sys
from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

def main():
    N = int(input())

    Ss = {}
    for x in range(N):
        tmp = ''.join(sorted(input()))

        if tmp in Ss:
            Ss[tmp] += 1

        else:
            Ss[tmp] = 1


    ans = 0
    for i in Ss.values():
        if i != 1:
            ans += combinations_count(i, 2)

    print(ans)

main()
### BUGGY CODE ###

#!/usr/bin/env python3
#coding:utf-8

n = int(input())
data = []
for i in range(n):
    data.append(int(input()))

maxdata = data[1] - data[0]

for i,n in enumerate(data):
    if len(data[i:]) == 1 :
        break

    nowdata = max(data[i+1:])-n
    if maxdata < nowdata:
        maxdata = nowdata

print(maxdata)


### FIXED CODE ###

#!/usr/bin/env python3
#coding:utf-8

n = int(input())
ans = -10000000000
mini = 10000000000

for i in range(n):
    x = int(input())
    ans = ans if (x-mini) < ans else x-mini
    mini = mini if x > mini else x

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

N, Q = map(int, input().split())

l = [set() for i in range(N)]

for i in range(N-1):
  a, b = map(int, input().split())
  l[a-1].add(b-1)
  l[b-1].add(a-1)

par = [-1] * N
par[0] = 0

children = [[] for i in range(N)]

stack = [0]
while stack:
  prev = stack.pop()
  for to in l[prev]:
    if par[to] < 0:
      par[to] = prev
      children[prev].append(to)
      stack.append(to)

counter = [0] * N

for i in range(Q):
  p, x = map(int, input().split())
  counter[p-1] += x

r = [-1] * N
r[0] = counter[0]

stack = [0]
while stack:
  i = stack.pop()
  stack += children[i]
  s = 0
  cur = i
  while r[cur] < 0:
    s += counter[cur]
    cur = par[cur]
  r[i] = r[cur] + s

print(*r)

### FIXED CODE ###

N, Q = map(int, input().split())

l = [[] for i in range(N)]

for i in range(N-1):
  a, b = map(int, input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)

used = [False] * N
r = [0] * N

for i in range(Q):
  p, x = map(int, input().split())
  r[p-1] += x

stack = [0]
while stack:
  i = stack.pop()
  used[i] = True
  for to in l[i]:
    if not used[to]:
      stack.append(to)
      r[to] += r[i]

print(*r)
### BUGGY CODE ###

K,S=map(int,input().split())
count=0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i+j+k==S:
                count+=1
print(count)

### FIXED CODE ###

K,S=map(int,input().split())
count=0
for i in range(K+1):
    for j in range(K+1):
        if K>=S-i-j>=0:
            count+=1
print(count)
### BUGGY CODE ###

import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

n,x = li()
a = li()

a = a+a

INF = float("inf")

# 区間内最小を探す
itv_min = [[INF for _ in range(2*n)] for _ in range(n)]
for st in range(n):
    mn = a[st]
    itv_min[st][st] = mn
    for ed in range(st+1,st+n):
        mn = min(mn, a[ed])
        itv_min[st][ed] = mn

# 魔法を唱える回数を固定
ans = INF
for k in range(n):
    temp = 0
    for st in range(n):
        temp += itv_min[st][st+k]
        
    ans = min(ans, temp+k*x)

print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

n,x = li()
a = li()

mins = [ai for ai in a]
a2 = a+a

ans = sum(mins)
for k in range(n):
    for i in range(n):
        mins[i] = min(mins[i],a2[i+k])
    
    temp = sum(mins)    
    ans = min(ans, temp + k*x)
    
print(ans)
### BUGGY CODE ###

N, A, B = map(int, input().split())
ball = []
kaisu = -(-N//(A+B))
for n in range(kaisu):
    for i in range(A):
        ball += [0]
        if len(ball)==N:
            break
    for j in range(B):
        ball += [1]
        if len(ball)==N:
            break
print(ball.count(0))

### FIXED CODE ###

N, A, B = map(int, input().split())
kaisu = N//(A+B)

n = N-((A+B)*kaisu)
if n >= A:
    print(A*(kaisu+1))
else:
    print(A*kaisu+n)
### BUGGY CODE ###

c=0
N=int(input())
A=list(map(int,input().split()))
for i in range(N):
  for j in range(i+1,N):
    if sum(A[i:j+1])==0:
      c=c+1
for i in range(N):
  if A[i]==0:
    c=c+1
print(c)

### FIXED CODE ###

N=int(input())
L=list(map(int,input().split()))
R={}
sums=0
for i in range(N):
  sums+=L[i]
  if sums in R:
    R[sums]+=1
  else:
    R[sums]=1
k=0
if 0 in R:
  k=R[0]
print(sum([i*(i-1)//2 for i in R.values()])+k)
### BUGGY CODE ###

import heapq
def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    BC = [list(map(int, input().split())) for i in range(M)]

    A.sort()
    BC.sort(key=lambda x: x[1], reverse=True)
    BC2 = []

    for bc in BC:
        for i in range(bc[0]):
            BC2.append(bc[1])
    
    BC_idx = 0
    for i in range(N):
        if BC_idx >= len(BC2):
            break
        if A[i] < BC2[BC_idx]:
            A[i] = BC2[BC_idx]
            BC_idx += 1

    print(sum(A))

if __name__ == '__main__':
    solve()


### FIXED CODE ###

def solve():
    N, M = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    operate = []
    for _ in range(M):
        b, c = map(int,input().split())
        operate.append([b,c])
    operate.sort(reverse=True, key=lambda x:x[1])    

    rewrite = [0] * N
    idx = 0
    for b,c in operate:
        for i in range(b):
            rewrite[idx] = c
            idx += 1
            if idx == N:
                break
        if idx == N:
            break
    
    ans = 0
    for i in range(N):
        ans += max(A[i],rewrite[i])
    
    print(ans)

if __name__ == '__main__':
    solve()
### BUGGY CODE ###

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

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

for i in range(n):
    ans = 0
    checked = [False]*n
    checked[i] = True
    def search(node):
        global ans, checked
        if node != i and node not in f[i] and node not in b[i]:
            ans += 1
        for _node in f[node]:
            if not checked[_node]:
                checked[_node] = True
                search(_node)
        return
    search(i)
    print(ans, end=" " if i != n-1 else "\n")

### FIXED CODE ###

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

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#初期化
#根なら-size,子なら親の頂点

n, m, k = map(int, input().split())
par = [-1]*n
f = [set() for _ in range(n)]
b = [set() for _ in range(n)]
for _ in range(m):
    a, _b = map(int, input().split())
    f[a-1].add(_b-1)
    f[_b-1].add(a-1)
    unite(a-1, _b-1)
for _ in range(k):
    a, _b = map(int, input().split())
    b[a-1].add(_b-1)
    b[_b-1].add(a-1)

for i in range(n):
    ans = size(i)-len(f[i])-1
    for node in b[i]-f[i]:
        if same(i, node):
            ans -= 1
    print(ans, end=" " if i!=n-1 else "\n")
### BUGGY CODE ###

from operator import itemgetter

n,q = map(int, input().split())

a = [0]*(n-1)
b = [0]*(n-1)
for i in range(n-1):
    a[i],b[i] = map(int, input().split())

p = [0]*q
x = [0]*q

for i in range(q):
    p[i],x[i] = map(int, input().split())


score = [0]*n

def down_tree(parent, add_score):
    global score
    for i in range(q):
        if p[i]-1 == parent:
            add_score += x[i]
    for i in range(n-1):
        if a[i]-1 == parent:
            down_tree(b[i]-1, add_score)

    score[parent] += add_score

    return 0

down_tree(0, 0)

print(*score)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(200005)
n, q = map(int, input().split())

to = [[] for i in range(n+1)]


for i in range(n-1):
    a, b = map(int, input().split())
    to[a].append(b)
    to[b].append(a)

score = [0]*(n+1)
for i in range(q):
    p, x = map(int, input().split())
    score[p] += x


def down_tree(index, parent):
    for i in to[index]:
        if i == parent:
            continue
        score[i] += score[index]
        down_tree(i, index)



down_tree(1, 1)

print(' '.join(map(str, score[1:])))
### BUGGY CODE ###

import sys
import math
mod = 1000000007

n = int(sys.stdin.readline().rstrip())
ab = {}
for i in range(n):
    a,b = map(int,sys.stdin.readline().rstrip().split())
    if a == 0 and b == 0:
        pass
    elif a == 0:
        b = 1
    else:
        gcd = math.gcd(a,b)
        a //= gcd
        b //= gcd
        if a < 0:
            a = -a
            b = -b
    ab.setdefault((a,b),0)
    ab[(a,b)]+=1
ans = 0
pairs=[]
s = list(set(ab.keys()))
for i in ab.keys():
    a = i[0];b = i[1]
    if a == 0 and b == 0:
        ans = ab[(0,0)]
        n -= ans
    else:
        if (-b, a) in s:
            pairs.append([ab[(a,b)],ab[(-b,a)]])
select = 1
for pair in pairs:
    select*= (pow(2,pair[0],mod) + pow(2,pair[1],mod) -1)
    n -= (pair[0]+pair[1])
all_ans = (pow(2,n,mod) * select) % mod + ans -1
all_ans %= mod
print(all_ans)

### FIXED CODE ###

import math
 
n = int(input())
mod = 10 ** 9 + 7
 
ab = {}
for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        pass
    elif a == 0:
        b = 1
    else:
        gcd = math.gcd(a, b)
        a //= gcd
        b //= gcd
        if a < 0:
            a, b = -a, -b
    num = (a, b)
    ab.setdefault(num, 0)
    ab[num] += 1
ans = 0
if (0, 0) in ab.keys():
    temp2 = ab[(0, 0)]
    ans += temp2
    n -= temp2
s = set(ab.keys())
pairs = []
for i in ab.keys():
    if i == (0, 0):
        continue
    else:
        a, b = i[0], i[1]
        if (-b, a) in s:
            pairs.append([ab[(a, b)], ab[(-b, a)]])
temp3 = 1
for i in range(len(pairs)):
    num2 = pairs[i][0]
    num3 = pairs[i][1]
    temp3 *= (pow(2, num2, mod) + pow(2, num3, mod) - 1)
    n = n- num2 - num3
    temp3 %= mod
temp3 *= pow(2, n, mod)
temp3 -= 1
temp3 %= mod
ans += temp3
ans %= mod
print(ans)