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

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

N = int(input())

P=set()
for _ in range(N - 1):
  a, b, c = map(int, input().split())
  P.add((c, a - 1, b - 1))

d, i, j = zip(*P)
G = csr_matrix((d, (i, j)),(N, N))

Q, K = map(int, input().split())
P = dijkstra(G, indices=K - 1, directed=False)
for _ in range(Q):
  x, y = map(int, input().split())
  print(int(P[x - 1] + P[y - 1]))

### FIXED CODE ###

from collections import deque

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

G = [[] * N for _ in range(N)]
for a, b, c in ABC:
  G[a - 1].append((b - 1, c))
  G[b - 1].append((a - 1, c))

D = [-1] * N
D[K - 1] = 0

q = deque()
q.append(K - 1)
while q:
  n = q.popleft()
  for i, c in G[n]:
    if D[i] < 0:
      q.append(i)
      D[i] = D[n] + c

for x, y in XY:
  print(D[x - 1] + D[y - 1])
### BUGGY CODE ###

#create date: 2020-07-25 09:13

import sys
stdin = sys.stdin
mod = 10**9+7

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n, m = na()
    a = list()
    for i in range(m):
        a.append(ni())

    dp = [0] * (10**5+1)
    dp[0] = 1
    if not 1 in a: dp[1] = 1
    for i in range(2, 10**5+1):
        if i in a:
            dp[i] = 0
        else:
            dp[i] = (dp[i-2] + dp[i-1]) % mod
    print(dp[n])

if __name__ == "__main__":
    main()

### FIXED CODE ###

#create date: 2020-07-25 09:13

import sys
stdin = sys.stdin
mod = 10**9+7

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n, m = na()
    a = [0] * (10**5+1)
    for i in range(m):
        st = ni()
        a[st] = 1

    dp = [0] * (10**5+1)
    dp[0] = 1
    if a[1] == 0: dp[1] = 1
    for i in range(2, n+1):
        if a[i] == 1:
            dp[i] = 0
        else:
            dp[i] = (dp[i-2] + dp[i-1]) % mod
    print(dp[n])

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

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

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

ans = 0
count = 0

for index_1, num_1 in enumerate(num_list):
  for index_2, num_2 in enumerate(num_list):
    if index_1 != index_2:
      if num_1 % num_2 != 0:
        count += 1
  
  if count == n - 1:
    ans += 1

  count = 0

print(ans)

### FIXED CODE ###

import collections
 
n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr)
s=set()
cnt=collections.Counter(arr)
 
