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

def bfs(graph, start, goal, connection):
    visited = {start: None}
    unvisited = [start]
    while unvisited:
        now = unvisited[0]
        if now == goal or (1000000*now + goal) in connection:
            connection[1000000*start + goal] = 1
            connection[1000000*goal + start] = 1
            return "yes"
        unvisited = unvisited[1:]
        for next in graph[now]:
            if not (next in visited):
                unvisited.append(next)
                visited[next] = now
    return "no"

n, m = map(int, input().split())
g = [[] for i in range(n)]
c = {}

for i in range(m):
    inp = list(map(int, input().split()))
    g[inp[0]].append(inp[1])
    g[inp[1]].append(inp[0])
    c[1000000*inp[0] + inp[1]] = 1
    c[1000000*inp[1] + inp[0]] = 1

q = int(input())

for i in range(q):
    s, t = map(int, input().split())
    print(bfs(g, s, t, c))

### FIXED CODE ###

from collections import deque

def bfs(graph, start):
    visited = {start: None}
    unvisited = deque()
    unvisited.append(start)
    while unvisited:
        now = unvisited.popleft()
        for next in graph[now]:
            if not (next in visited):
                unvisited.append(next)
                visited[next] = now
    return visited

n, m = map(int, input().split())
g = [set() for i in range(n)]
group = []

for i in range(m):
    a, b = map(int, input().split())
    g[a].add(b)
    g[b].add(a)

q = int(input())

for i in range(q):
    s, t = map(int, input().split())
    for j in range(len(group)):
        if s in group[j] and t in group[j]:
            print("yes")
            break
        elif s in group[j]:
            print("no")
            break
    else:
        group_tmp = set(bfs(g, s).keys())
        if t in group_tmp:
            print("yes")
        else:
            print("no")
        group.append(group_tmp)
### BUGGY CODE ###

# 1. 最大公約数を求める(ユークリッドの互除法)
# 2. 最大公約数を素因数分解する。
# 3. 2.の結果に含まれる素数を２つのグループに分ける

from collections import defaultdict
import itertools

def main():
  a, b = map(int, input().split())
  c = gojo(a,b)
  
  fac = defaultdict(lambda : 0)
  #print(c)
  fac[1] = 1
  fac = facto(c, fac)
  #print(fac)
  keys = list((fac.keys()))
  print(len(keys))  
  
def facto(n, fac):
  if n == 1:
    return fac
  cursor = 2
  while True:
    if n % cursor == 0:
      fac[cursor] += 1
      n = n // cursor
      if n == 1:
        break
    else:
      cursor += 1
      
  return fac
  
def gojo(a,b):
  if b > a:
    a, b = b, a
  c = a % b
  if c == 0:
    return(b)
  else:
    return gojo(b, c)

if __name__ == "__main__":
  main()

### FIXED CODE ###

# 1. 最大公約数を求める(ユークリッドの互除法)
# 2. 最大公約数を素因数分解する。
# 3. 2.の結果に含まれる素数＋１が答え

import itertools
from fractions import gcd
from math import ceil

def main():
  a, b = map(int, input().split())
  fac = facto(gcd(a,b))
  print(len(fac))  
  
def facto(n):
  fac = [1]
  if n == 1:
    return [1]
  elif n % 2 == 0:
    fac = [1, 2]
    while n % 2 == 0:
      n = n // 2
  
  max_n = ceil(n ** 0.5) + 1
  
  is_prime = [True for x in range(max_n)]
  for cursor in range(3, max_n, 2):
    if is_prime[cursor]:
      if n % cursor == 0:
        fac.append(cursor)
        while n % cursor == 0:
          n = n // cursor
        if n == 1:
          break
      for i in range(cursor, max_n, cursor):
        is_prime[i] = False
  if n != 1:
    fac.append(n)
  return fac

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

import sys
sys.setrecursionlimit(1000000)
N, M=map(int, input().split())


ACs=[]
WAs={}

AC=0
pena=0
for i in range(M):
  num, jud=input().split()
  if num in ACs:
    continue
  
  if jud=="WA":
    if num not in WAs.keys():
      WAs[num]=1
    else:
      WAs[num]+=1
  else:
    ACs.append(num)
    AC+=1
    if num in WAs.keys():
      pena+=WAs[num]

print(AC, pena)



### FIXED CODE ###

N, M=map(int, input().split())
import numpy as np

pena=np.array([0]*N)
status=np.array([0]*N)


