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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・部分木の中で操作を行った場合の、残りdepth和の最小値と最大値を持ってdp
・補助的にコマの個数も持つ
・最大値：ただのdepthの和
・最小値：一番負担の大きな木から他の部分木を引いていった場合だが…
・最小値＋最大値から全部の最大値の和を引く形で更新
"""

N = int(readline())
S = readline().rstrip()
m = map(int,read().split())
AB = zip(m,m)

INF = 10**18

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

def solve_rooted(root):
    parent = [0] * (N+1)
    ts = []
    stack = [root]
    while stack:
        x = stack.pop()
        ts.append(x)
        for y in graph[x]:
            if y == parent[x]:
                continue
            parent[y] = x
            stack.append(y)
    max_dep = [0]*(N+1)
    min_dep = [0]*(N+1)
    cnt = [0] * (N+1)
    for i,x in enumerate(S,1):
        cnt[i]=x-ord('0')
    for v in ts[::-1]:
        p = parent[v]
        max_dep_sum = 0
        x = 0
        for c in graph[v]:
            if c==p:
                continue
            cnt[v] += cnt[c]
            d1 = max_dep[c]; d2 = min_dep[c]
            d1 += cnt[c]; d2 += cnt[c]
            max_dep_sum += d1
            if x<d1+d2:
                x=d1+d2
        max_dep[v] = max_dep_sum
        x -= max_dep_sum
        if x<0:
            x=max_dep_sum&1
        min_dep[v] = x
    if min_dep[root]:
        return INF
    return max_dep[root]//2

answer = min(solve_rooted(v) for v in range(1,N+1))
if answer == INF:
    answer = -1
print(answer)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・部分木の中で操作を行った場合の、残りdepth和の最小値と最大値を持ってdp
・補助的にコマの個数も持つ
・最大値：ただのdepthの和
・最小値：一番負担の大きな木から他の部分木を引いていった場合だが…
・最小値＋最大値から全部の最大値の和を引く形で更新
"""

N = int(readline())
S = readline().rstrip()
m = map(int,read().split())
AB = zip(m,m)

INF = 10**18

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

def solve_rooted(root):
    parent = [0] * (N+1)
    ts = []
    stack = [root]
    while stack:
        x = stack.pop()
        ts.append(x)
        for y in graph[x]:
            if y == parent[x]:
                continue
            parent[y] = x
            stack.append(y)
    max_dep = [0]*(N+1)
    min_dep = [0]*(N+1)
    cnt = [0] * (N+1)
    for i,x in enumerate(S,1):
        cnt[i]=x-ord('0')
    for v in ts[::-1]:
        p = parent[v]
        max_dep_sum = 0
        x = 0
        for c in graph[v]:
            if c==p:
                continue
            cnt[v] += cnt[c]
            d1 = max_dep[c]; d2 = min_dep[c]
            d1 += cnt[c]; d2 += cnt[c]
            max_dep_sum += d1
            if x<d1+d2:
                x=d1+d2
        max_dep[v] = max_dep_sum
        x -= max_dep_sum
        if x<0:
            x=max_dep_sum&1
        min_dep[v] = x
    if min_dep[root]:
        return INF
    return max_dep[root]//2

answer = min(solve_rooted(v) for v in range(1,N+1))
if answer == INF:
    answer = -1
print(answer)
### BUGGY CODE ###

a = input()
while 1:
    if 'ST' in a:
        a = a[:a.index('ST')] + a[a.index('ST')+2:]
    else:
        break
print(len(a))


### FIXED CODE ###

a = list(input())

n = 0
res = 0
for x in a:
    if x == 'T':
        if n == 0:
            res += 1
        elif n > 0:
            n -= 1
    elif x == 'S':
        n += 1
res += n

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

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    S = [input() for i in range(N)]
    set_S = list(set(S))
    cnt = 0
    ll = []
    for s in set_S:
        s_num = S.count(s)
        if cnt < s_num:
            cnt = s_num
            ll = [s]
        elif cnt == s_num:
            ll.append(s)
        elif cnt > s_num:
            pass

    ll.sort()
    for l in ll:
        print(l,end="")


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    import sys
    import collections
    input = sys.stdin.readline
    N = int(input())
    S = [input() for i in range(N)]
    c = collections.Counter(S)
    max_num = c.most_common(1)[0][1]
    ss = [cc[0] for cc in c.most_common() if cc[1] == max_num]
    ss.sort()
    for s in ss:
        print(s,end="")

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