for i in range(n):
 if arr[i] in s:
   continue
 if cnt[arr[i]]>=2:
   s.add(arr[i])
 for j in range(2,10**6//arr[i]+1):
   s.add(arr[i]*j)
ans=0
for i in range(n):
 if arr[i] in s:
   continue
 ans+=1
 
print(ans)
### BUGGY CODE ###

K = int(input())

queue = [i for i in range(1, 10)]

for i in range(K - 1):
    N = queue.pop(0)
    if N % 10 == 0:
        queue.append(N * 10)
        queue.append(N * 10 + 1)
    elif N % 10 == 9:
        queue.append(N * 10 + 8)
        queue.append(N * 10 + 9)
    else:
        queue.append(N * 10 + (N % 10 - 1))
        queue.append(N * 10 + N % 10)
        queue.append(N * 10 + (N % 10 + 1))
print(queue.pop(0))

### FIXED CODE ###

K = int(input())

queue = [i for i in range(1, 10)]

for i in range(K - 1):
    N = queue.pop(0)
    if i < K // 2:
        if N % 10 == 0:
            queue.append(N * 10)
            queue.append(N * 10 + 1)
        elif N % 10 == 9:
            queue.append(N * 10 + 8)
            queue.append(N * 10 + 9)
        else:
            queue.append(N * 10 + (N % 10 - 1))
            queue.append(N * 10 + N % 10)
            queue.append(N * 10 + (N % 10 + 1))

print(queue.pop(0))
### BUGGY CODE ###

N=int(input())
L=sorted(list(map(int,input().split())))
count=0
d2breakFlag=False
for d1 in range(N-2):
    for d2 in range(d1+1,N-1):
        for d3 in range(d2+1,N):
            if L[d1]+L[d2]>L[d3]:count+=1
            else:break
print(count)


### FIXED CODE ###

import bisect
N=int(input())
L=sorted(list(map(int,input().split())))
count=0
for d1 in range(N-2):
    for d2 in range(d1+1,N-1):
        m=bisect.bisect_left(L,L[d1]+L[d2])
        if m>d2+1:count+=m-(d2+1)
print(count)
### BUGGY CODE ###

n = int(input())
A = []
for i in range(n):
  A.append(int(input()))
  
for i in range(n):
  Ai = A[:]
  Ai.pop(i)
  print(max(Ai))


### FIXED CODE ###

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

sort = sorted(A)

max = sort[-1]
maxx = sort[-2]

for i in range(n):
  if max == A[i]:
    print(maxx)
  else:
    print(max)
### BUGGY CODE ###

import itertools
N, M, R = map(int, input().split())
rs = list(itertools.permutations(list(map(lambda x: int(x) - 1, input().split()))))
dist = [[10**9 for _ in range(N)] for _ in range(N)]
for _ in range(M):
    v1, v2, d = map(int, input().split())
    dist[v1-1][v2-1] = dist[v2-1][v1-1] = d
for i in range(N):
    dist[i][i] = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
ans = 10**9
for r in rs:
    t = 0
    for i in range(R-1):
        t += dist[r[i]][r[i+1]]
        if t > 10**9:
            break
    ans = min(t, ans)
print(ans)

### FIXED CODE ###

from itertools import permutations
N, M, R = map(int, input().split())
rs = map(lambda x: int(x) - 1, input().split())
dist = [[10**9 for _ in range(N)] for _ in range(N)]
for _ in range(M):
    v1, v2, d = map(int, input().split())
    dist[v1-1][v2-1] = dist[v2-1][v1-1] = d
for i in range(N):
    dist[i][i] = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
ans = 10**9
for r in permutations(rs):
    t = 0
    for i in range(R-1):
        t += dist[r[i]][r[i+1]]
        if t > 10**9:
            break
    ans = min(t, ans)
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
inf=[]
pre=[[] for _ in range(n)]
for _ in range(m):
    p,y=map(int,input().split())
    pre[p-1].append(y)
    inf.append([p,y])
for key,lis in enumerate(pre): pre[key]=sorted(lis)
for i in inf: print("{:06}{:06}".format(i[0],1+pre[i[0]-1].index(i[1])))

### FIXED CODE ###

n,m=map(int,input().split())
pre=[[] for _ in range(n)]
for _ in range(m):
    p,y=map(int,input().split())
    pre[p-1].append([y,_,p])
for p in range(n):
    pre[p].sort(key=lambda x:x[0])
    for i in range(len(pre[p])):
        pre[p][i].append(i)
lis=[]
for i in pre:
    for j in i:
        lis.append(j)
lis.sort(key=lambda x:x[1])
for i in lis: print("{:06}{:06}".format(i[2],i[3]+1))
### BUGGY CODE ###

N, M = (int(i) for i in input().split(' '))
ten = [i+1 for i in range(N)]
H = [int(i) for i in input().split(' ')]
dic = {}
for i in range(len(H)):
    list_item = H[i]
    dic[i+1] = list_item
for i in range(M):
    x, y = (int(a) for a in input().split(' '))
    if dic[x] >= dic[y]:
        if y in ten:
            ten.remove(y)
    if dic[y] >= dic[x]:
        if x in ten:
            ten.remove(x)
print(len(ten))

### FIXED CODE ###

n,m=map(int,input().split())
arr=[0]+list(map(int,input().split()))
g=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
ans=0
for v in range(1,n+1):
  for u in g[v]:
    if arr[u]>=arr[v]:
      break
  else:
    ans+=1
print(ans)
### BUGGY CODE ###

import sys
import bisect
from collections import deque
sys.setrecursionlimit(4100000)
input = sys.stdin.readline



def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)
    dp = [[A[0]] for _ in range(N)]
    B = [[A[0]] for _ in range(N)]
    dist = [-1]*N
    dist[0] = 0
    queue = deque()
    queue.append([0,-1])
    while queue:
        Q = queue.popleft()
        now, pre = Q
        d = dist[now]
        for i in edge[now]:
            if dist[i] > -1:
                continue
            dist[i] = d + 1
            queue.append((i,now))
            B[i] = B[now] + [A[i]]
            dp[i] = dp[now].copy()
            if B[i][-1] > dp[i][-1]:
                dp[i].append(B[i][-1])
            else:
                dp[i][bisect.bisect_left(dp[i], B[i][-1])] = B[i][-1]

    for i in range(N):
        print(len(dp[i]))

    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import bisect
