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

import sys

# import re
# import math
# import collections
# import decimal
# import bisect
# import itertools
# import fractions
# import functools
# import copy
# import heapq
# import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 10
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    h, w = ns()
    mat = [list(sys.stdin.readline()) for _ in range(h)]

    def bfs(x, y):
        arrived_mat = [[False for i in range(w)] for j in range(h)]

        que = queue.Queue()
        que.put((x, y, 1))
        arrived_mat[y][x] = True
        res = 0

        direc = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        while que.qsize() > 0:
            xi, yi, cnt = que.get()
            arrived_mat[yi][xi] = True

            for dx, dy in direc:
                next_x = xi + dx
                next_y = yi + dy
                if -1 < next_x < w and -1 < next_y < h:
                    if mat[next_y][next_x] == "." and arrived_mat[next_y][next_x] != True:
                        que.put((next_x, next_y, cnt + 1))
                        res = max(res, cnt + 1)

        return res

    ans = 0
    for y in range(h):
        for x in range(w):
            if mat[y][x] == ".":
                ans = max(ans, bfs(x, y) - 1)

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

# import re
# import math
# import collections
# import decimal
# import bisect
# import itertools
# import fractions
# import functools
# import copy
# import heapq
# import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 10
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    h, w = ns()
    mat = [list(sys.stdin.readline()) for _ in range(h)]

    def bfs(x, y):
        arrived_mat = [[False for i in range(w)] for j in range(h)]

        que = queue.Queue()
        que.put((x, y, 1))
        arrived_mat[y][x] = True
        res = 0

        direc = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        while que.qsize() > 0:
            xi, yi, cnt = que.get()

            for dx, dy in direc:
                next_x = xi + dx
                next_y = yi + dy
                if -1 < next_x < w and -1 < next_y < h:
                    if mat[next_y][next_x] == "." and arrived_mat[next_y][next_x] != True:
                        que.put((next_x, next_y, cnt + 1))
                        arrived_mat[next_y][next_x] = True                        
                        res = max(res, cnt + 1)

        return res

    ans = 0
    for y in range(h):
        for x in range(w):
            if mat[y][x] == ".":
                ans = max(ans, bfs(x, y) - 1)

    print(ans)


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

s = input()
n = int(input())
for i in range(n):
    order = list(input().split())
    if len(order) == 3:
        if int(order[1]) == 1:
            s = order[2] + s
        else:
            s += order[2]
    else:
        s = s[::-1]
print(s)

### FIXED CODE ###

from collections import deque
s = deque(input())
n = int(input())
initial = True
for i in range(n):
    order = list(input().split())
    if len(order) == 3:
        if initial:
            if int(order[1]) == 1:
                s.appendleft(order[2])
            else:
                s.append(order[2])
        else:
            if int(order[1]) == 1:
                s.append(order[2])
            else:
                s.appendleft(order[2])
    else:
        initial = not initial
    
if initial:
    print(''.join(s))
else:
    print(''.join(s)[::-1])
### BUGGY CODE ###

import collections
N = int(input())
S = input()
S_list = [S[i] for i in range(N)]
S_c = collections.Counter(S_list)
list12 = []
ans = 0
for i in range(N-2):
    s1 = S_list[i]
    S_c[s1] = S_c[s1]-1
    S_c23 = S_c.copy()

    for j in range(i+1,N-1):

        s2 = S_list[j]

        S_c23[s2] = S_c23[s2] - 1
        if (s1+s2) in list12:
            pass
        else:
            list12.append(s1+s2)
            for key in S_c23.keys():
                if S_c23[key] != 0:
                    ans+=1
print(ans)

### FIXED CODE ###

import collections
N = int(input())
S = input()
S_list = [S[i] for i in range(N)]
S_c = collections.Counter(S_list)
list12 = []
list1 = []

ans = 0
for i in range(N-2):
    s1 = S_list[i]

    S_c[s1] = S_c[s1]-1
    if s1 in list1:
        continue

    S_c23 = S_c.copy()
    list1.append(s1)
    for j in range(i+1,N-1):
        s2 = S_list[j]
        
        S_c23[s2] = S_c23[s2] - 1
        if (s1+s2) in list12:
            continue
        else:
            list12.append(s1+s2)
            for key in S_c23.keys():
                if S_c23[key] != 0:
                    ans+=1