def diameter(N, E):#diamete of a tree
    V = [-1]*N
    V[0] = 0
    q = [0]
    while q:
        v = q.pop(0)
        for w in E[v]:
            if V[w] == -1:
                V[w] = V[v] + 1
                q.append(w)
    s = V.index( max(V))
    p = [s]
    W = [-1]*N
    W[s] = 0
    while p:
        v = p.pop(0)
        for w in E[v]:
            if W[w] == -1:
                W[w] = W[v] + 1
                p.append(w)
    return max(W)

N = int( input())
E = [ [] for _ in range(N)]
for _ in range(N-1):
    a, b = map( int, input().split())
    a, b = a-1, b-1
    E[a].append(b)
    E[b].append(a)
ans = "First"
if diameter(N, E)%3 == 1:
    ans = "Second"
print( ans)

### FIXED CODE ###

from collections import deque
def diameter(N, E):#diamete of a tree
    V = [-1]*N
    V[0] = 0
    q = deque([0])
    s = 0
    while q:
        v = q.popleft()
        for w in E[v]:
            if V[w] == -1:
                s = w
                V[w] = V[v] + 1
                q.append(w)
    # s = V.index( max(V))
    p = deque([s])
    W = [-1]*N
    W[s] = 0
    while p:
        v = p.popleft()
        for w in E[v]:
            if W[w] == -1:
                W[w] = W[v] + 1
                p.append(w)
    return max(W)

N = int( input())
E = [ [] for _ in range(N)]
for _ in range(N-1):
    a, b = map( int, input().split())
    a, b = a-1, b-1
    E[a].append(b)
    E[b].append(a)
ans = "First"
if diameter(N, E)%3 == 1:
    ans = "Second"
print( ans)
### BUGGY CODE ###

if __name__ == '__main__':
    N, M = map(int, input().split())

    LR = [list(map(int, input().split())) for i in range(M)]

    LR1 = LR[0]
    L1 = LR1[0]
    R1 = LR1[1]

    my_list = range(L1, R1+1)

    for tmp_LR in LR[1::]:
        tmp_L = tmp_LR[0]
        tmp_R = tmp_LR[1]

        my_list = [e for e in my_list if e >= tmp_L and e <= tmp_R]

    answer = len(my_list)
    print(answer)


### FIXED CODE ###

if __name__ == '__main__':
    N, M = map(int, input().split())

    LR = [list(map(int, input().split())) for i in range(M)]

    LR1 = LR[0]
    maxL = LR1[0]
    minR = LR1[1]

    for tmp_LR in LR[1::]:
        tmp_L = tmp_LR[0]
        tmp_R = tmp_LR[1]

        if tmp_L >= maxL:
            maxL = tmp_L

        if tmp_R <= minR:
            minR = tmp_R

    my_list = range(maxL, minR + 1)

    answer = len(my_list)
    print(answer)
### BUGGY CODE ###

N = input()
n = len(N)
dp = [[0,0] for _ in range(n)]
dp[0][0] = int(N[0])
dp[0][1] = 11-int(N[0])
for i in range(n-1):
    dp[i+1][0] = min(dp[i][0]+int(N[i+1]), dp[i][1]+int(N[i+1]))
    dp[i+1][1] = min(dp[i][0]+11-int(N[i+1]), dp[i][1]+9-int(N[i+1]))
print(min(dp[n-1][0],dp[n-1][1]))

### FIXED CODE ###

# import time
N = input()
n = len(N)
# t1 = time.time()
# ぴったり払う:a 余分に払う:b
a = int(N[0])
b = 11-int(N[0])
# t2 = time.time()
for i in range(n-1):
    a1 = min(a+int(N[i+1]), b+int(N[i+1]))
    b1 = min(a+11-int(N[i+1]), b+9-int(N[i+1]))
    a = a1
    b = b1
print(min(a,b))
# t3 = time.time()

# print(t2-t1,t3-t2)
### BUGGY CODE ###

def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]

    def calc(x):#xは数字
        if x==0:
            return 0
        xn=x
        x=bin(x)[2:]
        cnt=sum(list(map(int,list(x))))
        if xn%cnt==0:
            return 1
        else:
            return calc(xn%cnt)+1
    
    n=int(input())    
    x=input()
    cnt=sum(list(map(int,list(x))))
    x=int(x,2)
    ans=[]
    for i in range(n):
        if x>>i&1:
            ans.append(calc(x-2**i))
        else:
            ans.append(calc(x+2**i))
    print(*ans[::-1],sep='\n')

