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

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

N,mod=map(int,input().split())
EDGE=[list(map(int,input().split())) for i in range(N-1)]

#N=10**5
#mod=10**8
#import random
#EDGE=[[i,random.randint(1,i-1)] for i in range(2,N+1)]

EDGELIST=[[] for i in range(N+1)]
DPDICT=dict()

for x,y in EDGE:
    EDGELIST[x].append(y)
    EDGELIST[y].append(x)

for i in range(1,N+1):
    if len(EDGELIST)==1:
        DPDICT[(i,EDGELIST[i][0])]=2    


def SCORE(point):
    ANS=1
    for to in EDGELIST[point]:
        ANS=ANS*dp(to,point)%mod
    return ANS

def dp(x,y):
    if DPDICT.get((x,y))!=None:
        return DPDICT[(x,y)]

    ANS=1
    for to in EDGELIST[x]:
        if to==y:
            continue
        ANS=ANS*dp(to,x)%mod

    DPDICT[(x,y)]=ANS+1
    return ANS+1

for i in range(1,N+1):
    print(SCORE(i))


### FIXED CODE ###

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

N,mod=map(int,input().split())
EDGE=[list(map(int,input().split())) for i in range(N-1)]

if N==1:
    print(1)
    sys.exit()

EDGELIST=[[] for i in range(N+1)]
for x,y in EDGE:
    EDGELIST[x].append(y)
    EDGELIST[y].append(x)

SCORELIST=[[-1]*len(EDGELIST[i]) for i in range(N+1)]
PRODLIST=[[-1]*len(EDGELIST[i]) for i in range(N+1)]
PRODLIST_rev=[[-1]*len(EDGELIST[i]) for i in range(N+1)]
EDICT=dict()

for i in range(1,N+1):
    for j in range(len(EDGELIST[i])):
        EDICT[(i,EDGELIST[i][j])]=j

def dp(x,y):
    if SCORELIST[y][EDICT[(y,x)]]!=-1:
        return SCORELIST[y][EDICT[(y,x)]]

    ANS=1
    for to in EDGELIST[x]:
        if to==y:
            continue
        ANS=ANS*dp(to,x)%mod

    SCORELIST[y][EDICT[(y,x)]]=ANS+1   
    return ANS+1

def dp2(x,y):
    if PRODLIST[x][0]==-1:
        PRODLIST[x][0]=(SCORELIST[x][0])%mod
        for i in range(1,len(EDGELIST[x])):
            PRODLIST[x][i]=PRODLIST[x][i-1]*SCORELIST[x][i]%mod

        PRODLIST_rev[x][-1]=SCORELIST[x][-1]
        for i in range(len(EDGELIST[x])-2,-1,-1):
            PRODLIST_rev[x][i]=PRODLIST_rev[x][i+1]*SCORELIST[x][i]%mod

    if len(EDGELIST[x])==1:
        ANS=1
    elif EDICT[(x,y)]==0:
        ANS=PRODLIST_rev[x][1]
    elif EDICT[(x,y)]==len(EDGELIST[x])-1:
        ANS=PRODLIST[x][EDICT[(x,y)]-1]
    else:
        ANS=PRODLIST[x][EDICT[(x,y)]-1]*PRODLIST_rev[x][EDICT[(x,y)]+1]%mod

    SCORELIST[y][EDICT[(y,x)]]=ANS+1

for to in EDGELIST[1]:
    dp(to,1)

QUE=deque([1])
check=[0]*(N+1)

while QUE:
    x=QUE.pop()
    if check[x]==1:
        continue
    for to in EDGELIST[x]:
        if check[x]==0 or check[to]==0:
            dp2(x,to)
            QUE.append(to)
    check[x]=1

for i in range(1,N+1):
    print(PRODLIST[i][-1])
### BUGGY CODE ###

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

n_pears = 0
used_balls = []

for i in reversed(range(0, len(A))):
    if i % 1000 == 0:
        used_balls.sort()
        for n in used_balls:
            if i <= n:
                del used_balls[n:]
            break
        if i == n:
            continue
    if i in used_balls:
        continue
    for j in reversed(range(0, i)):
        if j in used_balls:
            continue
        if not ((A[i] + A[j]) & (A[i] + A[j] - 1)):
            n_pears += 1
            used_balls.append(j)
            break

