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

import sys
from collections import deque
input = sys.stdin.readline

class UnionFind():
    def __init__(self, n=0):
        self.d = [-1]*n
        self.g = set()
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:return False
        if self.d[x] > self.d[y]: x,y=y,x
        self.d[x] += self.d[y]
        self.g.add(x)
        if y in self.g:self.g.remove(y)
        self.d[y] = x
        return True

    def same(self,x,y): return self.find(x)==self.find(y)
    def size(self,x): return -self.d[self.find(x)]
    
def comb2(n):
  return n*(n-1)//2
    
N,M=map(int,input().split())
edges=[list(map(int,input().split())) for _ in range(M)]

total=comb2(N)
ans = deque([total])
uf = UnionFind(N+1)
for i in range(M-1):
  if uf.unite(edges[-1-i][0],edges[-1-i][1]):
  	ans.appendleft(total-sum(map(lambda x: comb2(uf.size(x)),uf.g)))
  else:
    ans.appendleft(ans[0])

print(*ans)

### FIXED CODE ###

from collections import defaultdict

class UnionFind():
    def __init__(self, n=0):
        self.d = [-1]*n
        self.g = set()
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:return False
        if self.d[x] > self.d[y]: x,y=y,x
        self.d[x] += self.d[y]
        self.g.add(x)
        if y in self.g:self.g.remove(y)
        self.d[y] = x
        return True

    def same(self,x,y): return self.find(x)==self.find(y)
    def size(self,x): return -self.d[self.find(x)]
    
def comb2(n):
  return n*(n-1)//2
    
N,M=map(int,input().split())
E = [tuple(map(int,input().split())) for _ in range(M)]

total=comb2(N)
uf = UnionFind(N+1)
ans = [total]
for i in range(M-1):
  a,b = E[-i-1]
  if uf.same(a,b):
    ans.append(ans[-1])
    continue
  else:
    size1,size2 = uf.size(a),uf.size(b)
    uf.unite(a,b)
    size3 = uf.size(a)
    tmp = ans[-1]+comb2(size1)+comb2(size2)-comb2(size3)
    ans.append(tmp)
print(*ans[::-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n = int(input())
    a_list = input_to_int_tuple()

    ret = ""
    for i in range(n):
        my = 0
        for j, v in enumerate(a_list):
            if i == j:
                continue

            my ^= v

        ret += str(my) + " "

    print(ret.rstrip())


if __name__ == "__main__":
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-

# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n = int(input())
    a_list = input_to_int_tuple()

    all = 0
    for v in a_list:
        all ^= v

    ret = ""
    for v in a_list:
        ret += str(all ^ v) + " "

    print(ret.rstrip())


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

n = int(input())
h = list(map(int,input().split()))
h.append(10**10)
counter = []

for i in range(n):
  cnt = 0
  for j in range(i,n):
    if h[j]>=h[j+1]:
      cnt +=1
    else:
      counter.append(cnt)
      break

ans = max(counter)
print(ans)

### FIXED CODE ###

n = int(input())
h = list(map(int,input().split()))
h = h[::-1]
h.append(10**10)
cnt = 0
L = []
for i in range(n):
  L.append(cnt)
  if h[i+1]>=h[i]:
    cnt +=1
  else:
    cnt =0
print(max(L))
### BUGGY CODE ###

import sys
import resource

input = sys.stdin.readline

sys.setrecursionlimit(10 ** 9)
resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))