from collections import deque
sys.setrecursionlimit(4100000)
input = sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)

    ans = [0] * (N + 1)
    LIS = [-1]
    
    def dfs(v, p = N):
        if A[v] > LIS[-1]:
            LIS.append(A[v])
            ans[v] = ans[p] + 1
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS.pop()
        else:
            ans[v] = ans[p]
            idx = bisect.bisect_left(LIS, A[v])
            old = LIS[idx]
            LIS[idx] = A[v]
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS[idx] = old
    dfs(0)
    for i in range(N):
        print(ans[i])

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


#通るかな？
def 解():
    import numpy as np
    import sys
    input = sys.stdin.readline

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

    S = input()
    dS = {}
    for i in range(1,N+1):
        s = S[i-1]
        if s in dS:
            dS[s].add(i)
        else:
            dS[s]={i}
    #aM = [1]*(N+2)
    #aM = {i:1 for i in range(N+2)}
    aM = np.array([1]*(N+2))

    for _ in range(Q):
        t,d = input().split()
        if t in dS:
            if d == "R":
                for i in dS[t]:
                    if aM[i]:
                        aM[i+1] += aM[i]
                        aM[i] = 0
            else:
                for i in dS[t]:
                    if aM[i]:
                        aM[i-1] += aM[i]
                        aM[i] = 0

    #print(sum(aM[i] for i in range(1,N+1)))
    print(sum(aM[1:N+1]))
解()


### FIXED CODE ###

#こうけ？
def 解():
    import sys
    input = sys.stdin.readline
    N,Q = [int(_) for _ in input().split()]
    S = " " + input() + " "
    aC = [[ _.rstrip() for _ in  _.split()] for _ in sys.stdin.readlines()]
    iL = 0
    iR = N+1
    for t,d in aC[::-1]:
        if t == S[iL+1] and d == "L" and iL < N+1:
                iL += 1
        elif t == S[iL] and d == "R" and 0 < iL:
                iL -= 1

        if t == S[iR-1] and d == "R" and 0 < iR:
                iR -= 1
        elif t == S[iR] and d == "L" and  iR < N+1:
                iR += 1
    if iL < iR:
        print(iR-iL-1)
    else:
        print(0)
解()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

(n, k), s = map(int, input().split()), list(map(lambda x: (int(x) + 1) / 2, input().split()))
print(f'{max([sum(s[i:i+k]) for i in range(n - k + 1)]):.10f}')

### FIXED CODE ###

import sys
input = sys.stdin.readline

(n, k), s, res, sm = map(int, input().split()), list(map(lambda x: (int(x) + 1) / 2, input().split())), 0, 0
for i in range(n):
	if i < k: sm += s[i]
	else: sm += s[i]; sm -= s[i-k]
	res = max(res, sm)
print(f'{res:.10f}')
# print(f'{max([sum(s[i:i+k]) for i in range(n - k + 1)]):.10f}')
### BUGGY CODE ###

# -*- coding utf-8 -*-

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

counts = [0] if S[0] == '0' else []
s = '1' if S[0] == '1' else '0'
c = 0
for i in range(N):
    if S[i] != s:
        counts.append(c)
        c = 0
        if s == '1':
            s = '0'
        else:
            s = '1'
    c += 1
counts.append(c)

ans = 0
for i in range(len(counts)):
    if i % 2 == 1:
        continue
    ans = max(ans, sum(counts[i: i + 2 * K + 1]))
print(ans)



### FIXED CODE ###

# -*- coding utf-8 -*-

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

counts = [0] if S[0] == '0' else []
s = '1' if S[0] == '1' else '0'
c = 0
for i in range(N):
    if S[i] != s:
        counts.append(c)
        c = 0
        if s == '1':
            s = '0'
        else:
            s = '1'
    c += 1
counts.append(c)

ans = 0
cumsum = [0] * (len(counts) + 1)
for i in range(len(counts)):
    cumsum[i + 1] = cumsum[i] + counts[i]