print(n_pears)

### FIXED CODE ###

import math
from collections import Counter


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

n_pears = 0
counter = Counter(A)

for i in reversed(range(0, len(A))):
    if counter[A[i]] <= 0:
        continue
    counter[A[i]] -= 1
    Aj = 2 ** int(math.log2(A[i]) + 1) - A[i]
    if counter[Aj] > 0:
        n_pears += 1
        counter[Aj] -= 1

print(n_pears)
### BUGGY CODE ###

N,K = map(int,input().split())
P = [int(p) for p in input().split()]

E = []
for i in range(len(P)):
  E.append((1+P[i])/2)

Ex = []
for j in range(0,len(P)-K+1):
  Ex.append(sum(E[j:j+K]))

print(max(Ex))

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
from itertools import accumulate
pac = [0]+list(accumulate(p))
num = 0
for i in range(N-K+1):
    num = max(pac[i+K]-pac[i],num)
print((K+num)/2)
### BUGGY CODE ###

N, Q = [int(_) for _ in input().split()]
S = input()
l_r_list = [[int(_) for _ in input().split()] for _ in range(Q)]

AC_accumulation = [S[:j].count("AC") for j in range(1, N + 1)]

ans = []
for l, r in l_r_list:
    ans.append(str(AC_accumulation[r - 1] - AC_accumulation[l - 1]))

print("\n".join(ans))


### FIXED CODE ###

N, Q = [int(_) for _ in input().split()]
S = input()
l_r_list = [[int(_) for _ in input().split()] for _ in range(Q)]

AC_accumulation = [0]

for i in range(1, N):
    if S[i] == "C" and S[i - 1] == "A":
        AC_accumulation.append(AC_accumulation[-1] + 1)
    else:
        AC_accumulation.append(AC_accumulation[-1])


ans = []
for l, r in l_r_list:
    ans.append(str(AC_accumulation[r - 1] - AC_accumulation[l - 1]))

print("\n".join(ans))
### BUGGY CODE ###

from scipy.special import comb
n = int(input())
aa = list(map(int, input().split()))
list1 = []

for j in range(n):
  for i in range(j+1, n):
    list1.append([comb(aa[i], aa[j]), aa[i],aa[j]])
    
ma = max(list1, key= lambda x:x[0])
ans = sorted([ma[1], ma[2]], reverse = True)

print(*ans)

### FIXED CODE ###