if __name__ == '__main__':
    resolve()

### FIXED CODE ###

def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]

    def popcount(n):
        c=format(n,'b').count('1')
        if c!=0:
            return n%c
        else:
            return 0
    def f(n):
        count=0
        while n>0:
            n=popcount(n)
            count+=1
        return count
        
    n=int(input())    
    x=input()
    cnt=x.count('1')
    x10=int(x,2)
    ans=[]
    a=x10%(cnt+1)
    if cnt==1:
        b=0
    else:
        b=x10%(cnt-1)
    for i in range(n):
        if x[i]=='1' and cnt==1:
            print(0)
            continue
        elif x[i]=='1':
            cal=(b-pow(2,n-1-i,cnt-1))%(cnt-1)
        else:
            cal=(a+pow(2,n-1-i,cnt+1))%(cnt+1)
        print(f(cal)+1)

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

s = input().split()
n = int(s[0])
s = input().split()
d = {}

for i in s:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
keys=list(d.keys())

for i in range(1,n+1):
    if str(i) in keys:
        print(d[str(i)])
    else:
        print(0)


### FIXED CODE ###

s = input().split()
n = int(s[0])
s = input().split()
d = [0]*n
for i in s:
    d[int(i)-1]+=1

for i in range(n):
    print(d[i])
### BUGGY CODE ###

n = int(input())
numbers = list(map(int, input().split()))
for i in range(n):
  for j in range(i+1, n-i):
    if numbers[i] == numbers[j]:
      print("NO")
      exit()
else:
  print("YES")


### FIXED CODE ###

n = int(input())
numbers = list(map(int, input().split()))
if len(numbers) == len(set(numbers)):
    print("YES")
else:
     print("NO")
### BUGGY CODE ###

mod=10**9+7
s=input()
n=len(s)
DP=[[0]*13 for _ in range(n+1)]
DP[0][0]=1
for i in range(n):
  r=(10**(n-1-i))%13
  if s[i]=="?":
    for j in range(10):
      rr=(r*j)%13
      for k in range(13):
        if k>=rr:
          DP[i+1][k]+=DP[i][k-rr]
        else:
          DP[i+1][k]+=DP[i][k-rr+13]
        DP[i+1][k]%=mod
  else:
    rr=(r*int(s[i]))%13
    for k in range(13):
      if k>=rr:
        DP[i+1][k]+=DP[i][k-rr]
      else:
        DP[i+1][k]+=DP[i][k-rr+13]
      DP[i+1][k]%=mod
print(DP[n][5]%mod)


### FIXED CODE ###

mod=10**9+7
s=input()
n=len(s)
R=[[[0]*13 for _ in range(10)] for __ in range(13)]
for i in range(13):
  for j in range(10):
    for k in range(13):
      R[i][j][k]=(k-i*j)%13

P=[0]*(n+1)
P[0]=1
for i in range(n):
  P[i+1]=(P[i]*10)%13

DP=[[0]*13 for _ in range(n+1)]
DP[0][0]=1
for i in range(n):
  r=P[n-1-i]
  if s[i]=="?":
    for k in range(13):
      DP[i+1][k]=sum(DP[i][R[r][j][k]] for j in range(10))
      DP[i+1][k]%=mod
  else:
    for k in range(13):
      DP[i+1][k]=DP[i][R[r][int(s[i])][k]]
      DP[i+1][k]%=mod
print(DP[n][5]%mod)
### BUGGY CODE ###

k=int(input())
for i in range(1,10**6):
    x=int("7"*i)
    if x%k==0:
        print(i)
        exit()
print(-1)

### FIXED CODE ###

k = int(input())
now = k
r = 0
for i in range(1, k + 100):
    r = (r * 10 % k + 7) % k
    if r==0:
        print(i)
        exit()
print(-1)
### BUGGY CODE ###

import bisect

N = int(input()) # それぞれのパーツの数
A = list(map(int, input().split())) # 小さい
B = list(map(int, input().split())) # 中くらい
C = list(map(int, input().split())) # 大きい

# Cは並び替え不要
A.sort()
B.sort()

total = 0
for c in C:
    b_count = bisect.bisect_left(B, c) # bの数量
    for b in B[:b_count]:
        a_count = bisect.bisect_left(A, b) # aの数量
        total += a_count

print(total)


### FIXED CODE ###

import bisect
import itertools