for i in range(M):
  p,s=tuple(input().split())
  p=int(p)
  if s=="WA":
    if status[p-1]!=1:
      pena[p-1]+=1
  if s=="AC":
    if status[p-1]!=1:
      status[p-1]=1
nac=sum(status)
npena=sum(pena*status)
print(nac, npena)
### BUGGY CODE ###

n,a,b = map(int,input().split())
ans = 0
q = 0
A = 'Blue'
if a == 0:
  print(0)
  exit()
  
for i in range(n):
  if i % 2 == 0:
    ans += a
    q += a
    A = 'Blue'
  if i % 2 != 0:
    q += b
    A = 'Red'
  if q > n:
    break
    
if A == 'Red':
  print(ans)
  
if A == 'Blue':
  print(ans-(q-n))

### FIXED CODE ###

n,a,b = map(int,input().split())
ans = 0
q = n // (a+b)

ans += q*a
q = n - (a+b)*q

if q - a >= 0:
    ans += a
if q - a < 0:
    ans = ans + a +(q-a)
print(ans)
### BUGGY CODE ###

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

    a = [i for i in a if i <k]
    n = len(a)

    DP1 = [[False]*(k+1)]
    DP1[0][0] = True
    DP2 = [[False]*(k+1)]
    DP2[0][0] = True
    b = a[::-1]

    for i in range(n):
        DP1.append(DP1[i][:])
        DP2.append(DP2[i][:])
        for j in range(k+1):
            if DP1[i][j] and a[i]+j <= k:
                DP1[i+1][a[i]+j] = True
            if DP2[i][j] and b[i]+j <= k:
                DP2[i+1][b[i]+j] = True

    for i in range(n+1):
        q = [0]
        for j in range(k+1):
            q.append(q[-1]+int(DP2[i][j]))
        DP2[i] = q

    ans = 0
    for i in range(n):
        use = False
        for j in range(k+1):
            if not DP1[i][j]:
                continue
            left = max(0, k-a[i]-j)
            right = k-j
            if DP2[n-i-1][right] - DP2[n-i-1][left]:
                use = True
                break
        if not use:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np

def main():
    def check(m):
        DP = np.full(k+1, False)
        DP[0] = True
        for i in range(n):
            if i == m:
                continue
            DP[a[i]:] = np.logical_or(DP[a[i]:], DP[:k+1-a[i]])
        return any(DP[i] for i in range(k-a[m], k))

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

    a = [i for i in a if i <k]
    a.sort()
    n = len(a)

    left = -1
    right = n

    while right-left > 1:
        mid = (right+left)//2
        if check(mid):
            right = mid
        else:
            left = mid

    print(right)

main()
### BUGGY CODE ###

H, W = map(int, input().split())
N = int(input())
color = [0]
data = list(map(int, input().split()))
for i in range(N):
    color.append(color[i] + data[i])

def num(i):
    for j in range(N):
        if color[j] <= i < color[j + 1]:
            return str(j + 1)

for h in range(H):
    line = ""
    for w in range(W):
        if h % 2 == 0:
            line = line + num(h * W + w)
            if w == W - 1:
                break
            line = line + " "
        else:
            line = num(h * W + w) + line
            if w == W - 1:
                break
            line = " " + line
    print(line)


### FIXED CODE ###

H, W = map(int, input().split())
N = int(input())
# color = [0]
data = list(map(int, input().split()))
# for i in range(N):
#    color.append(color[i] + data[i])

# def num(i):
#    for j in range(N):
#        if color[j] <= i < color[j + 1]:
#            return str(j + 1)

# grid = [[num(h * W + w) for w in range(W)] for h in range(H)]
col = 1
count = 1
grid = [["" for w in range(W)] for h in range(H)]
for h in range(H):
    for w in range(W):
        grid[h][w] = str(col)
        if count == data[col - 1]:
            count = 1
            col += 1
        else:
            count += 1

for h in range(H):
    if h % 2 == 0:
        print(" ".join(grid[h]))
    else:
        print(" ".join(grid[h][::-1]))
### BUGGY CODE ###

N, M = map(int, input().split())
adjL = [[] for v in range(N)]
indegs = [0] * N
for _ in range(N+M-1):
    u, v = map(int, input().split())
    adjL[u-1].append(v-1)
    indegs[v-1] += 1

parents = [-1] * N
vRoot = [v for v in range(N) if indegs[v] == 0][0]
vNows = set([vRoot])
while vNows:
    vNexts = set()
    for vNow in vNows:
        for v2 in adjL[vNow]:
            parents[v2] = vNow
            vNexts.add(v2)
    vNows = vNexts