n = int(input())
aa = sorted(list(map(int, input().split())))
list1 = []
ma = aa[-1]
for i in range(n):
  d = abs(aa[i]-(ma+1)//2)
  list1.append([d,i])
md = min(list1, key=lambda x:x[0])

print(ma, aa[md[1]])
### BUGGY CODE ###

from collections import Counter

N, K, *DC = map(int, open(0).read().split())

D = tuple(zip(*[iter(DC[:K * K])] * K))
C = tuple(zip(*[iter(DC[K * K:])] * N))

A = [Counter() for _ in range(3)]
for k in range(K):
    for i in range(N):
        for j in range(N):
            A[(i + j) % 3][k] += D[C[i][j] - 1][k]

ans = float("inf")
for i in range(K):
    for j in range(K):
        for k in range(K):
            if i == j or j == k or k == i:
                continue
            ans = min(ans, A[0][i] + A[1][j] + A[2][k])

print(ans)

### FIXED CODE ###


from collections import Counter

N, K, *DC = map(int, open(0).read().split())

D = tuple(zip(*[iter(DC[:K * K])] * K))
C = tuple(zip(*[iter(DC[K * K:])] * N))

A = [Counter() for _ in range(3)]
for k in range(K):
    for i in range(N):
        for j in range(N):
            A[(i + j) % 3][k] += D[C[i][j] - 1][k]

ans = float("inf")
for i in range(K):
    for j in range(K):
        for k in range(K):
            if i == j or j == k or k == i:
                continue
            ans = min(ans, A[0][i] + A[1][j] + A[2][k])

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

N=int(input())
st=list(input())
ans=[]
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            ans.append(st[i]+st[j]+st[k])
ans=set(ans)
print(len(ans))

### FIXED CODE ###

def main():
  N = int(input())
  S = list(map(int,input()))
  ans = 0
  for i in range(10):
    for j in range(10):
      for k in range(10):
        flg = False
        flg2 = False
        for x in range(N):
          if flg2:
            break
          if not flg:
            if S[x] == i:
              flg = True
          else:
            if S[x] == j:
              flg2 = True
              if k in S[x+1:]:
                ans +=1
  print(ans)
main()
### BUGGY CODE ###

from queue import Queue
from itertools import product
import numpy as np

NOT_VISITED = 0
SCHEDULED = 1
VISITED = 2

H, W = map(int, input().split())
S = np.zeros((H, W), dtype='U1')
for hi in range(H):
    raw = input()
    S[hi, :] = list(raw)

maxmove = np.zeros_like(S, dtype='int')

for hi, wi in product(range(H), range(W)):
    # hi, wiをスタート位置とする場合
    if S[hi, wi] == '#': continue

    # 必要な諸々を定義
    flag = np.zeros_like(S, dtype='int')
    flag[:] = NOT_VISITED
    flag[hi, wi] = VISITED
    nummove = np.zeros_like(S, dtype='int')
    queue = Queue()

    queue.put((hi, wi))
    while queue.empty() == False:
        hj, wj = queue.get()
        flag[hj, wj] = VISITED
        for neighbour in [(hj, wj-1), (hj, wj+1), (hj+1, wj), (hj-1, wj)]:
            if not (0 <= neighbour[0] < H and 0 <= neighbour[1] < W): continue
            if S[neighbour] == '#': continue
            if flag[neighbour] == NOT_VISITED:
                nummove[neighbour] = nummove[hj, wj] + 1
                queue.put(neighbour)
                flag[neighbour] = SCHEDULED
    
    maxmove[hi, wi] = np.max(nummove)

print(np.max(maxmove))


### FIXED CODE ###

# 幅優先探索
# YouTube解説を見てから (https://www.youtube.com/watch?v=1oLDDdWRu6Y&feature=youtu.be)

# queue.Queueよりも、collections.dequeの方が高速だった
# 前者を使うとTLEになっちゃった。。。

from queue import Queue
from collections import deque
from itertools import product
import numpy as np

H, W = map(int, input().split())
S = np.zeros((H, W), dtype='U1')
for hi in range(H):
    raw = input()
    S[hi, :] = list(raw)

maxmove = np.zeros_like(S, dtype='int')

for hi, wi in product(range(H), range(W)):
    # hi, wiをスタート位置とする場合
    if S[hi, wi] == '#': continue

    # 必要な諸々を定義
    # flag = np.zeros_like(S, dtype='int')
    # flag[:] = NOT_VISITED
    # flag[hi, wi] = VISITED
    VisitOrScheduled = np.zeros_like(S, dtype='bool')
    VisitOrScheduled[hi, wi] = True
    nummove = np.zeros_like(S, dtype='int')
    # queue = Queue()
    deq = deque()

    # queue.put((hi, wi))
    deq.append((hi, wi))
    # while queue.empty() == False:
    while True:
        try:
            # hj, wj = queue.get()
            hj, wj = deq.popleft()
        except IndexError:
            break
        # flag[hj, wj] = VISITED
        VisitOrScheduled[hj, wj] = True
        for neighbour in [(hj, wj-1), (hj, wj+1), (hj+1, wj), (hj-1, wj)]:
            if not (0 <= neighbour[0] < H and 0 <= neighbour[1] < W): continue
            if S[neighbour] == '#':
                continue
            # if flag[neighbour] == NOT_VISITED:
            if not VisitOrScheduled[neighbour]:
                nummove[neighbour] = nummove[hj, wj] + 1
                # queue.put(neighbour)
                deq.append(neighbour)
                # flag[neighbour] = SCHEDULED
                VisitOrScheduled[neighbour] = True
    
    maxmove[hi, wi] = np.max(nummove)

print(np.max(maxmove))
### BUGGY CODE ###

from collections import Counter
from functools import reduce
from operator import mul
from math import factorial

def make_divisors(n):
    divs = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divs.append(i)
            if i != n // i:
                divs.append(n//i)
    # divisors.sort()
    return divs

def prime_factorize(n):
  factors = {}
  for i in range(2,n+1):
    while n%i ==0:
      n /= i
      if i not in factors:
        factors[i] = 1
      else:
        factors[i] += 1
  return factors

N = int(input())
ans = 0
for div in make_divisors(factorial(N)):
  res = prime_factorize(div)
  if len(res) > 0:
    div_num = reduce(mul, [num+1 for num in res.values()])
    if div_num == 75: ans += 1
print(ans)

### FIXED CODE ###

from collections import defaultdict
from collections import Counter


def prime_factorization(divs, n):
    while n % 2 == 0:
        divs[2] += 1
        n //= 2

    i = 3
    while i <= int(n ** .5) + 1:
        while n % i == 0:
            divs[i] += 1
            n //= i
        i += 2
    if n != 1:
        divs[n] += 1

    return divs


def num(m):
    return sum([value if key >= m else 0 for key, value in cnt_divs.items()])


N = int(input())
divs = defaultdict(int)
for n in range(2, N + 1):
    divs = prime_factorization(divs, n)

cnt_divs = Counter(divs.values())

print(num(74) + \
      num(24) * (num(2) - 1) + \
      num(14) * (num(4) - 1) + \
      num(4) * (num(4) - 1) * (num(2) - 2) // 2)
### BUGGY CODE ###

import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))

n,k = m()

s = [[] for i in range(n)]

sss = [[Max,Max,Max] for i in range(n)]

for i in range(k):
    u,v = m()
    u -= 1
    v -= 1
    if v not in s[u]:
        s[u].append(v)

st,g = m()
st -= 1
g -= 1
co = Max

eee = [[s,0,st,0]]
eee = cl.deque(eee)
def bfs(x,nn,now,coun):
    global eee,sss,g,co
    if sss[now][nn] == Max:
        if nn == 0 and g == now:
            co = min(co,coun)
        else:
            sss[now][nn] = coun
            if nn == 2:
                nn = 0
                coun += 1
            else:
                nn += 1
            for i in x[now]:
                eee.append([x,nn,i,coun])
    else:
        if now == g and nn == 0:
            co = min(co,coun)

while eee:
    op = eee.popleft()
    bfs(op[0],op[1],op[2],op[3])

#dfs(s,0,g,0)
if co == Max:
    print(-1)
else:
    print(co)



### FIXED CODE ###

import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))

