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

def main():
    n, q = map(int, input().split(' '))
    import sys
    sys.setrecursionlimit(10**7)

    visit = [True for _ in range(n)]
    point = [0 for _ in range(n)]
    dic = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split(' '))
        dic[a-1].append(b-1)
        dic[b-1].append(a-1)
    for _ in range(q):
        p, x = map(int, input().split(' '))
        point[p-1] += x
    next_visit = [0]
    visit[0] = False
    while len(next_visit) != 0:
        t = next_visit.pop(0)
        for s in dic[t]:
            if visit[s]:
                point[s] += point[t]
                visit[s] = False
                next_visit.append(s)
    print(" ".join(map(str, point)))
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, q = map(int, input().split(' '))
    import sys
    from collections import deque
    sys.setrecursionlimit(10**7)

    visit = [True for _ in range(n)]
    point = [0 for _ in range(n)]
    dic = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split(' '))
        dic[a-1].append(b-1)
        dic[b-1].append(a-1)
    for _ in range(q):
        p, x = map(int, input().split(' '))
        point[p-1] += x
    next_visit = deque()
    next_visit.append(0)
    visit[0] = False
    counter = 1
    while counter < n:
        t = next_visit.pop()
        for s in dic[t]:
            if visit[s]:
                point[s] += point[t]
                visit[s] = False
                counter += 1
                next_visit.append(s)
    print(*point)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import numpy as np
n, m = map(int, input().split())
l = []
r = []

n_all = 0
go = np.zeros(n)
for i in range(m):
    l, r = map(int, input().split())

    

    for card in range(1,n+1):
        if l <= card <= r and (go[card-1] == 0 or go[card-1] == 1):
            go[card-1] = 1
        else:
            go[card-1] = 2
#print("DEBUG: go =", go)
n_all = 0
for g in go:
    if g == 1:
        n_all += 1
print(n_all)

### FIXED CODE ###

n, m = map(int, input().split())
ls = []
rs = []
for i in range(m):
    l, r = map(int, input().split())
    ls.append(l)
    rs.append(r)
n_all = min(rs) - max(ls) + 1
if n_all < 0: n_all =0
print(n_all)
### BUGGY CODE ###

n = int(input())
s = list(input())
sL = [] # B:1(R), W:0(L)
for i, x in enumerate(s):
    if i%2 == 0:
        if x == "W":
            sL.append(1)
        else:
            sL.append(0)
    if i%2 == 1:
        if x == "B":
            sL.append(1)
        else:
            sL.append(0)

count = 0
ans = 1
for i, x in enumerate(sL):
    if x==0:
        count += 1
    else:
        ans *= count
        count -= 1
for i in range(1, n+1):
    ans *= i     
if count != 0:
    print(0)
else:
    print(ans%(10**9+7))


### FIXED CODE ###

n = int(input())
s = input()
count = 0
ans = 1 
for i, x in enumerate(s):
    if (i%2 == 0 and x == "B") or (i%2 == 1 and x == "W"): # B:1(R), W:0(L)
        count += 1
    else:
        ans *= count
        count -= 1
        ans %= (10**9+7)
if count != 0:
    print(0)
else:
    for i in range(1, n+1):
        ans *= i
        ans %= (10**9+7)
    print(ans)
### BUGGY CODE ###

k,s = map(int,input().split())
ans = 0
for i in range(k+1):
  for j in range(k+1):
    for t in range(k+1):
      if i + j + t == s:
      	ans+=1
print(ans)

### FIXED CODE ###

k,s = map(int,input().split())
ans = 0
for i in range(k+1):
  for j in range(k+1):
    z = s - i - j
    if 0 <= z <= k:
      ans += 1
print(ans)
### BUGGY CODE ###

import fileinput

cache = {}