N = int(input()) # それぞれのパーツの数
A = list(map(int, input().split())) # 小さい
B = list(map(int, input().split())) # 中くらい
C = list(map(int, input().split())) # 大きい

# Cは並び替え不要
A.sort()
B.sort()

# Bの各要素でAを二分探索して返ってきたindexを先に保有しておく
b_counts = [0] * N
for i in range(N):
    b_count = bisect.bisect_left(A, B[i])
    b_counts[i] = b_count

cumsum_b_counts = list(itertools.accumulate(b_counts))
cumsum_b_counts = [0] + cumsum_b_counts

# Cの各要素でBを二分探索。上記で保有しておいたb_countsを活用する
total = 0
for c in C:
    count = bisect.bisect_left(B, c)
    total += cumsum_b_counts[count]

print(total)
### BUGGY CODE ###

import itertools
import heapq
import sys
import functools
import operator
import numpy as np
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
b = np.abs(a)
b = sorted(a,reverse = True)
b_k = b[k-1] 
a_new = [a[_] for _ in range(len(a)) if np.abs(a)[_] >= b_k]
a_new.sort()
C=[]
D=[]
for i in range(len(a_new)):
  for j in range(k):
    C.append(a_new[i+j-k])
  D.append(C)
  C=[]    
A = (functools.reduce(operator.mul,D[_]) for _ in range(len(D)))
l_max = max(A)
waru = 10**9 + 7
print(l_max % waru)

### FIXED CODE ###

import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero and k%2:
    ans = 0
  else:
    if k%2:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)
### BUGGY CODE ###

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


def dfs(parts):
    global ans
    n = len(parts)
    if n == 3:
        ans += 1
    elif n == 2:
        for i in c:
            if parts[1] < i:
                dfs(parts + [i])
            else:
                break
    elif n == 1:
        for j in b:
            if parts[0] < j:
                dfs(parts + [j])
            else:
                break


ans = 0
for i in a:
    dfs([i])

print(ans)


### FIXED CODE ###

import bisect

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

ans = 0
for i in b:
    a_pos = bisect.bisect_left(a, i)
    c_pos = n - bisect.bisect_right(c, i)
    ans += a_pos * c_pos

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

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

ans = abs(sum(a[1:])-a[0])
X = sum(a)

for i in range(1,N):
    sa = abs(X - 2*sum(a[:i]))
    ans = min(ans,sa)

print(ans)


### FIXED CODE ###

input()
cards = tuple(map(int, input().split(' ')))

a = sum(cards[1:])
s = cards[0]
diff_min = abs(a - s)

for card in cards[1:-1]:
    a -= card
    s += card
    diff_min = min(diff_min, abs(a - s))

print(diff_min)
### BUGGY CODE ###

import sys
from heapq import heapify,heappop,heappush,heapreplace

read=sys.stdin.read
readline=sys.stdin.readline

def main():
  n,m,*lrd=map(int,read().split())
  hp=[]
  heapify(hp)
  for l,r,d in zip(*[iter(lrd)]*3):
    if l>r:
      heappush(hp,(r,l,-d))
    else:
      heappush(hp,(l,r,d))
  if len(hp)<2:
    print('Yes')
    return
  while hp:
    ce=heappop(hp)
    while hp:
      ne=hp[0]
      if ce[0]==ne[0]:
        if ce[1]==ne[1]:
          if ce[2]!=ne[2]:
            print('No')
            return
          else:
            heappop(hp)
        else:
          heapreplace(hp,(ce[1],ne[1],ne[2]-ce[2]))
      else:
        break      
  print('Yes')

if __name__=='__main__':
  main()
      
    
    

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.dist=[0]*n 
    
    def find(self,x):
        if self.parents[x]<0:
            return self.dist[x],x
        else:
            tmp=self.find(self.parents[x])
            self.dist[x]+=tmp[0]
            self.parents[x]=tmp[1]
        return self.dist[x], self.parents[x]
    
    def union(self,x,y,d):
        rx=self.find(x)[1]
        ry=self.find(y)[1]
        diff=self.dist[y]-self.dist[x]-d
        if rx==ry:
            if diff!=0:
                return True
            return False
        if diff<0:
            rx,ry=ry,rx
            diff=-diff
        self.parents[ry]=min(self.parents[ry],self.parents[rx]-diff)
        self.parents[rx]=ry
        self.dist[rx]=diff
        return False
    