n,k = m()

s = [[] for i in range(n)]

sss = [[Max,Max,Max] for i in range(n)]

for i in range(k):
    u,v = m()
    u -= 1
    v -= 1
    if v not in s[u]:
        s[u].append(v)

st,g = m()
st -= 1
g -= 1
co = Max

eee = [[s,0,st,0]]
eee = cl.deque(eee)
def bfs(x,nn,now,coun):
    global eee,sss,g,co
    if sss[now][nn] == Max:
        if nn == 0 and g == now:
            co = min(co,coun)
        else:
            sss[now][nn] = coun
            if nn == 2:
                nn = 0
                coun += 1
            else:
                nn += 1
            for i in x[now]:
                eee.append([x,nn,i,coun])
    else:
        if now == g and nn == 0:
            co = min(co,coun)

while eee:
    op = eee.popleft()
    bfs(op[0],op[1],op[2],op[3])

#dfs(s,0,g,0)
if co == Max:
    print(-1)
else:
    print(co)
### BUGGY CODE ###

import heapq

S = input()
lenS = len(S)
T = input()
Si = {}
for i,s in enumerate(S):
  if s not in Si:
    Si[s] = []
  heapq.heappush(Si[s],i)

ans = 0
for t in T:
  if t not in Si:
    print(-1)
    exit()
  else:
    idx = -1
    while idx<ans:
      idx = heapq.heappop(Si[t])
      heapq.heappush(Si[t],idx+lenS)
    ans = idx
print(ans+1)

### FIXED CODE ###

import bisect

REPEAT_NUM = 10 ** 100

S = input()
T = input()
lenS = len(S)
lenT = len(T)

