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

import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 = list(map(int,sys.stdin.readlines())) #縦入力
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""
n,m =  map(int, sys.stdin.readline().split())

dp=[0]*(n+1)
list_a = list(map(int,sys.stdin.readlines()))

dp[0]=1

for i in range(1,n+1):
    if i in list_a:
        dp[i]=0
    else:
        dp[i] = dp[i-1] + dp[i-2] #dp[-1]=0
ans = dp[n] % big_prime
print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
INF = 1000000007

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in a:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF

print(dp[N])
### BUGGY CODE ###

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

a=[]

for i in range(1,N+1):
    a.append(A.index(i)+1)

print(" ".join(map(str,a)))

### FIXED CODE ###

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

a=[0]*N

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

print(" ".join(map(str,a)))
### BUGGY CODE ###

x= int(input())
k = 1
while True:
  if 360/x == k:
    print(k)
    break
  k+=1

### FIXED CODE ###

x= int(input())
k = 1
while True:
  a = x*k
  if a%360==0:
    print(k)
    break
  k+=1
### BUGGY CODE ###

if __name__ == "__main__":
    n, k = map(int, input().split())
    arr = list(map(int,input().split()))

    tmp = 0
    tmp_arr = []
    for i in range(n - (k - 1)):
        sum_tmp = sum(arr[i:i+k])
        if sum_tmp >= tmp:
            tmp = sum_tmp
            tmp_arr = arr[i:i+k]
    ans = 0
    for j in tmp_arr:
        tmp_sum = 0
        for m in range(1, j+1):
            tmp_sum += m
        ans += tmp_sum / j
    print(ans)

### FIXED CODE ###

n, k = [int(x) for x in input().split()]
arr = list(map(int,input().split()))

m = sum(arr[0:k])
sump = m

for i in range(1, n-k+1):
    sump = sump - arr[i-1] + arr[i+k-1]
    if m < sump:
        m = sump