for v in range(N):
    print(parents[v] + 1)


### FIXED CODE ###

from collections import deque

N, M = map(int, input().split())
adjL = [[] for v in range(N)]
indegs = [0] * N
for _ in range(N+M-1):
    u, v = map(int, input().split())
    adjL[u-1].append(v-1)
    indegs[v-1] += 1

parents = [-1] * N
Q = deque([v for v in range(N) if indegs[v] == 0])
while Q:
    vNow = Q.popleft()
    for v2 in adjL[vNow]:
        parents[v2] = vNow
        indegs[v2] -= 1
        if indegs[v2] == 0:
            Q.append(v2)

for v in range(N):
    print(parents[v] + 1)
### BUGGY CODE ###

import sys
from collections import Counter
input = lambda: sys.stdin.readline().rstrip()

MAX = 1000001
dp = [True for _ in range(MAX)]
n = int(input())
a = list(map(int, input().split()))
a.sort()
cnt = Counter(a)
ans = 0
for v in a:
   if cnt[v] <= 1 and dp[v]:
      ans += 1
   m = v
   while m < MAX:
      dp[m] = False
      m += v
print(ans)

### FIXED CODE ###

import sys
from collections import Counter
input = lambda: sys.stdin.readline().rstrip()

MAX = 1000001
dp = [True for _ in range(MAX)]
n = int(input())
a = list(map(int, input().split()))
cnt = Counter(a)
a = sorted(list(set(a)))
ans = 0
for v in a:
   if cnt[v] <= 1 and dp[v]:
      ans += 1
   m = v
   while m < MAX:
      dp[m] = False
      m += v
print(ans)
### BUGGY CODE ###

N =int(input())
L = list(map(int,input().split()))
A=1
for i in range(N):
    A = A * L[i]
    if i == N-1 and A <= 10**18:
        print(A)
if A > 10**18:
    print(-1)

### FIXED CODE ###

N = int(input())
Alist = list(map(int,input().split()))
Answer = 1
if 0 in Alist:
    Answer = 0
for i in range(N):
    Answer *= Alist[i]
    if Answer > 10**18:
        Answer = -1
        break
print(Answer)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
import numpy as np