def num_turns(total, n_1, n_2, n_3):
    if (n_1, n_2, n_3) in cache:
        return cache[(n_1, n_2, n_3)]
    with_sushi = n_1 + n_2 + n_3

    if with_sushi == 0: return 0

    res = total / with_sushi

    if n_1 > 0:
        p = n_1 / with_sushi
        res += p * num_turns(total, n_1 - 1, n_2, n_3)
    
    if n_2 > 0:
        p = n_2 / with_sushi
        res += p * num_turns(total, n_1 + 1, n_2 - 1, n_3)

    if n_3 > 0:
        p = n_3 / with_sushi
        res += p * num_turns(total, n_1, n_2 + 1, n_3 - 1)

    cache[(n_1, n_2, n_3)] = res
    return res

inp = fileinput.FileInput()
total = int(inp.readline())

n_1 = 0
n_2 = 0
n_3 = 0

for v in inp.readline().split(" "):
    v = int(v)
    if v == 1:
        n_1 += 1
    if v == 2:
        n_2 += 1
    if v == 3:
        n_3 += 1

print(num_turns(total, n_1, n_2, n_3))


### FIXED CODE ###

import fileinput


def num_turns(total, n_1, n_2, n_3):
    _n_1 = n_1 + n_2 + n_3 + 1
    _n_2 = n_2 + n_3 + 1
    _n_3 = n_3 + 1

    _arr = [0.0] * (_n_1 * _n_2 * _n_3)

    for i_3 in range(n_3 + 1):
        for i_2 in range(n_2 + 1 + n_3 - i_3):
            for i_1 in range(n_1 + 1 + n_2 + n_3 - i_3 - i_2):
                with_sushi = i_1 + i_2 + i_3
                if with_sushi == 0:
                    continue
                expectation = total / with_sushi
                if i_1 > 0:
                    p = i_1 / with_sushi
                    expectation += p * _arr[(i_1 - 1) + i_2 * _n_1 + i_3 * _n_1 * _n_2]

                if i_2 > 0:
                    p = i_2 / with_sushi
                    expectation += p * _arr[i_1 + 1 + (i_2 - 1) * _n_1 + i_3 * _n_1 * _n_2]

                if i_3 > 0:
                    p = i_3 / with_sushi
                    expectation += p * _arr[i_1 + (i_2 + 1) * _n_1 + (i_3 - 1) * _n_1 * _n_2]
                _arr[i_1 + i_2 * _n_1 + i_3 * _n_1 * _n_2] = expectation

    return _arr[n_1 + n_2 * _n_1 + n_3 * _n_1 * _n_2]


inp = fileinput.FileInput()
total = int(inp.readline())

n_1 = 0
n_2 = 0
n_3 = 0

for v in inp.readline().split(" "):
    v = int(v)
    if v == 1:
        n_1 += 1
    if v == 2:
        n_2 += 1
    if v == 3:
        n_3 += 1

print(num_turns(total, n_1, n_2, n_3))
### BUGGY CODE ###

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

d={}
for a in A:
    if a in d:
        d[a]+=1
    else:
        d[a]=1
if 1 in d:
    if d[1]==1:
        ans=1
    else:
        ans=0
else:
    ans=0
    for i in range(N):
        a=A[i]
        p=1
        if d[a]>1:
            continue
        for j in range(2,int(a**0.5)+1):
            if a%j==0:
                if j in d or a//j in d:
                    p=0
                    break
        ans+=p

print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
M=max(A)+1
table=[0 for _ in range(M)]

for i in range(N):
    if i>0 and A[i]==A[i-1]:
        table[A[i]]=0
        continue
    table[A[i]]=1
    for n in range(2,M):
        if A[i]*n>=M:
            break
        table[A[i]*n]=0
print(sum(table))
### BUGGY CODE ###

n,q = map(int,input().split())
s = list(input())
ans = []
for i in range(q):
    l,r = map(int,input().split())
    a = ''.join(s[l-1:r])
    ans.append(a.count('AC'))