ans = (m + k) / 2

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

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = float('inf')
    MX = 10**9
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,L = LI()
    road = [[] for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        if c <= L:
            road[a-1].append((b-1,c))
            road[b-1].append((a-1,c))

    town = [[[-1,0] for _ in range(N)] for _ in range(N)]

    for s in range(N):

        q = [(0,s)]
        heapq.heapify(q)
        while q:
            z,u = heapq.heappop(q)
            n = z // MX
            w = z % MX
            for v,c in road[u]:
                nn = n
                nw = w + c
                if nw > L:
                    nw = c
                    nn += 1

                if town[s][v][0] < 0 or town[s][v][0] > nn or \
                        town[s][v][0] == nn and town[s][v][1] > nw:
                    town[s][v][0] = nn
                    town[s][v][1] = nw
                    heapq.heappush(q,(nn*MX + nw,v))

    Q = NI()
    for _ in range(Q):
        s,t = LI()
        print(town[s-1][t-1][0])


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq


def wf(d,n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

def main():
    INF = 10**18
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,L = LI()
    road = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        if c <= L:
            road[a-1][b-1] = c
            road[b-1][a-1] = c

    road = wf(road,N)


    gas = [[INF] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if road[i][j] <= L:
                gas[i][j] = 1

    gas = wf(gas,N)

    Q = NI()
    for _ in range(Q):
        s,t = LI()
        if gas[s-1][t-1] == INF:
            print(-1)
        else:
            print(gas[s-1][t-1]-1)


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

# C
import functools
def gcd(a,b):
    if a<b:a,b=b,a
    if a%b==0:return b
    return gcd(b,a%b)

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
pre_a = -1

for i in range(n):
    if pre_a != a[i]:
        if len(a[:i]) >= 1 and len(a[i+1:]) >= 1:
            res = gcd(functools.reduce(gcd, a[:i]), functools.reduce(gcd, a[i+1:]))
        else:
            values = a[:i] + a[i+1:]
            res = functools.reduce(gcd, values)
        ans = max(ans, res)
    pre_a = a[i]
print(ans)


### FIXED CODE ###

# C
import functools
# 3.4以前は math の gcd が対応していないので fractions のものを使う
# from fractions import gcd
def gcd(a,b):
    if a<b:a,b=b,a
    if a%b==0:return b
    return gcd(b,a%b)


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

gcd_left = [a[0]]
gcd_right = [a[-1]]
for i in range(1,n):
    if gcd_left[i-1] != 1:
        res = gcd(gcd_left[i-1], a[i])
    else:
        res = 1
    gcd_left.append(res)

for i in range(1,n):
    if gcd_right[i-1] != 1:
        res = gcd(gcd_right[i-1], a[-(i+1)])
    else:
        res = 1
    gcd_right.append(res)
gcd_right = gcd_right[::-1]


ans = 0
for i in range(n):
    if i == 0:
        res = gcd_right[1]
    elif i == n-1:
        res = gcd_left[-2]
    else:
        res = gcd(gcd_right[i+1], gcd_left[i-1])
    ans = max(res, ans)
print(ans)
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]
if all(s[i][j]==s[0][0] for i in range(n) for j in range(n)): print(n**2)
else:
	for i in range(n): s[i] += s[i]
	ans = 0
	for i in range(n):
		s2 = []
		for j in s: s2.append(j[i:i+n])
		s2 += s2
		for k in range(n):
			flag = True
			for k2 in range(k,n+k):
				for k3 in range(n):
					if s2[k2][k3]!=s2[k3+k][k2-k]:
						flag = False
						break
				if not flag: break
			if flag: ans += 1
	print(ans)

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]
s,s2,ans = s+s,[],0
for i in range(n):
	x = ""
	for j in s: x+=j[i]
	s2.append(x)
for i in range(n):
	flag = True
	for j in range(i,i+n):
		if s[j][1:n]!=s2[j-i][1+i:n+i]:
			flag = False
			break
	if flag: ans += n
print(ans)
### BUGGY CODE ###

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

AB = []

for _ in range(M):
    A_i, B_i = map(int, input().split())
    AB.append([A_i, B_i])
    
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)
      
uf = UnionFind(N+1)
max_inconvenience = N * (N-1) // 2
ans_list = []
for bridge in reversed(AB):
    #print("====")
    #print(bridge)
    uf.union(bridge[0], bridge[1])

    #print(uf.par)
    #print(uf.rank)
    #print(uf.find(1),uf.find(2),uf.find(3),uf.find(4))
    
    count = {}
    for i in range(1, N+1):
        x = uf.find(i)
        if x in count:
            count[x] += 1
        else:
            count[x] = 1
    #print(count)
    ans = 0
    for c in count.values():
        ans += c * (c - 1) // 2
    ans_list.append(ans)

for ans in reversed(ans_list[:-1]):
    print(max_inconvenience - ans)
print(max_inconvenience)
    



### FIXED CODE ###

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

AB = []

for _ in range(M):
    A_i, B_i = map(int, input().split())
    AB.append([A_i, B_i])

class UnionFind():
    def __init__(self, n):
        self.parent = [-1 for _ in range(n)] # 親なら -1 * サイズ
        
    def root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]
    def size(self, x):
        x = self.root(x)
        return -1 * self.parent[x]
    
    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        x_size = self.size(x)
        y_size = self.size(y)
        if x_size < y_size:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        return True
        
max_inconvenience = N * (N - 1) // 2 
ans = [max_inconvenience]
uf = UnionFind(N)
for bridge in reversed(AB):
    x = uf.root(bridge[0] - 1)
    y = uf.root(bridge[1] - 1)

    if x != y:
        x_size = uf.size(x)
        y_size = uf.size(y)
        ans_tmp = max_inconvenience - x_size * y_size
        max_inconvenience = ans_tmp
        uf.union(x, y)
    else:
        ans_tmp = max_inconvenience
    ans.append(ans_tmp)
    