idxes_S = {}
for idx, s in enumerate(S):
    if s not in idxes_S:
        idxes_S[s] = []
    idxes_S[s].append(idx)

idx_s = -1
idx_t = 0
while idx_t < lenT and idx_s < lenS * REPEAT_NUM:
    if T[idx_t] not in idxes_S:
        print(-1)
        exit()
    else:
        tmp_idx = bisect.bisect(idxes_S[T[idx_t]], idx_s % lenS)
        if len(idxes_S[T[idx_t]]) == tmp_idx:
            idx_s += lenS - idx_s % lenS + idxes_S[T[idx_t]][0]
        else:
            idx_s += idxes_S[T[idx_t]][tmp_idx] - idx_s % lenS
        idx_t += 1

if idx_t == lenT:
    print(idx_s + 1)
else:
    print(-1)
### BUGGY CODE ###

n,k=map(int,input().split())
li=list(map(int,input().split()))
kai=[0]
for i in range(1,1001):
  kai.append(kai[i-1]+i)
ka=[0]+[kai[i]/i for i in range(1,len(kai))]

mx=0
for i in range(len(li)-k+1):
  x=li[i:i+k]
  ans=0
  for j in x:
    ans+=ka[j]
  mx=max(ans,mx)
print(mx)

### FIXED CODE ###

n,k=map(int,input().split())
li=list(map(int,input().split()))
kai=[0]
for i in range(1,1001):
  kai.append(kai[i-1]+i)
ka=[0]+[kai[i]/i for i in range(1,len(kai))]
lis=[ka[i] for i in li]

ans=sum(lis[:k])
mx=ans
for i in range(len(li)-k):
  ans-=lis[i]
  ans+=lis[i+k]
  mx=max(ans,mx)
print(mx)
### BUGGY CODE ###

N = int(input())
L = [int(a) for a in input().split()]

L.sort()

num_triangles = 0
for i in range(0, N - 2): # 0, 1, ..., N - 3
    for j in range(i + 1, N - 1): # i+1, i+2, ..., N-2
        for k in range(j + 1, N):
            if L[i] + L[j] <= L[k]:
                break
            else:
                num_triangles += 1

print(num_triangles)


### FIXED CODE ###

import bisect

N = int(input())
L = [int(a) for a in input().split()]

L.sort()

num_triangles = 0
for i in range(0, N - 2): # 0, 1, ..., N - 3
    for j in range(i + 1, N - 1): # i+1, i+2, ..., N-2
        num_triangles += bisect.bisect_left(L[j + 1:N], L[i] + L[j])

print(num_triangles)
### BUGGY CODE ###

h,w,m = map(int,input().split())
dh = [0]*(h+1)
dw = [0]*(w+1)
l=[[0 for i in range(w+1)] for j in range(h+1)]
for _ in range(m):
    x,y = map(int,input().split())
    dh[x]+=1
    dw[y]+=1
    l[x][y]=1
m = 0
for i in range(1,h+1):
    if dh[i]>m:
        m = dh[i]
        hi=i
c=m
m = 0
for i in range(1,w+1):
    d = dw[i]
    if l[hi][i]==1:
        d-=1
    m = max(m,d)
c+=m
print(c)

### FIXED CODE ###

from collections import defaultdict
h,w,m = map(int,input().split())
dh = defaultdict(int)
dw = defaultdict(int)
l=defaultdict(tuple)
for _ in range(m):
    x,y = map(int,input().split())
    dh[x]+=1
    dw[y]+=1
    l[(x,y)]=1
m = 0
for i in range(1,h+1):
    if dh[i]>m:
        m = dh[i]
        hi=i
c=m
m = 0
for i in range(1,w+1):
    d = dw[i]
    if l[(hi,i)]==1:
        d-=1
    m = max(m,d)
c+=m
m = 0
wi=0
for i in range(1,w+1):
    if dw[i]>m:
        m = dw[i]
        wi=i
c2=m
m = 0
for i in range(1,h+1):
    d = dh[i]
    if l[(i,wi)]==1:
        d-=1
    m = max(m,d)
c2+=m
print(max(c,c2))
### BUGGY CODE ###