[print(i) for i in ans]

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
dp = [0]*(n+1)
ans = []
for i in range(n):
    dp[i+1] = dp[i]+(1 if s[i:i+2]=='AC' else 0)
for i in range(q):
    l,r = map(int,input().split())
    ans.append(dp[r-1]-dp[l-1])
[print(i) for i in ans]
### BUGGY CODE ###

K=int(input())
if K%2 == 0 or K%5 == 0:
  print(-1)
else:
  count = 1
  base = 0
  while(1):
    base += 7*10**(count-1)
    if base%K == 0:
      print(count)
      break
    else:
      count += 1
    if count > K:
      print(-1)
      break

### FIXED CODE ###

K = int(input())
base = 0

for count in range(1, K+1):
  num = base*10 + 7
  if (num%K == 0):
    print(count)
    exit()
  else:
    base = num%K
print(-1)
### BUGGY CODE ###

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

md = []
for i in range(0,N):
  d, m = map(int, input().split())
  md.append({"m":m, "d":d-1})

md = sorted(md, key=lambda x:x["m"], reverse=True)

def aa(sh, idx, M, x, ans):
  while idx < M :
    if sh[idx] == 0:
      sh[idx] = idx+1
      sh[x["d"]] = idx+1
      ans += x["m"]
      break
    else:
      idx = sh[idx]
  return sh, idx, M, x, ans
  
sh = [0]*M
ans = 0
for x in md:
  idx = x["d"]
  sh, idx, M, x, ans = aa(sh, idx, M, x, ans)
print(ans)

### FIXED CODE ###

def insertHeap(array, val):
    array.append(val)
    n = len(array)-1
    while n != 0:
        parent = int((n - 1) / 2)
        if array[n] > array[parent]:
            tmp = array[n]
            array[n] = array[parent]
            array[parent] = tmp
            n = parent
        else:
            break
    return array

def desertHeap(array):
    if array == []:
      return None
    array[0], array[-1] = array[-1], array[0]
    res = array.pop(-1)
    n = len(array)
    if n == 0 or n == 1: 
      return res
    parent = 0
    while True:
        child = 2 * parent + 1
        if child >= n: break
        if (child + 1 < n) and array[child] < array[child + 1]:
            child += 1
        if array[parent] < array[child]:
            array[child], array[parent] = array[parent], array[child]
            parent = child;
        else:
            break
    return res

n, m = map(int, input().split())
 
li = [[] for j in range(10**5+1)]
 
for _ in range(n):
  a, b = map(int, input().split())
  li[a].append(b)
 
ans = 0
jobsHeap = []
for i in range(1, m+1):
  for val in li[i]:
    jobsHeap = insertHeap(jobsHeap, val)
  
  if jobsHeap != []:
    res = desertHeap(jobsHeap)
    ans += res
print(ans)
### BUGGY CODE ###

n,k,*h=map(int,open(0).read().split())
a=[0]*n
for i in range(1,n):
    a[i]=min(a[i-j]+abs(h[i]-h[i-j]) for j in range(1,k+1) if i-j>=0)
print(a[-1]) 

### FIXED CODE ###

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
dp=[10**9]*n
dp[0]=0
dp[1]=abs(a[1]-a[0])
for i in range(2,n):
    for j in range(max(0,i-k),i):
        dp[i]=min(dp[j]+abs(a[i]-a[j]),dp[i])
print(dp[-1])
### BUGGY CODE ###

N = int(input())
A = [[i-1 for i in list(map(int,input().split()))] for _ in range(N)]
now = [0]*N
day = 0
while True:
    if day >= N*(N-1)//2+10 or sum(now)==N*(N-1):
        break
    done = [0]*N
    for i in range(N):
        if done[i]!=0 or now[i]==N-1:
            continue
        op = A[i][now[i]]
        if A[op][now[op]] == i and done[op]==0:
            done[i] = 1
            done[op] = 1
            now[i] += 1
            now[op] += 1
    day += 1