for a in reversed(ans[:-1]):
    print(a)
### BUGGY CODE ###

import sys
from collections import deque, defaultdict


def bfs(links, s=0):
    ans = [0] * len(links)
    q = deque([(0, s, -1)])
    while q:
        cost, v, p = q.popleft()
        ans[v] = cost
        cost += 1
        q.extend((cost, u, v) for u in links[v] if u != p)
    return ans


def solve(n, k, ab):
    if k == 1:
        return n - 2

    links = [set() for _ in range(n)]
    for a, b in zip(ab[0::2], ab[1::2]):
        a -= 1
        b -= 1
        links[a].add(b)
        links[b].add(a)

    ans = n
    thr = k // 2
    if k % 2 == 0:
        for v in range(n):
            ans = min(ans, sum(d > thr for d in bfs(links, v)))
    else:
        cache = {}
        for a, b in zip(ab[0::2], ab[1::2]):
            a -= 1
            b -= 1
            if a in cache:
                da = cache[a]
            else:
                da = cache[a] = bfs(links, a)
            if b in cache:
                db = cache[b]
            else:
                db = cache[b] = bfs(links, b)
            ans = min(ans, sum(d1 > thr and d2 > thr for d1, d2 in zip(da, db)))
    return ans


n, k, *ab = map(int, sys.stdin.buffer.read().split())
print(solve(n, k, ab))


### FIXED CODE ###

import sys
from collections import deque


def bfs(links, s, limit):
    not_reachable = [True] * len(links)
    q = deque([(0, s, -1)])
    while q:
        cost, v, p = q.popleft()
        if cost > limit:
            break
        not_reachable[v] = False
        cost += 1
        q.extend((cost, u, v) for u in links[v] if u != p)
    return not_reachable


def solve(n, k, ab):
    if k == 1:
        return n - 2

    links = [set() for _ in range(n)]
    for a, b in zip(ab[0::2], ab[1::2]):
        a -= 1
        b -= 1
        links[a].add(b)
        links[b].add(a)

    ans = n
    thr = k // 2
    if k % 2 == 0:
        ans = min(sum(bfs(links, v, thr)) for v in range(n))
    else:
        dists = [bfs(links, v, thr) for v in range(n)]
        for a, b in zip(ab[0::2], ab[1::2]):
            a -= 1
            b -= 1
            ans = min(ans, sum(d1 and d2 for d1, d2 in zip(dists[a], dists[b])))
    return ans


n, k, *ab = map(int, sys.stdin.buffer.read().split())
print(solve(n, k, ab))
### BUGGY CODE ###

H,W,D = map(int, input().strip().split(' '))
A = [list(map(int, input().strip().split(' '))) for _ in range(H)]

a2pos = [None]*(H*W+1)
for h in range(H):
  for w in range(W):
    a2pos[A[h][w]] = [h,w]

def dist(a,b):
  return abs(a[0]-b[0])+abs(a[1]-b[1])

a2dist = [None]*(H*W+1)
for i in range(1,(H*W)-D+1):
  a2dist[i] = dist(a2pos[i+D], a2pos[i])
  

q = int(input().strip())
for _ in range(q):
  l,r = map(int, input().strip().split(' '))
  print(sum(a2dist[l:r:D]))

### FIXED CODE ###

H,W,D = map(int, input().strip().split(' '))
A = [list(map(int, input().strip().split(' '))) for _ in range(H)]

a2pos = [None]*(H*W+1)
for h in range(H):
  for w in range(W):
    a2pos[A[h][w]] = [h,w]

def dist(a,b):
  return abs(a[0]-b[0])+abs(a[1]-b[1])

a2dist = [0]*(H*W+1)
for i in range(1,(H*W)-D+1):
  a2dist[i+D] = a2dist[i]+dist(a2pos[i],a2pos[i+D])
  