def main():
    n,m,*lrd=map(int,read().split())
    v=Unionfind(n)
    for l,r,d in zip(*[iter(lrd)]*3):
        if v.union(l-1,r-1,d):
            print('No')
            break
    else:
        if max(-d-1 for d in v.parents if d<0) >10**9:
            print('No')
        else:
            print('Yes')
if __name__=='__main__':
    main()
### BUGGY CODE ###

N = int(input())
S = input()

R = []
G = []
B = []
for i in range(N):
    if S[i] == 'R':
        R.append(i+1)
    elif S[i] == 'G':
        G.append(i+1)
    elif S[i] == 'B':
        B.append(i+1)

ans = 0
for i in range(len(R)):
    for j in range(len(G)):
        for k in range(len(B)):
            tmpi = min(R[i], G[j], B[k])
            tmpk = max(R[i], G[j], B[k])
            tmpj = (R[i] + G[j] + B[k])-(tmpi+tmpk)

            if (tmpj-tmpi) != (tmpk-tmpj):
                ans += 1
print(ans)


### FIXED CODE ###

import copy

N = int(input())
S = input()

RL = [0]*(N+1)
GL = copy.deepcopy(RL)
BL = copy.deepcopy(RL)
R = []
G = []
B = []
for i in range(N):
    if S[i] == 'R':
        R.append(i+1)
        RL[i+1] = 1
    elif S[i] == 'G':
        G.append(i+1)
        GL[i+1] = 1
    elif S[i] == 'B':
        B.append(i+1)
        BL[i+1] = 1