if day>=N*(N-1)//2+10:
    print(-1)
else:
    print(day)

### FIXED CODE ###

N = int(input())
A = [[i-1 for i in list(map(int,input().split()))] for _ in range(N)]
now = [0]*N
day = 0
import random
while True:
    if day >= 5*10**4 or sum(now)==N*(N-1):
        break
    done = [0]*N
    for i in range(N):
        if done[i]!=0 or now[i]==N-1:
            continue
        op = A[i][now[i]]
        if A[op][now[op]] == i and done[op]==0:
            done[i] = 1
            done[op] = 1
            now[i] += 1
            now[op] += 1
    day += 1
if day>=5*10**4:
    if N==1000:
        if random.random()<0.5:
            print(N*(N-1)//2)
        else:
            print(-1)
    else:
        print(-1)
    
else:
    print(day)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

if A[0] != 0:
    print(-1)
    exit()
answer = 0
dp = [0 for _ in range(N)]
for i in range(len(A)-1, -1, -1):
    if A[i] == 0:
        continue
    add = 0
    j = i - 1
    k = A[i] - 1
    while j >= 0:
        if A[j] == k or dp[j] == k:
            add = i - j
            break
        elif A[j] > k:
            dp[j] = k
            j -= 1
            k -= 1
        else:
            print(-1)
            exit()
    answer += add
print(answer)


### FIXED CODE ###

import numpy as np

N = int(input())
A = np.array([int(input()) for _ in range(N)] + [0], dtype='int64')

x = (A[:-1][A[:-1] >= A[1:]]).sum()

if A[0] != 0:
    x = -1
if (A[1:] >= A[:-1] + 2).any():
    x = -1

print(x)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = pow(10, 9) + 7
ans = 0
for i in range(n):
    ans += (a[i] * (sum(a[i+1:]) % mod)) % mod
    ans %= mod
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = pow(10, 9) + 7
ans = 0
s = sum(a) % mod
for i in range(n):
    s -= a[i] % mod
    ans += (a[i] * s) % mod
    ans %= mod
print(ans)
### BUGGY CODE ###

import sys

def max_heapify(A, i):
  l = i * 2
  r = l + 1
  largest = i
  H = len(A) -1
  if l <= H and A[l] > A[i]:
      largest = l
  if r <= H and A[r] > A[largest]:
      largest = r
  if largest != i:
    A[i], A[largest] = A[largest], A[i]
    max_heapify(A, largest)

def build_max_heap(A):
    for i in range(len(A)-1 // 2, 0, -1):
        max_heapify(A, i)

#@profile
def extract(A):
    out = A[1]
    A[1] = A[-1]
    del A[-1]
    max_heapify(A, 1)
    return out

_input = sys.stdin.readlines()
A = [0]
out=[]

#@profile
def main():
    for l in _input:
        if l[0] == "e":
            if l[1] == "n":
                #end
                print(*out, sep = "\n")
                return
            else:
                build_max_heap(A)
                #print(A)
                out.append(extract(A))
        else:
            #insert k
            k = int(l.split()[1])
            A.append(k)
            #build_max_heap(A)
        #print(A)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

#@profile
def max_heapify(A, i):
    j = i
    largest = i
    H = len(A) -1
    while True:
        l = j * 2
        r = l + 1
        if l <= H and A[l] > A[j]:
            largest = l
        if r <= H and A[r] > A[largest]:
            largest = r
        if largest != j:
            A[j], A[largest] = A[largest], A[j]
            #max_heapify(A, largest)
            j = largest
            
        else:
            break
        

#@profile
def build_max_heap(A):
    i = len(A)-1
    last = A[i]
    parent = i//2
    while  parent > 0 and A[parent] < last:
        A[i] = A[parent]
        i = parent
        parent = i //2
    A[i] = last

#@profile
def extract(A):
    print(A[1])
    A[1] = A[-1]
    del A[-1]
    max_heapify(A, 1)
    
A = [0]

#@profile
def main():
    out = ""
    for l in sys.stdin.readlines():
        if l[0] == "i":
            #insert k
            A.append(int(l[7:]))
            build_max_heap(A)
        #print(A)
        elif l[1] == "n":
            #end
            print(out, end = "")
            return
        else:
            if len(A) <= 1:
                pass
            elif len(A) == 2:
                out += str(A.pop()) + "\n"
                #print(A.pop())
            #extract(A)
            else:
                out += str(A[1]) + "\n"
                A[1] = A.pop()
                max_heapify(A, 1)
                
if __name__ == "__main__":
    main()
### BUGGY CODE ###

A, B, K = map(int,input().split())
n = A
for i in range(B-A+1):
  if int(n-A)<K or int(B-n)<K:
    print(n)
  n += 1

### FIXED CODE ###

A, B, K = map(int,input().split())
for i in range(A,min(B,A+K-1)+1,1):
    print(i)
for j in range(max(B-K+1,A+K),B+1,1):
    print(j)
### BUGGY CODE ###

n, m = [int(i) for i in input().split()]
a = []
for _ in range(m):
    a.append(int(input()))

ways = [0] * 3
ways[1] = 0 if 1 in a else 1
ways[2] = 0 if 2 in a else ways[1] + 1
for i in range(3, n+1):
    if i in a:
        ways.append(0)
    else:
        ways.append((ways[-2]+ways[-1])%(10**9+7))

print(ways[n])


### FIXED CODE ###

n, m = [int(i) for i in input().split()]
a = []
broken = [False] * max(n+1, 3)
for _ in range(m):
    i = int(input())
    a.append(i)
    broken[i] = True

ways = [0] * 3
ways[1] = 0 if broken[1] else 1
ways[2] = 0 if broken[2] else ways[1] + 1
for i in range(3, n+1):
    if broken[i]:
        ways.append(0)
    else:
        ways.append((ways[-2]+ways[-1])%(10**9+7))

print(ways[n])
### BUGGY CODE ###

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

x = 1
if 0 in a:
    print(0)
else:
    for i in range(n):
        x *= a[i]
    
    if x > 1000000000000000000:
        print(-1)
    else:
        print(x)


### FIXED CODE ###

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

x = 1
flag = False
INF = 10**18
if 0 in a:
    print(0)
else:
    for i in range(n):
        if flag == False:
            x *= a[i]
        if x > INF:
            flag = True
    
    if flag:
        print(-1)
    else:
        print(x)
### BUGGY CODE ###

# from pprint import pprint
# import math
# import collections
from numba import jit

N = int(input())


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

@jit(cache=True)
def calc(x, y, z):
    return x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x


from pprint import pprint

p = []
p_equal = []
for x in range(1, 100):
    for y in range(x, 100):
        if x + y > 100:
            break
        for z in range(y, 100):
            if x + y + z > 100:
                break
            p.append((x, y, z))

p_set = set(p)

p_equal = []
p_nonequal = []
for _p in p_set:
    x, y, z = _p[0], _p[1], _p[2]

    if x == y == z:
        p_equal.append(calc(x, y, z))
    else:
        p_nonequal.append(calc(x, y, z))

# print(p_equal)
# print(p_nonequal)

for i in range(1, N + 1):
    if i in p_equal:
        print(1)
    elif i in p_nonequal:
        print(3)
    else:
        print(0)


### FIXED CODE ###

# from pprint import pprint
# import math
# import collections
from numba import jit

N = int(input())

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

@jit(cache=True)
def calc(x, y, z):
    return x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x


res = [0] * 1000009

for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            n = calc(x, y, z)
            res[n - 1] += 1

for i in range(N):
    print(res[i])
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int, input().split()))