def main():
  # Nがノードの数, Qが操作回数
  N, Q = map(int, input().split())

  parents = [None] * N
  childrens = [set() for _ in range(N)]
  relations = {}
  shown = set()

  for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    # parents[b] = a
    # childrens[a].add(b)
    relations.setdefault(a, [])
    relations.setdefault(b, [])
    relations[a].append(b)
    relations[b].append(a)

  def f(parent, relations, parents, childrens):
    shown.add(parent)
    for c in relations[parent]:
      if c not in shown:
        parents[c] = parent
        childrens[parent].add(c)
        f(c, relations, parents, childrens)

  f(0, relations, parents, childrens)
  points = {}
  result = [0] * N

  for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    points.setdefault(p, 0)
    points[p] += x

  def solve(idx, parents, childrens, points, result):
    # print(idx)
    if idx in points:
      result[idx] += points[idx]
    if parents[idx] is not None:
      result[idx] += result[parents[idx]]
    for child in childrens[idx]:
      solve(child, parents, childrens, points, result)
      
  solve(0, parents, childrens, points, result)
  print(*result)

if __name__ == "__main__":
  main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 9)

def main():
  input = sys.stdin.buffer.readline
  read = sys.stdin.buffer.read
  # Nがノードの数, Qが操作回数
  N, Q = map(int, input().split())
  ABPX = list(map(int, read().split()))
  AB = iter(ABPX[:N+N-2])
  PX = iter(ABPX[N+N-2:])

  parents = [None] * N
  childrens = [set() for _ in range(N)]
  relations = [[] for _ in range(N)]
  shown = set()

  for a, b in zip(AB, AB):
    a -= 1
    b -= 1
    relations[a].append(b)
    relations[b].append(a)

  points = [0] * N
  result = [0] * N

  for p, x in zip(PX, PX):
    p -= 1
    points[p] += x

  def solve(parent, relations, points, result):
    result[parent] += points[parent]
    shown.add(parent)
    for child in relations[parent]:
      if child not in shown:
        result[child] += result[parent]
        solve(child, relations, points, result)
      
  solve(0, relations, points, result)
  print(*result)

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

N,X,Y=map(int,input().split())

L=[[i+1 for i in range(j+1)][::-1]+[0]*(N-1-j) for j in range(N-1)]
for i in range(len(L)):
    L[i]=[0]+L[i]+[0]
L.append([0]*(N+2))
L.insert(0,[0]*(N+2))
L.insert(0,[0]*(N+2))

H=[i+1 for i in range(N-1)][::-1]

L[Y][X]=1
task=[(Y,X,1)]
while len(task)>0:
    P=task.pop()
    y,x,c=P[0],P[1],P[2]
    if y<0 or x<0 or y>N or x>N:
        continue
    if L[y+1][x]>c+1:
        L[y+1][x]=c+1
        task.append((y+1,x,c+1))
    if L[y-1][x]>c+1:
        L[y-1][x]=c+1
        task.append((y-1,x,c+1))
    if L[y][x+1]>c+1:
        L[y][x+1]=c+1
        task.append((y,x+1,c+1))
    if L[y][x-1]>c+1:
        L[y][x-1]=c+1
        task.append((y,x-1,c+1))
    #print(y,x,c)
    #print(numpy.array(L))

LL=[]
for i in range(len(L)):
    LL+=L[i]

import collections
D=collections.Counter(LL)
d=list(D.values())
d.pop(0)
d+=[0]*(max(N-len(d)-1,0))

for i in d:
    print(i)


### FIXED CODE ###

N,X,Y=map(int,input().split())
ans=[0]*N
X-=1
Y-=1

for i in range(N-1):
    for j in range(i+1,N):
        ans[min(j-i,abs(j-Y)+abs(i-X)+1)]+=1

ans.pop(0)
for i in ans:
    print(i)
### BUGGY CODE ###

h,w,kk = map(int,input().split())
arr = []
for i in range(h):
    arr.append(list(map(int,list(input()))))