q = int(input().strip())
for _ in range(q):
  l,r = map(int, input().strip().split(' '))
  print(a2dist[r]-a2dist[l])
### BUGGY CODE ###

# coding: utf-8
S = input().split()
Q = int(input())

def pop(left, right, rev, f, c):
    left_ = left
    if rev == 1:
        if f == '1':
            left_ = [c] + left
        else:
            right.append(c)
    else:
        if f == '1':
            right.append(c)
        else:
            left_ = [c] + left
    return left_, right


left, right = [], []
rev = 1
for _ in range(Q):
    que = input().split()
    if que[0] == '1':
        rev *= -1
        continue
    if que[0] == '2':
        left, right = pop(left, right, rev, *que[1:])
print(''.join(left+S+right)[::rev])

### FIXED CODE ###

# coding: utf-8
S = input().split()
Q = int(input())

def pop(left, right, rev, f, c):
    if rev == 1:
        if f == '1':
            left.append(c)
        else:
            right.append(c)
    else:
        if f == '1':
            right.append(c)
        else:
            left.append(c)
    return left, right


left, right = [], []
rev = 1
for _ in range(Q):
    que = input().split()
    if que[0] == '1':
        rev *= -1
        continue
    if que[0] == '2':
        left, right = pop(left, right, rev, *que[1:])
print(''.join(left[::-1]+S+right)[::rev])
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC98 C

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

x = [1 if s[i] == 'W' else 0 for i in range(n)]
y = [1 if s[i] == 'E' else 0 for i in range(n)]

mi = float('inf')
for i in range(n):
    a = sum(x[:i])
    b = sum(y[i+1:])
    mi = min(mi,a+b)
print(mi)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC98 C

#累積和を用いる
from itertools import accumulate

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

x = [0]+[1 if s[i] == 'W' else 0 for i in range(n)]
y = [1 if s[i] == 'E' else 0 for i in range(n)] + [0]

mx = list(accumulate(x))
my = list(accumulate(y[::-1]))
my = my[::-1]
mi = float('inf')
for i in range(n+1):
    a = mx[i]
    b = my[i]
    mi = min(mi,a+b)
print(mi)
### BUGGY CODE ###

N = int(input())
A = sorted([int(a) for a in input().split()], reverse=True)
B = sorted([int(b) for b in input().split()], reverse=True)
C = sorted([int(c) for c in input().split()], reverse=True)
ans = 0

for i in range(N):
  for j in range(N):
    if A[i] >= B[j]:
      continue
    for k in range(N):
      if B[j] < C[k]:
        ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
A = sorted([int(a) for a in input().split()])
B = [int(b) for b in input().split()]
C = sorted([int(c) for c in input().split()])
ans = 0

import bisect
for i in range(N):
  b = B[i]
  end_A = bisect.bisect_left(A, b)
  start_C = bisect.bisect_right(C, b)
  ans += end_A * (N - start_C)

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

N=int(input())
L=[[0]*26 for _ in range(N)]
a=ord('a')
for i in range(N):
  s=input()
  for c in s:
    L[i][ord(c)-a]+=1
count = 0
for i in range(N-1):
  for j in range(i+1,N):
    if L[i] == L[j]:
      count+=1
print(count)

### FIXED CODE ###

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

n,k=map(int,input().split())
mod=998244353
S=set()
for _ in range(k):
  l,r=map(int,input().split())
  for i in range(l,r+1):
    S.add(i)
dp=[0 for _ in range(n+1)]
for i in S:
  dp[i]=1

for i in range(1,n+1):
  for j in S:
    if i-j<1:
        continue
    dp[i]+=dp[i-j]
print(dp[n-1]%mod)

### FIXED CODE ###

n,k=map(int,input().split())
mod=998244353
R=[]
for _ in range(k):
  l,r=map(int,input().split())
  R.append([l,r])