def main():
    n,k=map(int,input().split())
    A=np.array(input().split(),np.int64)
    F=np.array(input().split(),np.int64)
    A.sort()
    F.sort()
    F=F[::-1]

    def ok(x): #チームの成績をxとするような修行の仕方が存在するか
        B=A-(x//F)
        return sum(B[B>0])<=k
    
    l=-1
    r=10**18
    while r-l>1:
        mid=(r+l)//2
        if ok(mid):
            r=mid
        else:
            l=mid
    print(r)   

if __name__=='__main__':
    main()

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
A = np.array(input().split(), dtype=np.int64)
F = np.array(input().split(), dtype=np.int64)
A = np.sort(A)
F = np.sort(F)[::-1]


def C(x):
    train = np.maximum(0, A - x // F).sum()
    return train <= K


left = -1
right = 10 ** 12 + 1
while right > left + 1:
    mid = (right + left) // 2
    if C(mid):  # 食べきれる場合
        right = mid
    else:
        left = mid

ans = right
print(ans)
### BUGGY CODE ###

N, x = map(int, input().split())
A = list(map(int, input().split()))
lowest_costs = A.copy()
A.extend(A)
ans = float('inf')

for k in range(N):
    cost = 0
    for i in range(N):
        lowest_costs[i] = min(lowest_costs[i], A[i+k])
        cost += lowest_costs[i]
    ans = min(cost + x * k, ans)

print(ans)

### FIXED CODE ###

N, x = map(int, input().split())
A = list(map(int, input().split()))
lowest_costs = A[:]
ans = float('inf')

for k in range(N):
    lowest_costs = [min(lowest_costs[i], A[i-k]) for i in range(N)]
    ans = min(sum(lowest_costs) + x * k, ans)

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

N,M=map(int,input().split())
b = input()
k = [[]*26]
s = [0]+[1]*N+[0]
from collections import defaultdict as ddict
d = ddict(lambda: [])
for i,t in enumerate(b):
  d[t].append(i+1)
for i in range(M):
  ta,tb=map(str,input().split())
  r = 1 if tb == "R" else -1
  for j in d[ta]:
    s[j+r] += s[j]
    s[j]   -= s[j]
print(N-s[-1]-s[0])
    

  



### FIXED CODE ###

N,M=map(int,input().split())
a = "a"+input()+"q"
k = []
for i in range(M):
  ta,tb=map(str,input().split())
  k.append([ta,tb])
k = k[::-1]
s = 1
t = N
c=0
for i, j in k:
  if j == "R" and i == a[t]:
    t-=1
    c+=1
  if j == "L" and i == a[s]:
    s+=1
  if j == "R" and i == a[s-1] and s!= 1:
    s-=1
  if j == "L" and i == a[t+1] and t!= N:
    t+=1
    c-=1
  if s+c-1==N and N!=0:break
if N>1:print(N-s-c-1+2)
else: 
  if s+c+1>1:print(1)
  else:print(0)
### BUGGY CODE ###

L, R = map(int, input().split())

P = 2019

def mul(a, b):
    return ((a % P) * (b % P)) % P

R = min(R, L+4038)

tmp = 10**9
for i in range(L, R):
    for j in range(L+1, R+1):
        tmp = min(mul(i, j), tmp)
        
print(tmp)

### FIXED CODE ###

L, R = map(int, input().split())

P = 2019

R = min(R, L+673)

tmp = 2018
for i in range(L, R):
    for j in range(L+1, R+1):
        tmp = min((i*j)%P, tmp)
        
print(tmp)
### BUGGY CODE ###

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


def maximum_profit(profits):
    max_v = profits[1] - profits[0]

    for j in range(1, len(profits)):
        for i in range(0, j):
            max_v = max(profits[j] - profits[i], max_v)

    print(max_v)


def to_int(v):
    return int(v)


if __name__ == '__main__':
    l = to_int(input())
    profits = [to_int(input()) for i in range(l)]

    maximum_profit(profits)

### FIXED CODE ###

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


def maximum_profit(profits):
    max_v = profits[1] - profits[0]
    min_v = profits[0]

    for j in range(1, len(profits)):
        max_v = max(max_v, profits[j]-min_v)
        min_v = min(min_v, profits[j])

    print(max_v)


def to_int(v):
    return int(v)


if __name__ == '__main__':
    l = to_int(input())
    profits = [to_int(input()) for i in range(l)]

    maximum_profit(profits)
### BUGGY CODE ###

N,W=map(int,input().split())
v=[]
w=[]
for _ in range(N):
    ww,vv=map(int,input().split())
    v.append(vv)
    w.append(ww)

dp=[[0 for _ in range(W)] for _ in range(N)]

for h in range(W):
    if h+1>=w[0]:
        dp[0][h]=v[0]

for i in range(1,N):
    for j in range(W):
        if j+1>w[i]:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
        else:
            dp[i][j]=dp[i-1][j]
print(max(dp[-1]))

### FIXED CODE ###

N,W=map(int,input().split())
v=[]
w=[]
for _ in range(N):
    ww,vv=map(int,input().split())
    v.append(vv)
    w.append(ww)

dp=[[0 for _ in range(W)] for _ in range(N)]

for h in range(W):
    if h+1>=w[0]:
        dp[0][h]=v[0]

for i in range(1,N):
    for j in range(W):
        if j+1>w[i]:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[-1][-1])
### BUGGY CODE ###

import numpy as np

H, W = map(int, input().split())
S = [input() for _ in range(H)]
 
up =    np.zeros((H+2, W+2), dtype=int)
down =  np.zeros((H+2, W+2), dtype=int)
left =  np.zeros((H+2, W+2), dtype=int)
right = np.zeros((H+2, W+2), dtype=int)

for i in range(1, H+1):
    for j in range(1, W+1):
        if S[i-1][j-1] == '.':
            up[i][j] = up[i-1][j] + 1
            left[i][j] = left[i][j-1] + 1
        
        if S[-i][-j] == '.':
            down[-1-i][-1-j] = down[-i][-1-j] + 1
            right[-1-i][-1-j] = right[-1-i][-j] + 1

print(np.max(up+down+left+right)-3)

### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)]) == '.'
up = np.zeros((H, W), dtype=int)
down = np.zeros((H, W), dtype=int)
left = np.zeros((H, W), dtype=int)
right = np.zeros((H, W), dtype=int)
 
for i in range(H):
    up[i] = (up[i-1] + 1) * S[i]
    down[-i-1] = (down[-i] + 1) * S[-i-1]

for i in range(W):
    left[:, i] = (left[:, i-1] + 1) * S[:, i]
    right[:, -i-1] = (right[:, -i] + 1) * S[:, -i-1]

print(np.max(up+down+left+right)-3)
### BUGGY CODE ###

n, m, k = map(int, input().split())

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

acA = [0]
for i in range(n):
  acA.append(acA[i] + A[i])

acB = [0]
for i in range(m):
  acB.append(acB[i] + B[i])

ans = 0
for a in range(n+1):
  for b in range(m+1):
    if acA[a] + acB[b] <= k:
      ans = max(ans, a + b)
    else:
      break

print(ans)

### FIXED CODE ###

import bisect

n, m, k = map(int, input().split())

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

acA = [0]
for i in range(n):
  acA.append(acA[i] + A[i])

acB = [0]
for i in range(m):
  acB.append(acB[i] + B[i])

ans = 0
for a in range(n+1):
  if k-acA[a] < 0: break
  b = bisect.bisect(acB, k-acA[a]) - 1
  ans = max(ans, a+b)
    
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
lcm = a[0]
for i in range(1,n):
  big,sml = lcm,a[i]
  while sml != 0:
    big,sml = sml,big%sml
  lcm *= a[i] // big
ans = 0
mod = 10 ** 9 + 7
for i in range(n):
  tmp = lcm // a[i]
  tmp %= mod
  ans += tmp
  ans %= mod
print(ans)
#print(lcm)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
mod = 10 ** 9 + 7
lcm = a[0]
for i in range(1,n):
  big,sml = lcm,a[i]
  while sml != 0:
    big,sml = sml,big%sml
  lcm *= a[i] // big
ans = 0
def inv(x):
  y = 1
  while x != 1:
    y *= mod // x + 1
    y %= mod
    x -= mod % x
  return y
#print(inv(5))
for i in range(n):
  ans += inv(a[i])
  ans %= mod
#print(ans)
ans *= lcm
ans %= mod
print(ans)
#print(lcm)
#print(1000000*999999*999998%mod)
### BUGGY CODE ###

s = list(map(int , input()))
n = len(s)
i = 0
while True:
    try:
        if s[i] + s[i+1] == 1:
            del s[i]
            del s[i]
            i = 0
        else:
            i += 1
    except:
        break
print(n - len(s))

### FIXED CODE ###

import numpy as np

s = np.array(list(map(int , input())))
n = np.count_nonzero(s == 0)
print(2 * min(len(s)-n, n))
### BUGGY CODE ###

n=int(input())

count=0

while True:
    if n-3>=3:
        count+=1
    
    if n<3:
        print(count)
        break


### FIXED CODE ###

n=int(input())

print(n//3)
### BUGGY CODE ###

from numpy import int32,zeros,arange
def solve(s):
    a=0
    d=zeros(2019,int32)
    for i in s:
        p=zeros(2019,int32)
        p[(arange(2019)*10+i)%2019]+=d[arange(2019)]
        d=p
        d[i]+=1
        a+=d[0]
    return a
print(solve(int32([*input()])))

### FIXED CODE ###

a,*d=[0]*2020
for i in map(int,input()):
  p=[0]*2019
  for j in range(2019):p[(j*10+i)%2019]+=d[j]
  d=p
  d[i]+=1
  a+=d[0]
print(a)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
import math
from itertools import permutations, combinations
from collections import deque

sys.setrecursionlimit(10**7)
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]

edges = [[] for _ in range(N)]
for abi in ab:
    a, b = abi[0], abi[1]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

K = max(list(map(len, edges)))
print(K)

adjm = [[0]*N for _ in range(N)]

Q = deque()
for edge in edges[0]:
    Q.append((0, edge))

while Q:
    labels = set(i for i in range(1, K+1))
    points = Q.popleft()
    p0, p1 = points

    set1 = set(adjm[p0])
    can_use_labels = labels - set1
    use_label = can_use_labels.pop()

    adjm[p0][p1] = use_label
    adjm[p1][p0] = use_label

    for p in edges[p1]:
        if p != p0:
            Q.append((p1, p))

for abi in ab:
    a, b = abi[0], abi[1]
    print(adjm[a-1][b-1])
        


### FIXED CODE ###

#import numpy as np
from copy import deepcopy
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N = int(input())
#AB = [list(map(int, input().split())) for _ in range(N-1)]
edge = [[] for i in range(N)]
seen = [0]*N
colors = [0]*(N-1)
#for val in AB:
for i in range(N-1):
    x, y = list(map(int, input().split()))
    edge[x-1].append((i, y-1))
    edge[y-1].append((i, x-1))

lenedge = [len(val) for val in edge]
mledge = max(lenedge)
root = lenedge.index(mledge)
print(mledge)


que = deque()
que.append([(root, -1)])
while que[0]:
    nque = []
    cque = que.popleft()
    #print('cstack:', cstack)
    for tupl in cque:
        index, pcolor = tupl
        seen[index] = 1
        color = 1
        if (color == pcolor): color += 1
        for tupl2 in edge[index]:
            findex, edgei = tupl2
            if seen[edgei] == 0:
                nque.append((edgei, color))
                colors[findex] = color
                color += 1
                if (color == pcolor): color += 1
    que.append(nque)

#pri(color)

for color in colors:
    print(color)
### BUGGY CODE ###

a, b, k = [int(i) for i in input().split()]
for i in range(k):
    if a >= 1: a -= 1
    elif b >= 1: b -= 1
print(a, b)

### FIXED CODE ###

a, b, k = [int(i) for i in input().split()]
if a >= k:
    a = a - k
elif b >= k - a:
    b = b - k + a
    a = 0
else:
    a = 0
    b = 0
print(a,b)
### BUGGY CODE ###

from collections import Counter
import sys
read_=sys.stdin.buffer.readline

N=int(read_())
S=[Counter(list(input())) for _ in range(N)]

ans=0

for i in range(N-1):
    for j in range(i+1,N):
        if S[i]==S[j]:
            ans+=1
print(ans)

### FIXED CODE ###

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

n = int(input())

ans = 1
for i in range(1, n+1):
  ans *= i
ans %= (10 ** 9 + 7)
print(ans)

### FIXED CODE ###

import numpy as np
n = int(input())

ans = 1
for i in range(1, n+1):
  ans *= i
  ans %= (10**9 + 7)
  
print(ans)
### BUGGY CODE ###

from collections import deque
import sys
input=sys.stdin.readline


def BFS():
    point=0
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[0 for _ in range(w)] for _ in range(h)]

    queue=deque([])
    for i in range(h):
        for j in range(w):
            if A[i][j]=="#":
                queue.append([i,j])
                D[i][j]=0

    while len(queue)>0:
        x,y=queue.popleft()
        for a,b in [[1,0],[-1,0],[0,1],[0,-1]]:
            X,Y=x+a,y+b
            if 0<=X<h and 0<=Y<w:
                if color[X][Y]!="black":
                    color[X][Y]="gray"
                    D[X][Y]=D[x][y]+1
                    point=max(point,D[X][Y])
                    queue.append([X,Y])
        color[x][y]="black"

    return point