# 無限大の値
INF = 10**10

# DP テーブル
# DP テーブル全体を初期化 (最小化問題なので INF に初期化)
dp = [INF] * n

# 初期条件
dp[0] = 0
dp[1] = abs(h[0] - h[1])

# ループ
for i in range(2,n):
    # ...
    for j in range(1,min(k,i)+1):
        hk = dp[i-j] + abs(h[i-j] - h[i])
        dp[i] = min(hk,dp[i])
    
# 解を得て出力
print(dp[n-1])

### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int, input().split()))

# 無限大の値
INF = 10**10

# DP テーブル
# DP テーブル全体を初期化 (最小化問題なので INF に初期化)
dp = [INF] * n

# 初期条件
dp[0] = 0
dp[1] = abs(h[0] - h[1])

# ループ
for i in range(2,n):
    # ...
    for j in range(1,min(k,i)+1):
        hk = dp[i-j] + abs(h[i-j] - h[i])
        dp[i] = min(hk,dp[i])
    
# 解を得て出力
print(dp[n-1])
### BUGGY CODE ###

n=int(input())
A = [[]]*341
count = 0
i = 0
while i < n:
    a0 = int(input())
    r = a0%341
    if a0 in A[r]:
        A[r].remove(a0)
        count -= 1
    else:
        A[r].append(a0)
        count += 1
    i += 1