dp=[0 for _ in range(n+1)]
dp[1]=1
dpsum=[0 for _ in range(n+1)]
dpsum[1]=1
for i in range(2,n+1):
  for j in range(k):
    li=i-R[j][1]
    ri=i-R[j][0]
    if ri<0:
      continue
    li=max(li,1)
    dp[i]+=(dpsum[ri]-dpsum[li-1])%mod
  dpsum[i]=dpsum[i-1]+dp[i]
  dpsum[i]%=mod
print(dp[n]%mod)
### BUGGY CODE ###

N, M = map(int, input().split())
heights = list(map(int,input().split()))
win = []

for i in range(1, N + 1):
  win.append(i)

for i in range(M):
  x, y = map(int, input().split())
  if heights[x - 1] > heights[y - 1]:
    if y in win:
      win.remove(y)
  elif heights[x - 1] < heights[y - 1]:
    if x in win:
      win.remove(x)
  elif heights[x - 1] == heights[y - 1]:
    if x in win:
      win.remove(x)
    if y in win:
      win.remove(y)

print(len(win))

### FIXED CODE ###

N, M = map(int, input().split())
heights = list(map(int,input().split()))
lose = []

for i in range(M):
  x, y = map(int, input().split())
  if heights[x - 1] > heights[y - 1]:
    lose.append(y)
  elif heights[x - 1] < heights[y - 1]:
    lose.append(x)
  elif heights[x - 1] == heights[y - 1]:
    lose.append(y)
    lose.append(x)

print(N - len(list(set(lose))))
### BUGGY CODE ###

(n, m) = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse = True)

while m > 0:
    found = False
    for i in range(n-1):
        if a[i] < a[i+1]:
            a[i+1] = int(a[i+1] / 2)
            found = True
            break
    if not found:
        a[0] /= 2
    m -= 1
sum = 0
for a_i in a:
    sum += int(a_i)
print(sum)


### FIXED CODE ###

import math
import heapq

(n, m) = map(int, input().split())
a = []
for a_i in input().split():
    heapq.heappush(a, -1 * int(a_i))

for i in range(m):
    a_i = heapq.heappop(a)
    heapq.heappush(a, a_i / 2)

sum = 0
for a_i in a:
    sum += int(-1 * a_i)
print(sum)
### BUGGY CODE ###

s= input()
q= int(input())
inv = False
for i in range(q):
    p = input()
    if p[0]=='1':
        if inv:inv=False
        else:inv=True
    elif p[0]=='2':
        _,f,c= p.split()
        if f=='1':
            if inv:s = s+c
            else: s = c+s
        elif f=='2':
            if inv:s=c+s
            else:s = s + c
if inv:print(s[::-1])
else:print(s)

### FIXED CODE ###

from collections import deque
s= input()
q= int(input())
inv = False
head = deque()
tail = deque()
for i in range(q):
    p = input()
    if p[0]=='1':
        if inv:inv=False
        else:inv=True
    elif p[0]=='2':
        _,f,c= p.split()
        if f=='1':
            if inv:tail.append(c)
            else:head.appendleft(c)
        elif f=='2':
            if inv:head.appendleft(c)
            else:tail.append(c)
news = ''.join(head) + s + ''.join(tail)
if inv:print(news[::-1])
else:print(news)
### BUGGY CODE ###

# import math
# from collections import Counter

# N = int(input()) # 1行, 単数
# arg = list(map(int, input().split())) # 1行, 配列
# D = Counter(arg) # 出現数カウント

# print('Yes')
# print('No')
# print()


N = int(input()) # 1行, 単数

arg = list(map(int, input().split())) # 1行, 配列
m = 1

for A in arg:
  m = A * m

if m - 1000000000000000000 > 0:
  print('-1')
else:
  print(m)


### FIXED CODE ###

# import math
# from collections import Counter