h,w=map(int,input().split())
A=[list(input()) for _ in range(h)]
print(BFS())

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**7)
inf=10**7


def BFS():
    color=[["white" for _ in range(w+2)] for _ in range(h+2)]
    D=[[inf for _ in range(w+2)] for _ in range(h+2)]

    queue=deque([])
    for i in range(1,h+1):
        for j in range(1,w+1):
            if A[i][j]=="#":
                queue.append([i,j])
                D[i][j]=0
                color[i][j]="gray"

    cnt=0
    while len(queue)!=0:
        a,b=queue.popleft()
        for c,d in ((1,0),(0,1),(-1,0),(0,-1)):
            X,Y=a+c,b+d
            if A[X][Y]=="." and color[X][Y]=="white":
                color[X][Y]="gray"
                D[X][Y]=D[a][b]+1
                cnt=max(cnt,D[X][Y])
                queue.append([X,Y])
        color[a][b]="black"

    return cnt


h,w=map(int,input().split())
A=[["#"]+list(input())+["#"] for _ in range(h)]
A.insert(0,["#"]*(w+2))
A.append(["#"]*(w+2))
print(BFS())
### BUGGY CODE ###


n = input()
t = len(n)
total = 0
for i in range(t-4):
    for j in range(i+4,t):
        k = (n[i:j+1])
        l = int(k)
        #print(l)
        if l%2019 == 0:
            total += 1

print(total)

### FIXED CODE ###

S = input()[::-1]
ans = 0
mods = [0] * 2019
mods[0] = 1
current = 0
x = 1
for s in S:
    current = (current + x * int(s)) % 2019
    ans += mods[current % 2019]
    mods[current % 2019] += 1
    x = x * 10 % 2019
print(ans)