print(ans)
### BUGGY CODE ###

N, Ma, Mb = map(int, input().split())
a = [[0, 0, 0] for _ in range(N)]
sa = 0
sb = 0
for i in range(N):
    a[i][0], a[i][1], a[i][2] = map(int, input().split())
    sa += a[i][0]
    sb += a[i][1]
INF = 1000000  

DP = [[[INF for _ in range(sb+1)] for _ in range(sa+1)] for _ in range(N+1)]
DP[0][0][0] = 0

for i in range(N):
    for j in range(sa+1):
        for k in range(sb+1):
            if(j >= a[i][0] and k >= a[i][1]):
                DP[i+1][j][k] = min(DP[i][j-a[i][0]][k-a[i][1]] + a[i][2], DP[i][j][k])
            else:
                DP[i+1][j][k] = DP[i][j][k]
ans = INF
for i in range(1, min(sa//Ma, sb//Mb)+1):
    ans = min(ans, DP[N][Ma*i][Mb*i])
    
if(ans == INF):
    print(-1)
else:
    print(ans)

### FIXED CODE ###

def main():
    N, Ma, Mb = map(int, input().split())
    yakuhin = []
    sa = 0
    sb = 0
    for i in range(N):
        yakuhin.append(list(map(int, input().split())))
        sa += yakuhin[i][0]
        sb += yakuhin[i][1]
    
    INF = 10**15
    DP = [[[INF for _ in range(sb+1)] for _ in range(sa+1)] for _ in range(N+1)]
    
    for i in range(N):
        DP[i][0][0] = 0
    
    for i in range(N):
        for j in range(sa+1):
            for k in range(sb+1):
                if(j >= yakuhin[i][0] and k >= yakuhin[i][1]):
                    DP[i+1][j][k] = min(DP[i][j][k], DP[i][j-yakuhin[i][0]][k-yakuhin[i][1]]+yakuhin[i][2])
                else:
                    DP[i+1][j][k] = min(DP[i+1][j][k], DP[i][j][k])
        
    ans = INF
    for i in range(1, N+1):
        for j in range(1, sa+1):
            for k in range(1, sb+1):
                if(j*Mb == k*Ma):
                    ans = min(ans, DP[i][j][k])    
        
    print(ans if ans != INF else -1)
    
main()
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    cnt = 0
    for i in range(N):
        if i > 0 and A[i] == A[i-1]:
            continue
        for j in range(i+1,N):
            if A[i] % A[j] == 0:
                break
        else:
            cnt += 1

    print(cnt)


if __name__ == "__main__":
    main()

### FIXED CODE ###

def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

def main():
    N = int(input())
    A = list(map(int, input().split()))
    max_A = max(A)
    ans = [0] * (max_A + 1)
    A.sort()
    for a in A:
        tmp = 1
        b = 0
        while b <= max_A:
            b = a * tmp
            if b > max_A:
                break
            ans[b] += 1
            tmp += 1
    cnt = 0
    for a in A:
        if ans[a] == 1:
            cnt += 1

    print(cnt)


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

# 2020-05-22
def main():
    n, m, k = [int(x) for x in input().split()]
    friends = [set() for _ in range(n)]
    blocks = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        blocks[a].add(b)
        blocks[b].add(a)

    networks = {}  # The dict of networks as sets. Keys are leaders.
    net_leaders = [-1] * n  # The leaders of the networks that the ones joined.
    visited = [False] * n
    for person in range(n):
        if visited[person]:
            continue
        network = set()
        network_add = network.add
        stack = [person]
        stack_append = stack.append
        stack_pop = stack.pop
        while stack:
            new = stack_pop()
            visited[new] = True
            net_leaders[new] = person
            network_add(new)
            for adj in friends[new]:
                if visited[adj]:
                    continue
                stack_append(adj)
        networks[person] = network

    answers = []
    answers_append = answers.append
    for person in range(n):
        net = networks[net_leaders[person]]
        ans = len(net) - len(friends[person]) - 1
        for block in blocks[person]:
            if block in net:
                ans -= 1
        answers_append(ans)

    print(*answers)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

# 2020-05-22
def main():
    n, m, k = [int(x) for x in input().split()]
    friends = [set() for _ in range(n)]
    blocks = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        blocks[a].add(b)
        blocks[b].add(a)

    networks = {}  # The dict of networks as sets. Keys are leaders.
    net_leaders = [-1] * n  # The leaders of the networks that the ones joined.
    visited = [False] * n
    for person in range(n):
        if visited[person]:
            continue
        network = set()
        network_add = network.add
        stack = [person]
        stack_append = stack.append
        stack_pop = stack.pop
        while stack:
            new = stack_pop()
            visited[new] = True
            net_leaders[new] = person
            network_add(new)
            for adj in friends[new]:
                if visited[adj]:
                    continue
                stack_append(adj)
        networks[person] = network

    answers = []
    answers_append = answers.append
    for person in range(n):
        net = networks[net_leaders[person]]
        ans = len(net) - len(friends[person]) - 1
        for block in blocks[person]:
            if block in net:
                ans -= 1
        answers_append(ans)

    print(*answers)
    return


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

n, m = map(int, input().split())
hlis = list(map(int, input().split()))
road = []
for i in range(m):
    a, b = map(int, input().split())
    road.append([a, b])
table = [0]*n
ans = 0
for i in range(n):
    if table[i] == 0:
        rival = []
        for j in road:
            if j[0] == i+1:
                rival.append(j[1]-1)
            elif j[1] == i+1:
                rival.append(j[0]-1)
        if hlis[i] == max([hlis[q] for q in rival]+[hlis[i]]) and [hlis[q] for q in rival].count(hlis[i])== 0:
            table[i] = 1
            ans += 1
            for q in rival:
                table[q] = -1 
        else:
            table[i] = -1
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
hlis = list(map(int, input().split()))
lis = [1]*n
for i in range(m):
    a, b = map(int, input().split())
    if hlis[a-1] > hlis[b-1]:
        lis[b-1] = -1
    elif hlis[a-1] < hlis[b-1]:
        lis[a-1] = -1
    elif hlis[a-1] == hlis[b-1]:
        lis[a-1] = -1
        lis[b-1] = -1
print(lis.count(1))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n, k = map(int, input().split())
h = list(map(int, input().split()))

INF = float('inf')
dp = [INF for _ in range(n)]
dp[0] = 0

for i in range(1, n):
    l, r = max(i - k, 0), i
    for j in range(l, r):
        dp[r] = min(dp[r], dp[j] + abs(h[r] - h[j]))

print(dp[-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-
n, k = map(int, input().split())
h = list(map(int, input().split()))

INF = float('inf')
dp = [INF for _ in range(n)]
dp[0] = 0

for i in range(1, n):
    l, r = max(i - k, 0), i
    dp[i] = min([pdp + abs(h[i] - ph) for pdp, ph in zip(dp[l:r], h[l:r])])

print(dp[-1])
### BUGGY CODE ###

import sys, bisect
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))

N = read_int()[0]
A = sorted(read_int())
B = sorted(read_int())
C = sorted(read_int())

def solve():
    ans = 0
    for i in range(N):
        lbb = bisect.bisect_right(B,A[i])
        for j in range(lbb, N):
            lbc = bisect.bisect_right(C,B[j])
            ans += N - lbc
    return ans


if __name__ == "__main__":
    print(solve())

### FIXED CODE ###

import sys, bisect
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))