# N = int(input()) # 1行, 単数
# arg = list(map(int, input().split())) # 1行, 配列
# D = Counter(arg) # 出現数カウント

# print('Yes')
# print('No')
# print()


N = int(input()) # 1行, 単数

arg = list(map(int, input().split())) # 1行, 配列
m = 1

if 0 in arg:
  print(0)
else:
  for A in arg:
    m = A * m
    if m > 1000000000000000000:
      m = -1
      break;
  print(m)
### BUGGY CODE ###

from operator import mul
from functools import reduce

[n,k] = map(int, input().split(' '))
A = list(map(int, input().split(' ')))

def hyoka(j,p,b_point):
  point = reduce(mul, A[j-k:j])
  if j == k:
    return point
  if b_point < point:
    print('Yes')
  else:
    print('No')
  return point
b_point = 0
for i,p in enumerate(A):
  if i+1 < k:
    continue
  result = hyoka(i+1,p,b_point)
  if result > 0:
  	b_point = result


### FIXED CODE ###

[n,k] = map(int, input().split(' '))
A = list(map(int, input().split(' ')))

for i in range(k,n):
  if A[i-k]<A[i]:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

n=int(input())
for i in range(n):
    if i==0:
        x,y=map(int,input().split())
    else:
        t,a=map(int,input().split())
        v=t
        w=a
        while t<x or a<y:
            v+=t
            w+=a
        x=v
        y=w
print(x+y)
        



### FIXED CODE ###

n=int(input())
x=1
y=1
for i in range(n):
    t,a=map(int,input().split())
    c=max(-(-x//t),-(-y//a))
    x=t*c
    y=a*c      
print(int(x+y))
### BUGGY CODE ###

N,Q = map(int,input().split())
X = [list(map(int,input().split())) for _ in range(N-1)]
Y = [list(map(int,input().split())) for _ in range(Q)]

con = [[] for _ in range(N)]
for i in range(N-1):
    con[X[i][0]-1]+=[X[i][1]-1]
    con[X[i][1]-1]+=[X[i][0]-1]

dif = [0]*N
for i in range(Q):
    dif[Y[i][0]-1] += Y[i][1]

root = [0]
while root:
    cur = root.pop()
    for i in con[cur]:
        dif[i] += dif[cur]
        con[i].remove(cur)
        root.append(i) 

print(*dif)

### FIXED CODE ###

import sys
input=sys.stdin.readline
def main():
    N,Q = map(int,input().split())
    X = [list(map(int,input().split())) for _ in range(N-1)]
    Y = [list(map(int,input().split())) for _ in range(Q)]

    con = [[] for _ in range(N)]
    for i in range(N-1):
        con[X[i][0]-1]+=[X[i][1]-1]
        con[X[i][1]-1]+=[X[i][0]-1]

    dif = [0]*N
    for i in range(Q):
        dif[Y[i][0]-1] += Y[i][1]

    root = [0]
    while root:
        cur = root.pop()
        for i in con[cur]:
            dif[i] += dif[cur]
            con[i].remove(cur)
            root.append(i) 
    print(*dif)

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

s=input()
n=int(s)
m=len(s)

if n<2019:
    print(0)
    exit()
dp=[]
for i in range(m+1):
    dp.append((n%(10**i))%2019)
def comb(n,m):
    import math
    if n-m<0:
        return 0
    return(math.factorial(n)//math.factorial(n-m)//math.factorial(m))
import collections
c=collections.Counter(dp)
ll=c.most_common()
ans=0
for i,j in ll:
    if j>=2:
        ans+=comb(j,2)
    else:
        break
print(ans)

### FIXED CODE ###

s=[int(j) for j in input()][::-1]
c=[0]*2019
tmp=0
c[0]+=1
t=1
import numpy as np
for i in s:
    tmp+=t*i
    c[tmp%2019]+=1
    t=t*10%2019
c=np.array(c)
ans=c*(c-1)//2
print(ans.sum())