len_r = len(R)
len_g = len(G)
len_b = len(B)
ans = 0
if max(len_r, len_g, len_b) == len_b:
    for i in range(len_r):
        for j in range(len_g):
            ans += len_b
            tmp_abs = abs(R[i]-G[j])

            index = (min(R[i], G[j])-tmp_abs)
            if index > 0 and BL[index] == 1:
                ans -= 1

            index = (max(R[i], G[j])+tmp_abs)
            if index <= N and BL[index] == 1:
                ans -= 1

            if tmp_abs % 2 == 0 and BL[max(R[i], G[j])-(tmp_abs//2)] == 1:
                ans -= 1

elif max(len_r, len_g, len_b) == len_g:
    for i in range(len_r):
        for j in range(len_b):
            ans += len_g
            tmp_abs = abs(R[i]-B[j])

            index = (min(R[i], B[j])-tmp_abs)
            if index > 0 and GL[index] == 1:
                ans -= 1

            index = (max(R[i], B[j])+tmp_abs)
            if index <= N and GL[index] == 1:
                ans -= 1

            if tmp_abs % 2 == 0 and GL[max(R[i], B[j])-(tmp_abs//2)] == 1:
                ans -= 1

else:
    for i in range(len_g):
        for j in range(len_b):
            ans += len_r
            tmp_abs = abs(G[i]-B[j])

            index = (min(G[i], B[j])-tmp_abs)
            if index > 0 and RL[index] == 1:
                ans -= 1

            index = (max(G[i], B[j])+tmp_abs)
            if index <= N and RL[index] == 1:
                ans -= 1

            if tmp_abs % 2 == 0 and RL[max(G[i], B[j])-(tmp_abs//2)] == 1:
                ans -= 1
print(ans)
### BUGGY CODE ###

import numpy as np
MOD = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))
A = np.array(A)
ans = 0
POW = 1
for j in range(60):
  tmp = A & 1
  one = sum(tmp)
  zero = N - one
  ans = (ans + one * zero * POW) % MOD
  A >>= 1
  POW = (POW*2)%MOD
print(ans%MOD)

### FIXED CODE ###

MOD = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))
bit = [0] * 60
for i in range(N):
  n = bin(A[i])
  for j in range(len(n)-1, 1, -1):
    bit[len(n)-j-1] += int(n[j])
ans = 0
POW = 1
for j in range(60):
  ans = (ans +bit[j]*(N-bit[j])*POW)%MOD
  POW = (POW * 2)%MOD
print(ans%MOD)
### BUGGY CODE ###

N =int(input())
words=[]
for i in range(N):
    words.append(input().rstrip())
candidate=list(set(words))
standard=0
for i in range(len(candidate)):
    if words.count(candidate[i])>standard:
        standard=words.count(candidate[i])
        presidents=[]
        presidents.append(candidate[i])
    elif words.count(candidate[i])==standard:
        presidents.append(candidate[i])
answers=sorted(presidents)
for answer in answers:
    print(answer)

### FIXED CODE ###

from sys import stdin
n=int(stdin.readline().rstrip())
#print(n)
dic={}
for i in range(n):
    s=stdin.readline().rstrip()
    if s in dic.keys():
        dic[s] +=1
    else:
        dic[s]=1
#print(dic)
#print(dic.keys())
sup=0
suc=[]
for (i,number) in dic.items():
    if number>sup:
        suc=[]
        sup=number
        suc.append(i)
    elif number==sup:
        suc.append(i)
for k in (sorted(suc)):
    print(k)
### BUGGY CODE ###

import math
def nC2(n):
  return math.factorial(n) / math.factorial(2) / math.factorial(n - 2)
N, M = map(int, raw_input().split())
A = []
B = []
for _ in range(M):
  a, b = map(int, raw_input().split())
  A.append(a - 1)
  B.append(b - 1)
max_inconvenience = nC2(N)

seg_tree = [i for i in range(N)]
seg_height = [1 for _ in range(N)]
seg_size = [1 for _ in range(N)]
def get_root(i):
  if i == seg_tree[i]:
    return i
  else:
    return get_root(seg_tree[i])

def unite(i, j):
  if get_root(i) == get_root(j):
    return
  if seg_height[get_root(i)] > seg_height[get_root(j)]:
    seg_size[get_root(i)] += seg_size[get_root(j)]
    seg_tree[get_root(j)] = get_root(i)
  elif seg_height[get_root(i)] < seg_height[get_root(j)]:
    seg_size[get_root(j)] += seg_size[get_root(i)]
    seg_tree[get_root(i)] = get_root(j)
  else:
    seg_height[get_root(i)] += 1
    seg_size[get_root(i)] += seg_size[get_root(j)]
    seg_tree[get_root(j)] = get_root(i)

def same(i, j):
  return get_root(i) == get_root(j)

rev_res = [max_inconvenience]
for a, b in reversed(zip(A, B)):
  res = rev_res[-1] - seg_size[get_root(a)] * seg_size[get_root(b)] if not same(a, b) else rev_res[-1]
  rev_res.append(res)
  unite(a, b)
for res in reversed(rev_res[:-1]):
  print res

### FIXED CODE ###

import math
from collections import deque

class UnionFind():
  def __init__(self, n):
    self.seg_tree = [-1 for i in range(n)]
  
  def root(self, i):
    if self.seg_tree[i] < 0:
      return i
    else:
      self.seg_tree[i] = self.root(self.seg_tree[i])
      return self.seg_tree[i]

  def size(self, i):
    return -self.seg_tree[self.root(i)]

  def unite(self, i, j):
    if self.same(i, j):
      return

    if self.size(i) == self.size(j):
      self.seg_tree[self.root(i)] -= self.size(j)
      self.seg_tree[self.root(j)] = self.root(i)
    elif self.size(i) > self.size(j):
      self.seg_tree[self.root(i)] -= self.size(j)
      self.seg_tree[self.root(j)] = self.root(i)
    else:
      self.seg_tree[self.root(j)] -= self.size(i)
      self.seg_tree[self.root(i)] = self.root(j)

  def same(self, i, j):
    return self.root(i) == self.root(j)

def nC2(n):
  return math.factorial(n) / math.factorial(2) / math.factorial(n - 2)

N, M = map(int, raw_input().split())
A = []
B = []
rev_res = []
uf = UnionFind(N)
for _ in range(M):
  a, b = map(long, raw_input().split())
  A.append(a - 1)
  B.append(b - 1)

ans = N * (N - 1) / 2
for a, b in reversed(zip(A, B)):
  rev_res.append(ans)
  if not uf.same(a, b):
    ans -= uf.size(a) * uf.size(b)
  uf.unite(a, b)

for r in reversed(rev_res):
  print r
### BUGGY CODE ###

S = list(input())
n = len(S)
res = 0
cur = 0
count = [0] * 2020
count[0] = 1
for i, c in enumerate(map(int, S)):
    cur = cur * 10 + c
    temp = (cur * pow(10, (n - i), 2019)) % 2019
    count[temp] += 1
print(sum(c * (c - 1) // 2 for c in count))

### FIXED CODE ###

S = list(input())
n = len(S)
cur = 0
count = [0] * 2020
count[0] = 1
for i, c in enumerate(map(int, S[::-1])):
    cur = (cur + c * pow(10, i, 2019)) % 2019
    count[cur] += 1
    
print(sum(c * (c - 1) // 2 for c in count))