h_loop = 2**(h-1)
ans = 100000000
for i in range(h_loop):
    sep = format(i,'b').zfill(h-1)
    ups = sum(map(int,list(sep)))
    slash = ups
    buf = [0 for j in range(ups+1)]
    temp_buf = [0 for j in range(ups+1)]
    is_sep = False
    # print(sep)
    for j in range(w):
        b_ind = 0
        is_sep = False
        for k in range(h):
            if k == 0:
                temp_buf[b_ind] += arr[k][j]
            else:
                if sep[k-1] == "1":
                    b_ind += 1
                    temp_buf[b_ind] += arr[k][j]
                else:
                    temp_buf[b_ind] += arr[k][j]

        for k in range(ups+1):
            if temp_buf[k] + buf[k] > kk:
                is_sep = True
        # print(buf)
        # print(temp_buf)
        # print(is_sep)
        if is_sep:
            slash += 1
            buf = temp_buf
        else:
            for k in range(ups+1):
                buf[k] += temp_buf[k]
        temp_buf = [0 for j in range(ups + 1)]

    # print(slash)
    if ans > slash:
        ans = slash

print(ans)




### FIXED CODE ###

h,w,kk = map(int,input().split())
arr = []
for i in range(h):
    arr.append(list(map(int,list(input()))))

h_loop = 2**(h-1)
ans = 100000000
for i in range(h_loop):
    sep = format(i,'b').zfill(h-1)
    ups = sum(map(int,list(sep)))
    slash = ups
    buf = [0 for j in range(ups+1)]
    temp_buf = [0 for j in range(ups+1)]
    is_sep = False
    # print(sep)
    # print("########")
    # print(slash)
    for j in range(w):
        # print("#####")
        # print(j)
        b_ind = 0
        is_sep = False
        for k in range(h):
            if k == 0:
                temp_buf[b_ind] += arr[k][j]
            else:
                if sep[k-1] == "1":
                    b_ind += 1
                    temp_buf[b_ind] += arr[k][j]
                else:
                    temp_buf[b_ind] += arr[k][j]

        for k in range(ups+1):
            if temp_buf[k] + buf[k] > kk :
                is_sep = True
        for k in range(ups+1):
            if buf[k] > kk :
                slash = 1000000000
        # print(buf)
        # print(temp_buf)
        # print(is_sep)
        if is_sep:
            slash += 1
            buf = temp_buf
        else:
            for k in range(ups+1):
                buf[k] += temp_buf[k]

        temp_buf = [0 for j in range(ups + 1)]


    # print(slash)
    if ans > slash:
        ans = slash

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

N,M = list(map(int,input().split()))
list_A = list(map(int,input().split()))
for i in range(M):
    A = max(list_A)
    list_A.remove(A)
    list_A.append(A // 2)
print(sum(list_A))

### FIXED CODE ###

N,M=list(map(int,input().split()))
import sys
A= list(map(int,sys.stdin.readline().split()))
A=[i*-1 for i in A]
import heapq
heapq.heapify(A)
for i in range(M):
    X=heapq.heappop(A)
    X=abs(X)//2*-1
    heapq.heappush(A,X)
print(abs(sum(A)))
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))
count = 0
li.sort()
for i in range(n - 2):
  for j in range(i + 1, n - 1):
    for k in range(j + 1, n):
      a = li[i]
      b = li[j]
      c = li[k]
      if a < b + c and b < c + a and c < a + b:
        count += 1
 
print(count)

### FIXED CODE ###

import bisect

n = int(input())
li = list(map(int,input().split()))
count = 0
li.sort()
for i in range(n - 2):
  for j in range(i + 1, n - 1):
    ab = li[i] + li[j]
    x = bisect.bisect_left(li, ab, lo=0, hi=n)
    count += (x - j - 1)
 
print(count)
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]
ss = [sorted(i) for i in s]
dic = [''.join(i) for i in ss]
key = [i for i in set(dic)]
cnt = 0
for i in key:
    a = dic.count(i)-1
    cnt += (a * (a+1))/2
print(int(cnt))


### FIXED CODE ###

n = int(input())
s = {}
cnt = 0
for i in range(n):
    j = ''.join(sorted(input()))
    if j in s:
        s[j] += 1
    else:
        s[j] = 0
    cnt += s[j]
print(int(cnt))
### BUGGY CODE ###

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

s = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        s += a[i] * a[j]
        s %= 10 ** 9 + 7