for i in range(len(counts)):
    if i % 2 == 1:
        continue
    # ans = max(ans, sum(counts[i: i + 2 * K + 1]))
    r = min(i + 2 * K + 1, len(counts))
    l = i
    if r == l:
        ans = max(ans, counts[i])
    else:
        ans = max(ans, cumsum[r] - cumsum[l])
    # ans = max(ans, cumsum[r] - cumsum[l])
    # print(l, r, cumsum[r] - cumsum[l])
print(ans)
### BUGGY CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


#隣接リスト 1-order
def make_adjlist_d(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


#nCr
def cmb(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


def main():
    N = NI()
    A = NLI()
    A = sorted(A)
    hurui = [1] * len(A)
    prev = 0
    for i, a in enumerate(A):
        if a == prev:
            hurui[i-1] = 0
            hurui[i] = 0
            prev = a
            continue
        if i == len(A)-1:
            prev = a
            continue
        if hurui[i] == 0:
            prev = a
            continue
        for j, b in enumerate(A[i+1:]):
            if hurui[i+1+j]==0:
                prev = a
                continue
            if b % a == 0:
                hurui[i+1+j] = 0
            prev = a
    print(sum(hurui))



if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


#隣接リスト 1-order
def make_adjlist_d(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


#nCr
def cmb(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


def main():
    N = NI()
    A = NLI()
    A = sorted(A)

    ma = A[-1]
    hurui = [0] * (ma + 10)
    for a in A:
        if hurui[a] == 0:
            hurui[a] = 1
        else:
            hurui[a] = 10

    for a in A:
        if hurui[a] == 0:
            continue

        for i in range(a*2, ma+10, a):
            hurui[i] = 0

    print(hurui.count(1))



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

import sys,random
input = sys.stdin.readline


def main():
    n = int(input())
    
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))

    if n <= 10000:
        p = 0
        q = 0
        for eA,eB in zip(a,b):
            p = (p+eA)<<30
            q = (q+eB)<<30
        p = p>>30
        q = q>>30


        for k in range(n):
            hyp = b[0]^a[k]
            judge = p^q
            if (judge^((judge>>30)<<30)) == hyp and (judge^((judge>>60)<<60))>>30 == hyp:
                print(k,hyp)
            q = (q>>30) + (b[n-1-k]<<(30*(n-1)))
    else:
        for k in range(n):
            hyp = b[0]^a[k]
            judge = True
            for _ in [0]*500:
                w = random.randrange(n)
                if b[w] != a[(w+k)%n]^hyp:
                    judge = False
                    break
            if judge:
                print(k,hyp)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

#Z[i]:length of the longest list starting from S[i] which is also a prefix of S
def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg


n = int(input())
a = tuple(map(int,input().split()))
b = tuple(map(int,input().split()))


BAA = []
for i in range(n-1):
    BAA.append(b[i]^b[i+1])
BAA.append(b[0]^b[-1])

BAA.append(-1)

for i in range(n-1):
    BAA.append(a[i]^a[i+1])
BAA.append(a[0]^a[-1])
for i in range(n-1):
    BAA.append(a[i]^a[i+1])
BAA.append(a[0]^a[-1])

z = Z_algorithm(BAA)

for k in range(n):
    if z[n+k+1] >= n:
        print(k,b[0]^a[k])
### BUGGY CODE ###

N = int(input())
alist = [int(input()) for i in range(N)]
### 三角形が成立しない場合を数える
MOD = 998244353
asum = [0]
for i in range(N):
    asum += [asum[-1] + alist[i]]
S = asum[-1]
Sharf = S / 2

tbsize = int(Sharf//1)+1
#dptableA[i番目までは振り分けた][Rの合計] -> そこからR>=S/2となる数
dptableA = [{} for i in range(N+1)]
#dptableB[i番目までは振り分けた][Rの合計] -> そこからR=G=S/2, B=0となる数
dptableB = [{} for i in range(N+1)]

def ddp(cur_N, R): #(retA: R>=S/2となる数, retB: R=G=S/2,B=0の数)を返す
    if R in dptableA[cur_N]: #DPテーブルにある
        return dptableA[cur_N][R], dptableB[cur_N][R]
    if cur_N == N: #末端
        retA = 1 if R >= Sharf else 0
        retB = 1 if R == Sharf else 0
        return retA, retB
    if R >= Sharf: #R>=S/2はこれ以降のパターン全てR>=S/2
        #となるので残りの要素をRGBどこに割り振っても良い
        retA = pow(3, N-cur_N, MOD)
        retB = 1 if R == Sharf else 0 #特にR=S/2の時はR=G=S/2にできる
        return retA, retB
    if asum[cur_N] - R > Sharf: #Rに入れないものがS/2を超える
        return 0, 0 #どう頑張ってもR >= S/2を実現できない
    
    #そうではない場合は計算が必要
    ai = alist[cur_N]
    #aiをRGBのどれかに振り分ける
    retA_R, retB_R = ddp(cur_N+1, R+ai) #Rに振り分けた場合
    retA_GB, retB_GB = ddp(cur_N+1,R) #Rに入れなかった場合
    retA_GB = retA_GB * 2 %MOD #GBで2通りあるので2倍
    retA = (retA_R + retA_GB) % MOD
    retB = (retB_R + retB_GB) % MOD
    dptableA[cur_N][R] = retA
    dptableB[cur_N][R] = retB
    return retA, retB

retA, retB = ddp(0,0)
#全体 - (ある辺がS/2以上) + (2辺がS/2)
ans = (pow(3, N, MOD) - retA*3 + retB*3) % MOD
print(ans)

### FIXED CODE ###

N = int(input())
alist = [int(input()) for i in range(N)]
import numpy as np
### 三角形が成立しない場合を数える
alist.sort(reverse=False) #大きい方からチェックするとS/2に早く到達しやすい
MOD = 998244353
asum = [0]
for i in range(N):
    asum += [asum[-1] + alist[i]]
S = asum[-1]
Sharf = S / 2

#dptableA[i番目までは振り分けた][Rの合計] -> そこからR>=S/2となる数
dptableA = np.zeros((N+1, S+1), dtype=np.int) #[[0 for i in range(S+1)] for j in range(N+1)]
dptableA[N, int(np.ceil(Sharf)):] = 1
#dptableB[i番目までは振り分けた][Rの合計] -> そこからR=G=S/2, B=0となる数
dptableB = np.zeros((N+1, S+1), dtype=np.int) #[[0 for i in range(S+1)] for j in range(N+1)]
if S %2 == 0:
    dptableB[N, int(Sharf)] = 1 

#dpの計算をまとめて行う
for i in range(N, 0, -1): #後ろから見ていく
    n = i - 1
    an = alist[n]
    asn = asum[n]
    dptableA[n, 0:asn+1] = (2*dptableA[n+1, 0:asn+1] + dptableA[n+1, an:an+asn+1])%MOD
    #dptableA[n] = [(2*dptableA[n+1][k]+dptableA[n+1][k+alist[n]]) % MOD for k in range(asum[n]+1)]
    dptableB[n, 0:asn+1] = (dptableB[n+1, 0:asn+1] + dptableB[n+1, an:an+asn+1])%MOD
    #dptableB[n] = [(dptableB[n+1][k]+dptableB[n+1][k+alist[n]]) %MOD for k in range(asum[n]+1)]
retA, retB = dptableA[0,0], dptableB[0,0]
#全体 - (ある辺がS/2以上) + (2辺がS/2)
ans = (pow(3, N, MOD) - retA*3 + retB*3) % MOD
print(ans)
### BUGGY CODE ###


s=input()

mod=2019
tc=[0]*2019

lens=len(s)
#tim=int(s[lens-1])
#tc[tim]+=1
#for i in range(len(s)-1,-1,-1):
#    print(i,(10*tim+int(s[i]))%mod)    
#    ti=(10*tim+int(s[i]))%mod
#    tc[ti]+=1
#    tim=ti

tc[0]=1
for i in range(len(s)-1,-1,-1):
    ti=int(s[i:lens])%mod
    tc[ti]+=1
#    print(i,s[i:lens],ti,tc[ti])    
    
tsum=0
for i in tc:
    tsum+=(i*(i-1))//2
    
print(tsum)


### FIXED CODE ###

s=input()

mod=2019
tc=[0]*2019

lens=len(s)

tc[0]=1
tim=0
p10=1
for i in range(len(s)-1,-1,-1):
    ti=(tim+int(s[i])*p10)%mod
    tc[ti]+=1
#    print(i,(10*tim+int(s[i]))%mod,ti,tc[ti])    
    tim=ti
    p10=p10*10%mod

#tc[0]=1
#for i in range(len(s)-1,-1,-1):
#    ti=int(s[i:lens])%mod
#    tc[ti]+=1
#    print(i,s[i:lens],ti,tc[ti])    
    
tsum=0
for i in tc:
    tsum+=(i*(i-1))//2
    
print(tsum)
### BUGGY CODE ###

def change_num(tmp, i):
    if tmp[i] == "0":
        return int(tmp, 2)+pow(2, N-i-1)
    else:
        return int(tmp, 2)-pow(2, N-i-1)


def popcount(num):
    tmp1 = bin(num)
    tmp2 = tmp1[2:]
    return tmp2.count("1")


N = int(input())
X = input()
flag = 0

for i in range(N):
    tmp = change_num(X, i)
    # num1 = str(tmp).count("1")
    num1 = popcount(tmp)
    while tmp > 0:
        # print(f"tmp={tmp},num1={num1}")
        tmp = tmp % num1
        num1 = popcount(tmp)
        flag += 1
    print(flag)
    flag = 0

### FIXED CODE ###

n=int(input())
x=input()
t=int(x,2)
c=x.count('1')
a=t%-~c
b=0 if c<2 else t%~-c
for i in range(n):
  if int(x[i]):
    if c<2: print(0); continue
    else: t=(b-pow(2,n-i-1,c-1))%~-c
  else: t=(a+pow(2,n-i-1,c+1))%-~c
  z=1
  while t:
    d=bin(t).count('1')
    t%=d
    z+=1
  print(z)
### BUGGY CODE ###

N = int(input())
s = [0]*N
ans = 0
p = []
for i in range(N):
    s[i] = sorted(input())
    k = s[i]
    ans += p.count(k)
    p.append(k)

print(ans)

### FIXED CODE ###

N = int(input())
s = [0]*N
p = {}
ans = 0
for i in range(N):
    s[i] = "".join(sorted(input()))
    if s[i] in p:
        ans += p[s[i]]
        p[s[i]] += 1
    else:
        p[s[i]] = 1

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

n = int(input())
XYP = [tuple(map(int, input().split())) for i in range(n)]
X = [x for x, y, p in XYP]
Y = [y for x, y, p in XYP]
P = [p for x, y, p in XYP]

DX = [[0] * n for s in range(2**n)]
DY = [[0] * n for s in range(2**n)]
for s in range(2**n):
    for i in range(n):
        DX[s][i] = abs(X[i]) * P[i]
        DY[s][i] = abs(Y[i]) * P[i]
        for j in range(n):
            if s & (1 << j):
                DX[s][i] = min(DX[s][i], abs(X[i] - X[j]) * P[i])
                DY[s][i] = min(DY[s][i], abs(Y[i] - Y[j]) * P[i])

A = [10**20] * (n + 1)
for s in range(3**n):
    tmp = s
    c, sx, sy = 0, 0, 0
    i = 0
    while tmp:
        if tmp % 3 == 1:
            sx += 2**i
            c += 1
        if tmp % 3 == 2:
            sy += 2**i
            c += 1
        tmp //= 3
        i += 1
    A[c] = min(A[c], sum(min(DX[sx][i], DY[sy][i]) for i in range(n)))
print(*A, sep="\n")


### FIXED CODE ###

n = int(input())
XYP = [tuple(map(int, input().split())) for i in range(n)]
X = [x for x, y, p in XYP]
Y = [y for x, y, p in XYP]
P = [p for x, y, p in XYP]
pow2 = [2**i for i in range(n + 1)]

DX = [[0] * n for s in range(pow2[n])]
DY = [[0] * n for s in range(pow2[n])]
for s in range(1 << n):
    for i in range(n):
        DX[s][i] = abs(X[i]) * P[i]
        DY[s][i] = abs(Y[i]) * P[i]
        for j in range(n):
            if s & (1 << j):
                DX[s][i] = min(DX[s][i], abs(X[i] - X[j]) * P[i])
                DY[s][i] = min(DY[s][i], abs(Y[i] - Y[j]) * P[i])

BC = [bin(s).count("1") for s in range(pow2[n])]

A = [10**20] * (n + 1)
for sx in range(pow2[n]):
    rx = (pow2[n] - 1) ^ sx
    sy = rx
    for _ in range(pow2[n - BC[sx]]):
        sy = (sy - 1) & rx
        d = 0
        for i in range(n):
            d += min(DX[sx][i], DY[sy][i])
        c = BC[sx] + BC[sy]
        A[c] = min(A[c], d)
print(*A, sep="\n")