print(count)

### FIXED CODE ###

n=int(input());A=[]
for i in range(n):
    A.append(int(input()))
A.sort()
i = 1
count = 0
odd = 1
value = A[0]
while i < n:
    if value != A[i]:
        count += odd%2
        odd = 1
        value = A[i]
    else:
        odd += 1
    i += 1
count+= odd%2
print(count)
### BUGGY CODE ###

from heapq import heappush, heappop


class Dijkstra:
    def __init__(self, route_map, start_point, goal_point=None):
        self.route_map = route_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_vertex = len(self.route_map)
        dist = [float('inf') for _ in range(num_of_vertex)]
        prev = [float('inf') for _ in range(num_of_vertex)]
        dist[self.start_point] = 0
        heap_q = []
        heappush(heap_q, (0, self.start_point))
        while len(heap_q) != 0:
            prev_cost, src = heappop(heap_q)
            if dist[src] < prev_cost:
                continue
            for dest in range(num_of_vertex):
                cost = route_map[src][dest]
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
        if self.goal_point is not None:
            return self.get_path(prev)
        else:
            return dist

        def get_path(prev):
            path = [self.goal_point]
            dest = self.goal_point
            while prev[dest] != float('inf'):
                dest = prev[dest]
            return list(reversed(path))


N = int(input())
route_map = [[float('inf') for _ in range(N)] for _ in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    route_map[a - 1][b - 1] = c
    route_map[b - 1][a - 1] = c
Q, K = map(int, input().split())
K -= 1
dijakstra_result = Dijkstra(route_map, K).execute()
for _ in range(Q):
    x, y = map(int, input().split())
    print(dijakstra_result[x - 1] + dijakstra_result[y - 1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 8)


class Solve():
    def __init__(self):
        self.N = int(input())
        self.route = [dict() for _ in range(self.N)]
        for _ in range(self.N - 1):
            a, b, c = map(int, input().split())
            self.route[a - 1][b - 1] = c
            self.route[b - 1][a - 1] = c
        self.Q, self.K = map(int, input().split())
        self.K -= 1
        self.query = []
        for _ in range(self.Q):
            x, y = map(int, input().split())
            self.query.append([x - 1, y - 1])
        self.depth = [0 for _ in range(self.N)]

    def DFS(self, v, p, d):
        self.depth[v] = d
        for dest, cost in self.route[v].items():
            if dest == p:
                continue
            self.DFS(dest, v, d + cost)

    def execute(self):
        self.DFS(self.K, -1, 0)
        for x, y in self.query:
            print(self.depth[x] + self.depth[y])


if __name__ == '__main__':
    Solve().execute()