N = read_int()[0]
A = sorted(read_int())
B = sorted(read_int())
C = sorted(read_int())

def solve():
    ans = 0
    # memo
    memo = [0 for _ in range(N + 1)]
    for i in range(N - 1, -1, -1):
        lbc = bisect.bisect_right(C,B[i])
        memo[i] += N - lbc
        if i > 0:
            memo[i - 1] = memo[i]
    for i in range(N):
        lbb = bisect.bisect_right(B,A[i])
        ans += memo[lbb]
    return ans


if __name__ == "__main__":
    print(solve())
### BUGGY CODE ###

N,M = [int(s) for s in input().split()]
pre_lst=[]
for i in range(N):
  a,b = [int(s) for s in input().split()]
  pre_lst=pre_lst+[[a,b,a*b]]
lst = sorted(pre_lst, key=lambda x: x[0])
m=0
i=0
cost=0
while m<M:
  m+=lst[i][1]
  cost+=lst[i][2]
  i+=1
if(m>M):
  cost-=lst[i-1][0]*(m-M)
print(cost)

### FIXED CODE ###

n, m = map(lambda x: int(x), input().split())
drinks = []
for _ in range(n):
    a, b = map(lambda x: int(x), input().split())
    drinks.append((a, b))
    
sorted_drinks = sorted(drinks, key=lambda x: x[0])