print(s)

### FIXED CODE ###

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

s = 0
for i in range(n):
    s += a[i]

tr = 0
for i in range(n):
    tr += a[i] ** 2

a2 = s ** 2 - tr
a = a2 // 2
a %= 10 ** 9 + 7

print(a)
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
	A.append(int(input()))
A.sort()
ary1 = [A[0]]
ary2 = [A[N-1]]
fst = 0
lst = N
fst_flg = False
while fst + 1 < lst:
	if fst_flg:
		fst_flg = False
		if fst + 2 != lst:
			fst += 1
			ary1 = [A[fst]] + ary1 + [A[fst+1]]
			ary2 = [A[N-1-fst]] + ary2 + [A[N-1-fst-1]]
			fst += 1
		else:
			fst += 1
			ary1 = [A[fst]] + ary1
			ary2 = [A[N-1-fst]] + ary2
	else:
		fst_flg = True
		if fst + 2 != lst:
			lst -= 1
			ary1 = [A[lst]] + ary1 + [A[lst-1]]
			ary2 = [A[N-1-lst]] + ary2 + [A[N-lst]]
			lst -= 1
		else:
			lst -= 1
			ary1 = [A[lst]] + ary1
			ary2 = [A[N-1-lst]] + ary2
sum1,sum2=0,0
for i in range(N-1):
	sum1 += abs(ary1[i] - ary1[i+1])
	sum2 += abs(ary2[i] - ary2[i+1])
print(max(sum1,sum2))

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
	A.append(int(input()))