import numpy as np
n,k=[int(i) for i in input().split()]
p=list((np.array([int(i) for i in input().split()])+1)/2)


ans=0
for i in range(n-k+1):
    sum_max=0
    for j in range(i,i+k):
        sum_max+=p[j]
    ans=max(ans,sum_max)
print(ans)


### FIXED CODE ###

n,k=[int(i) for i in input().split()]
p=[(int(i)+1)/2 for i in input().split()]

ans=0
sum_num=sum(p[:k])
for i in range(n-k+1):
    if i==0:
        sum_num = sum(p[:k])
    else:
        sum_num+=p[i+k-1]-p[i-1]
    ans=max(ans,sum_num)
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
def func(l,i):
    ret=l*(l+1)//2
    ret-=i*(i+1)//2
    ret-=(l-i-1)*(l-i)//2
    return ret
dn={a[i]:i+1 for i in range(n)}
from bisect import bisect_left,insort
space=[0,n+1]
ans=0
for i in range(1,n+1):
    t=dn[i]
    tl=bisect_left(space,t)
    l=space[tl-1]
    r=space[tl]
    lg=r-l-1
    ans+=func(lg,t-l-1)*i
    insort(space,t)
print(ans)



### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
dn={x:i for i,x in enumerate(p)}

#####segfunc#####
def segfunc(x, y):
    return x+y
#################

#####ide_ele#####
ide_ele = 0
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc=segfunc, ide_ele=ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

st=SegTree([0]*n)
ans=0

for k in range(1,n+1):
    i=dn[k]
    # idx=iを含み、区間和が0になる最長の区間を調べる。
    l,r=0,i
    while r-l>1:
        x=(l+r)//2
        if st.query(x,i+1)>0:
            l,r=x,r
        else:
            l,r=l,x
    l0=l if st.query(l,i+1)==0 else r
    l,r=i,n-1
    while r-l>1:
        x=(l+r)//2
        if st.query(i,x+1)>0:
            l,r=l,x
        else:
            l,r=x,r
    r0=r if st.query(i,r+1)==0 else l
    ans+=k*(i-l0+1)*(r0-i+1)
    st.update(i,1)
print(ans)
### BUGGY CODE ###

n=int(input())
d=list(map(int,input().split()))
if n>=24:
    print(0)
    exit()
if n==23:
    print(1)
op=2**n-1
ans=0
for i in range(op):
    t=[0]
    for j in range(n):
        if i&(2**j)>0:
            t.append(d[j])
        else:
            t.append(24-d[j])
    a=10000
    for p in range(1,1+n):
        for q in range(p):
            b=abs(t[p]-t[q])
            a=min(a,min(b,24-b))
    ans=max(ans,a)
print(ans)


### FIXED CODE ###

n=int(input())
d=list(map(int,input().split()))
if n>=24:
    print(0)
    exit()
if n>=22:
    t=[]
    d.append(0)
    d.sort()
    f=1
    for i in range(n):
        if d[i]==d[i+1]:
            f+=1
        else:
            if f>2:
                print(0)
                exit()
            f=1
    print(1)
    exit()

op=2**n-1
ans=0
for i in range(op):
    t=[0]
    for j in range(n):
        if i&(2**j)>0:
            t.append(d[j])
        else:
            t.append(24-d[j])
    a=10000
    for p in range(1,1+n):
        for q in range(p):
            b=abs(t[p]-t[q])
            a=min(a,min(b,24-b))
    ans=max(ans,a)
print(ans)
### BUGGY CODE ###

S = list(input())

ans = 0
tot = [str(0)]

for i in range(len(S)-1):
  for j in range(i,len(S)):
    if int(''.join(tot)) % 2019 == 0 and int(''.join(tot)) >= 2019:
      ans += 1
    tot = [str(0)]
    for k in range(i,j+1):
      tot.append(S[k])
print(ans)

### FIXED CODE ###

S = input()
mod = [0] * 2019
mod[0] = 1 
d = 1
n = 0
for i in reversed(S):
  n += int(i) * d
  n %= 2019
  d *= 10
  d %= 2019
  mod[n % 2019] += 1
ans = 0
for j in range(2019):
  ans += mod[j] * (mod[j] - 1) // 2
print(ans)