num_drinks = 0
sum_prices = 0
for price, num in sorted_drinks:
    num_drinks += num
    sum_prices += num * price
    if num_drinks > m:
        sum_prices -= (num_drinks - m) * price
        break
    elif num_drinks == m:
        break

print(sum_prices)
### BUGGY CODE ###

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

ans = 1
for i in a:
    ans *= i

if ans > 10**18:
    print(-1)

else:
    print(ans)

### FIXED CODE ###

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

ans = 1

if min(a)==0:
    print(0)
    exit()

for i in a:
    ans *= i
    if ans > 10**18:
        print(-1)
        exit()

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

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

lap = 0
big = max(a)
while big > 0:
    big //= 2
    lap += 1

xor = [0 for _ in range(lap)]
for i in a:
    num = 0
    for j in range(lap):
        if i % 2 == 1:
            xor[num] += 1
        i //= 2
        num += 1

ans = 0
for i in range(lap):
    ans += pow(2, i, mod) * xor[i] * (n - xor[i]) % mod
    ans %= mod

print(ans)

### FIXED CODE ###

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

lap = 0
big = max(a)
while big > 0:
    big //= 2
    lap += 1

xor = [0 for _ in range(lap)]
for i in a:
    num = 0
    for j in range(lap):
        if i % 2 == 1:
            xor[num] += 1
        i //= 2
        num += 1

ans = 0
for i in range(lap):
    ans += pow(2, i, mod) * xor[i] * (n - xor[i]) % mod
    ans %= mod

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

from collections import deque, defaultdict
N, X, Y = map(int, input().split())  # N個の頂点, XとYが繋がっている

graph = [[] for _ in range(N)]
for i in range(N-1):
    graph[i].append(i+1)
    graph[i+1].append(i)
X -= 1
Y -= 1
graph[X].append(Y)
graph[Y].append(X)
# print(graph)

# 最後に//2すれば良い
ans = defaultdict(int)
for i in range(N):
    q = deque()
    # 開始のノード
    q.append(i)
    visited = [False]*N
    visited[i] = True
    distant = [100000] * N
    distant[i] = 0
    while len(q):
        v = q.popleft()
        for e in graph[v]:
            if visited[e]:
                continue
            distant[e] = distant[v] + 1
            ans[distant[e]] += 1
            visited[e] = True
            q.append(e)
    # 始点iからの幅優先探索完了