A.sort()
if N % 2 == 0:
	print(-2*sum(A[:N//2-1]) + 2*(sum(A[N//2+1:])) + A[N//2] - A[N//2-1])
	exit()

a = 2*sum(A[N//2+1:]) - 2*sum(A[:N//2-1]) - A[N//2] - A[N//2-1]
b = 2*sum(A[N//2+2:]) - 2*sum(A[:N//2]) + A[N//2] + A[N//2+1]
print(max(a,b))
### BUGGY CODE ###

def simulate(n):
    if n==-1: return 0
    if n==N: return 2
    
    for i in range(Q):
        if TD[i][0]==s[n]:
            if TD[i][1]=="R": n+=1
            if TD[i][1]=="L": n-=1

        if n<0 : return 0
        elif n>=N: return 2 
    return 1

N, Q = map(int, input().split())
s = input()
TD = [input().split() for i in range(Q)]

low = 0
high =N-1
# t は中央番目の数
t =int((low+high)/2) 

# 探索の下限のlowが上限のhighになるまで探索
# lowがhighに達すると数は見つからなかったということ
while (1):
    if simulate(t) in [0,1] and simulate(t+1)==2:
        break
    elif simulate(t) in [0,1]:
        low = t+1
    elif simulate(t)==2:
        high = t-1
    t = int((low + high) / 2)


R=t

low = 0
high =N-1
# t は中央番目の数
t =int((low+high)/2) 

while (1):
    if simulate(t-1)==0 and simulate(t) in [1,2]:
        break
    elif simulate(t)==0:
        low = t+1
    elif simulate(t) in [1,2]:
        high = t-1
    t = int((low + high) / 2)

L=t

print(R-L+1)

### FIXED CODE ###

N,Q=map(int,input().split())
s="0"+input()+"0"
queri=[list(input().split()) for i in range(Q)]

L,R=0,N+1
for i in range(Q-1,-1,-1):
    t,d=queri[i]
    if t==s[L] and d=="R":
        L-=1
    elif t==s[L+1] and d=="L":
        L+=1
    if t==s[R] and d=="L":
        R+=1
    elif t==s[R-1] and d=="R":
        R-=1

print(R-L-1)
### BUGGY CODE ###

n = int(input())
xy = []
for _ in range(n):
  x, y, h = map(int, input().split())
  xy.append((x, y, h))

def check(cx, cy):
  x, y, h = xy[0]
  ch = h + abs(cx - x) + abs(cy - y)
  if h > 0:
    ch0 = [ch]
  else:
    ch0 = [i for i in range(1, ch+1)]
  
  for (x, y, h) in xy[1:]:
    ch = h + abs(cx - x) + abs(cy - y)
    if h > 0:
      ch0 = [i for i in ch0 if i == ch]
    else:
      ch0 = [i for i in ch0 if i <= ch]
    
    if len(ch0) == 0:
      return False
  return ch0[0]

for cx in range(101):
  for cy in range(101):
    ch = check(cx, cy)
    if ch:
      print(' '.join( map(str, [cx, cy, ch]) ))
      exit()



### FIXED CODE ###

n = int(input())
xy = []
for _ in range(n):
  x, y, h = map(int, input().split())
  xy.append((x, y, h))

def check(cx, cy):
  x, y, h = xy[0]
  ch = h + abs(cx - x) + abs(cy - y)
  if h > 0:
    ch0 = [ch]
  else:
    ch0 = [i for i in range(1, ch+1)]
  
  for (x, y, h) in xy[1:]:
    ch = h + abs(cx - x) + abs(cy - y)
    if h > 0:
      ch0 = [i for i in ch0 if i == ch]
    else:
      ch0 = [i for i in ch0 if i <= ch]
    
    if len(ch0) == 0:
      return False
  return ch0[0]

for cx in range(101):
  for cy in range(101):
    ch = check(cx, cy)
    if ch:
      print(' '.join( map(str, [cx, cy, ch]) ))
      exit()
### BUGGY CODE ###

n=int(input())
s=input()
sl=list(s)

c=0
b=0
w=0
res=2*10^5
for i in range(n-1):
	b = sl[:i].count("#")
	w = sl[i+1:].count(".")
	c = b + w
	#print(c)
	if c < res:
		res = c

if sl.count("#")==n or sl.count(".")==n:
	res = 0

print(res)

### FIXED CODE ###

n=int(input())
sl=list(input())

bi=0
wi=0
b=[]
w=[]
for i in range(n):
	if sl[i] == "#":
		bi = bi+1
	else:
		wi = wi+1
	b.append(bi)
	w.append(wi)

c=0
res=2*10**6
for i in range(n-1):
	if (sl[i]=="#" and sl[i+1]==".") or (sl[i]=="." and sl[i+1]=="#") :
		c = b[i] + w[n-1]-w[i]
		if c < res:
			res = c

w0=w[n-1]
b0=b[n-1]
if w[0]==1:
	for i in range(n-1):
		if w[i]==w[i+1]:
			w0=w[n-1]-w[i]
			break
if b[n-1]-b[n-2]==1:
	for i in range(n-1):
		if b[n-1-i]==b[n-1-i-1]:
			b0=b[n-1-i]
			break

if w0<res:
	res=w0
if b0<res:
	res=b0

print(res)
### BUGGY CODE ###

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

td=sorted([tuple(map(int,input().split())) for _ in range(N)],key=lambda x:-x[1])
answer=0
number=[]
afterpop=[]

for i in range(K):
  answer+=td[i][1]
  if td[i][0] not in number:
    number.append(td[i][0])
  else:
    afterpop.append(td[i][1])

answer+=len(number)**2
    
index=K
tempanswer=answer
while index<N and afterpop:
  if td[index][0] not in number:
    number.append(td[index][0])
    tempanswer=tempanswer+td[index][1]-afterpop.pop()-(len(number)-1)**2+(len(number))**2
    answer=max(tempanswer,answer)
  index+=1
                  
print(answer)

### FIXED CODE ###

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

td=sorted([tuple(map(int,input().split())) for _ in range(N)],key=lambda x:-x[1])
answer=0
number=set()
afterpop=[]

for i in range(K):
  answer+=td[i][1]
  if td[i][0] not in number:
    number.add(td[i][0])
  else:
    afterpop.append(td[i][1])

answer+=(len(number))**2
    
index=K
tempanswer=answer
while index<N and afterpop:
  if td[index][0] not in number:
    number.add(td[index][0])
    tempanswer=tempanswer+td[index][1]-afterpop.pop()-(len(number)-1)**2+(len(number))**2
    answer=max(tempanswer,answer)
  index+=1
                  
print(answer)
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

from collections import defaultdict
n, M = map(int, input().split())
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)

ws = {}
bs = {}
def sub(u, p):
    if (u,p) in ws:
        return ws[u,p], bs[u,p]
    w = 1
    b = 1
    for v in ns[u]:
        if v==p:
            continue
        ww,bb = sub(v, u)
        w += (bb-1)
        b *= (1+bb)
        b %= M
    ws[u,p] = w % M
    bs[u,p] = b % M
    return w,b

ans = [None]*n

for u in range(n):
    ans[u] = sub(u, -1)[1] % M
write("\n".join(map(str, ans)))

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n, M = map(int, input().split())
ns = defaultdict(list)
for _ in range(n-1):
    u,v = map(int, input().split())
    ns[u-1].append(v-1)
    ns[v-1].append(u-1)

bs = {}
cump0 = defaultdict(list)
cump1 = defaultdict(list)
def sub(u, p):
    if (p,u) in bs:
        return bs[p,u]
    b = 1
    ps = []
    for v in ns[u]:
        if v==p:
            continue
        bb = sub(v, u)
        b *= (1+bb)
        b %= M
        ps.append(bb)
    v0 = 1
    v1 = 1
    l = len(ps)
    for i in range(l):
        cump0[u].append(v0)
        cump1[u].append(v1)
        v0 *= ps[i]+1
        v1 *= ps[l-1-i]+1
        v0%=M;v1%=M
    cump0[u].append(v0)
    cump1[u].append(v1)
        
    bs[p,u] = b % M
    return b

ans = [None]*n
def sub2(u, p):
    i = 0
    for v in ns[u]:
        if v==p:
            continue
        b1 = bs[p,u]
        b2 = bs[u,v]
        b3 = bs[u,p]
        if p>=0:
            bb = (cump0[u][i] * cump1[u][-(i+2)] * (1+b3)) % M
        else:
            bb = (cump0[u][i] * cump1[u][-(i+2)]) % M
        bs[v,u] = bb
        ans[v] = bs[u,v] * (1+bb) % M
        sub2(v,u)
        i += 1
        
sub(0, -1)
bs[0,-1] = 1
ans[0] = bs[-1,0]
sub2(0,-1)

# for u in range(n):
#     ans[u] = sub(u, -1)[1] % M
write("\n".join(map(str, ans)))
### BUGGY CODE ###

s = list(input())
mod = 2019
tot = [0]
ans = 0
dp = [0 for _ in range(2020)]
dp[0] = 1
for i in range(len(s)):
    nx = tot[i] + int(s[i])*(10**(len(s)-i))%mod
    nx %= mod
    if dp[nx] != 0:
        ans += dp[nx]
    dp[nx] += 1
    tot.append(nx)
print(ans)

### FIXED CODE ###

s = list(input())
mod = 2019
tot = [0]
ans = 0
dp = [0 for _ in range(2020)]
dp[0] = 1
for i in range(len(s)):
    nx = tot[i] + int(s[i])*(pow(10,(len(s)-i),mod))
    nx %= mod
    if dp[nx] != 0:
        ans += dp[nx]
    dp[nx] += 1
    tot.append(nx)
print(ans)
### BUGGY CODE ###

N = int(input()) 
A=list(map(int,input().split())) 
i=0 
s=[] 
for i in range(N): 
    s.append(0) 
    s[i]=A.count(i+1) 
    print(s[i])

### FIXED CODE ###

import collections
n = int(input())
base = map(int,input().split())
c = collections.Counter(base)
for i in range(1,n):
    print(c[i])
print(0)
### BUGGY CODE ###

import numpy as np
n,k = map(int,input().split())	
s=list(input())	
s = np.array(s, dtype = int)
li = np.array([])
is1s = False
if s[0] == 1:
    is1s = True
cnt0 = 0
cnt1 = 0
for i in range(len(s)):
    if s[i] ==0 :
        cnt0 += 1
    if s[i] == 1:
        cnt1 += 1
    if i >= 1:
        if s[i] == 0 and s[i-1] == 1:
            li=np.append(li,cnt1)
            cnt1 = 0
        if s[i] == 1 and s[i-1] == 0: 
            li=np.append(li,cnt0)
            cnt0 = 0

if (cnt1 > 0):
    li=np.append(li,cnt1)
if (cnt0 > 0):
    li=np.append(li,cnt0)
pivot = 2 * k 

anslist=np.array([])
if(is1s):
    for i in range(len(li)):
        if(i % 2 == 0):
            tmp = np.sum(li[i:min(len(li), i+pivot+1)])
            anslist=np.append(anslist, tmp)
else:
    for i in range(len(li)):
        if(i % 2 == 1):
            tmp = np.sum(li[i:min(len(li), i+pivot+1)])
            anslist=np.append(anslist ,tmp)
    anslist=np.append(anslist, np.sum(li[0:pivot]))

print(int(np.max(anslist)))


### FIXED CODE ###

import numpy as np
n,k = map(int,input().split())	
s=list(input())	

li = []
is1s = False
if s[0] == "1":
    is1s = True
cnt0 = 0
cnt1 = 0
for i in range(len(s)):
    if s[i] == "0" :
        cnt0 += 1
    elif s[i] == "1":
        cnt1 += 1
    if i >= 1:
        if s[i] == "0" and s[i-1] == "1":
            li.append(cnt1)
            cnt1 = 0
        elif s[i] == "1" and s[i-1] == "0": 
            li.append(cnt0)
            cnt0 = 0

if (cnt1 > 0):
    li.append(cnt1)
if (cnt0 > 0):
    li.append(cnt0)
pivot = 2 * k 
li = np.array(li)
anslist=[]
if(is1s):
    for i in range(len(li)):
        if(i % 2 == 0):
            tmp = np.sum(li[i:min(len(li), i+pivot+1)])
            anslist.append(tmp)
else:
    for i in range(len(li)):
        if(i % 2 == 1):
            tmp = np.sum(li[i:min(len(li), i+pivot+1)])
            anslist.append(tmp)
    anslist.append(sum(li[0:pivot]))

print(max(anslist))
### BUGGY CODE ###

x=input()
ans=len(x)
while 1:
    x=x.replace("ST","")
    if len(x)==ans: break
    ans=len(x)
print(ans)


### FIXED CODE ###

X=raw_input()
l=[0,0]
for i in X:
    if i=='S':
        l[0]+=1
    elif i=='T' and l[0]>0:
        l[0]-=1
    else:
        l[1]+=1
print sum(l)
### BUGGY CODE ###

N,Q = map(int, input().split())
chi = [set([i]) for i in range(N)]


for n in range(N-1):
    a,b = map(int, input().split())
    chi[a-1].add(b-1)
    for i in range(N):
        if a-1 in chi[i]:
            chi[i] = chi[i] | chi[a-1]  
            
cnt = [0]*N   
for q in range(Q):
   p,x = map(int, input().split())
   for i in chi[p-1]:
       cnt[i] += x

for n in range(N):
    print(cnt[n], end=" ")

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
        
N,Q = (int(i) for i in input().split())
A = [[] for _ in range(N)]

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

cnt = [0]*N   
for q in range(Q):
   p,x = (int(i) for i in input().split())
   cnt[p-1] += x

st = deque([(0,-1)])
while st:
    n,par = st.popleft()
    val = cnt[n]   
    for node in A[n]:
        if node == par:
            continue
        else:
            cnt[node] += val
            st.append([node,n])

print(*cnt)