# print(ans)
for i in range(1, N):
    print(ans[i]//2)


### FIXED CODE ###

from collections import deque, defaultdict

N, X, Y = map(int, input().split())
# 全探索でいけるのでは？
# 有向グラフとしてN回幅優先すれば良いのでは？
tree = [[] for _ in range(N)]
for i in range(N-1):
    tree[i].append(i+1)
    tree[i+1].append(i)
tree[X-1].append(Y-1)
tree[Y-1].append(X-1)
ans = defaultdict(int)
q = deque()
# 更新されない時はqに追加しない
for i in range(N):
    distant = [N]*N
    q.append(i)  # 始まりのノード
    distant[i] = 0
    while len(q):
        # vは数字, 親のノードのインデックス
        v = q.pop()
        for e in tree[v]:
            if distant[e] < distant[v]+1:  # 到達済みなら次のノードへ
                continue
            distant[e] = distant[v]+1
            q.append(e)
    for d in distant:
        ans[d] += 1
for i in range(1, N):
    print(ans[i]//2)
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
l=""
for i in range(N):
    l=l+str(a.index(i+1)+1)+" "
print(l)

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
b=[0]*N
for index, m in enumerate(a):
    b[m-1]=index+1
print(*b)
### BUGGY CODE ###

#!/usr/bin/evn python3

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

for i in range(1, N+1):
    if not A:
        print(0)
    else:
        print(A.count(i))
        A =[j for j in A if j != i]

### FIXED CODE ###

#!/usr/bin/env python3

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

lis = [0] * N
for i in A:
    lis[i-1] += 1

for i in range(len(lis)):
    print(lis[i])
### BUGGY CODE ###

N,K = map(int,input().split())
A=sorted(list(map(int,input().split())))
F=sorted(list(map(int,input().split())),reverse=True)
ok=A[-1]*F[0]
ng=-1
while(ng+1<ok):
  c=ng+(ok-ng)//2
  sum=0
  for i in range(N):
    if(A[i] - c//F[i]>=0):
      sum += A[i] - c//F[i]
  if(sum<=K):
    ok=c
  else:
    ng=c
 
print(ok)

### FIXED CODE ###

def is_ok(x):
    result = 0
    for i in range(N):
        a = A[i]
        t = x // F[i]
        if t < a:
            result += a - t
    return result <= K

N,K = map(int,input().split())
A=list(map(int,input().split()))
F=list(map(int,input().split()))
A.sort()
F.sort(reverse=True)
ok=A[-1]*F[0]
ng=-1
while(ng+1<ok):
  c=ng+(ok-ng)//2
  if is_ok(c):
    ok=c
  else:
    ng=c

print(ok)
### BUGGY CODE ###

def main():
    import collections
    K = int(input())
    N = len(input())
    mod = 10**9 + 7

    def cmb(n, r, mod):
        if (r < 0 or r > n):
            return 0
        r = min(r, n-r)
        return g1[n] * g2[r] * g2[n-r] % mod

    n = N + K
    g1 = [1, 1]  # 元テーブル
    g2 = [1, 1]  # 逆元テーブル
    inverse = [0, 1]  # 逆元テーブル計算用テーブル

    for i in range(2, n + 1):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

    d = [0]*(K+1)
    d[0] = 1
    d2 = [0]*(K+1)
    d2[0] = 1

    for i in range(K):
        d[i+1] = d[i]*26
        d[i+1] %= mod

        d2[i+1] = d2[i]*25
        d2[i+1] %= mod

    ans = 0
    for i in range(K+1):
        ans += d2[K-i] * d[i] * cmb(N+K-i-1, N-1, mod)
        ans %= mod
    print(ans)


main()


### FIXED CODE ###

def main():
    import collections
    K = int(input())
    N = len(input())
    mod = 10**9 + 7

    def cmb(n, r, mod):
        if (r < 0 or r > n):
            return 0
        r = min(r, n-r)
        return g1[n] * g2[r] * g2[n-r] % mod

    n = N + K
    g1 = [1, 1]  # 元テーブル
    g2 = [1, 1]  # 逆元テーブル
    inverse = [0, 1]  # 逆元テーブル計算用テーブル

    for i in range(2, n + 1):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

    d = [0]*(K+1)
    d[0] = 1
    d2 = [0]*(K+1)
    d2[0] = 1

    for i in range(K):
        d[i+1] = d[i]*26
        d[i+1] %= mod

        d2[i+1] = d2[i]*25
        d2[i+1] %= mod

    ans = 0
    for i in range(K+1):
        ans += d2[K-i] * d[i] * cmb(N+K-i-1, N-1, mod)
        ans %= mod
    print(ans)


main()
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
mod=1000000000000000000
ans=1
p=1
for i in range(0,n):
  x=l[i]
  p=p*x
  if(x==0):
    ans=0
    break
if(p>mod):
    ans=-1
if(ans!=0 and ans!=-1):
  ans=p
print(ans)
  
  


### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
mod=1000000000000000000
ans=1
p=1
if(l.count(0)>=1):
    ans=0
else:
    for i in range(0,n):
        x=l[i]
        p=p*x
        if(p>mod):
            ans=-1
            break
if(ans!=0 and ans!=-1):
    ans=p
print(ans)
### BUGGY CODE ###

N = int(input())

A_i = []
for i in range(N):
    A_i.append(int(input()))

for i in range(N):
    A_i_copy = []
    if i == 0:
        A_i_copy = sorted(A_i[1:N])
    elif i == N - 1:
        A_i_copy = sorted(A_i[0:N-1])
    else:
        A_i_copy = sorted(A_i[0:i] + A_i[i+1:N])

    print(A_i_copy[N - 2])

### FIXED CODE ###

N = int(input())

A_i = []
for i in range(N):
    A_i.append(int(input()))

A_i_sord = sorted(A_i)
A_i_max_first = A_i_sord[N - 1]
A_i_max_second = A_i_sord[N - 2]

for i in range(N):
    if A_i_max_first == A_i[i]:
        print(A_i_max_second)
    else:
        print(A_i_max_first)
### BUGGY CODE ###

from operator import mul
from functools import reduce
import numpy as np
#def ConZ(i):
    #z_num = i+int(i*(i-1)/2)
    #return z_num
#def ConN(i):
    #n_num = int(i*(i-1)/2)
    #return n_num

def cmb(n):
    over = reduce(mul, range(n, n - 2, -1))
    under = reduce(mul, range(1,2 + 1))
    return over // under


S = input()[::-1]
keta = 1
A_num = 0
x = 0
mod = np.array([0]*2019)
mod[0] += 1
for i in range(len(S)):
    A_num += (int(S[i:i+1])*keta)%2019
    if A_num >= 2019:
        A_num = A_num%2019
    mod[A_num] +=1
    keta*=10
    
#print(mod)
#x += ConZ(mod[0])
#del mod[0]

#for j in range(len(mod)):
    #x+=cmb(mod[j])
#print(x)
print(int(np.sum(mod* (mod - 1) /2)))


### FIXED CODE ###

from operator import mul
from functools import reduce
import numpy as np
#def ConZ(i):
    #z_num = i+int(i*(i-1)/2)
    #return z_num
#def ConN(i):
    #n_num = int(i*(i-1)/2)
    #return n_num

def cmb(n):
    over = reduce(mul, range(n, n - 2, -1))
    under = reduce(mul, range(1,2 + 1))
    return over // under


S = input()[::-1]
keta = 1
A_num = 0
x = 0
mod = np.array([0]*2019)
mod[0] += 1
for i in range(len(S)):
    A_num += (int(S[i:i+1])*keta)%2019
    if A_num >= 2019:
        A_num = A_num%2019
    mod[A_num] +=1
    #keta*=10
    keta = keta * 10 % 2019
#print(mod)
#x += ConZ(mod[0])
#del mod[0]

#for j in range(len(mod)):
    #x+=cmb(mod[j])
#print(x)
print(int(np.sum(mod* (mod - 1) /2)))
### BUGGY CODE ###

n = int(input())

ai = [False for _ in range(n)]

ai = [int(s) for s in input().split()]

#print(ai)

dic = {}

for i in ai:
    if(i in dic):
        dic[i] += 1
    else:
        dic[i] = 1
    
for i in ai:
    dic[i] -= 1
    res = 0
    for j in dic:
        if(dic[j] < 2):
            continue
        else:
            res += int(dic[j]*(dic[j]-1)/2)
    
    print(res)
    dic[i] += 1

### FIXED CODE ###

n = int(input())

ai = [False for _ in range(n)]

ai = [int(s) for s in input().split()]

#print(ai)

dic = {}

for i in ai:
    if(i in dic):
        dic[i] += 1
    else:
        dic[i] = 1
mx = 0
for i in dic:
    if(dic[i] < 2):
            continue
    else:
        mx += int(dic[i]*(dic[i]-1)/2)

for i in ai:
    if(dic[i] < 2):
        print(mx)
    else:
        res = mx - (dic[i]-1)
        print(int(res))