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

# -*- coding: utf-8 -*-
"""
Created on Fri Jan  4 20:10:14 2019

@author: Yamazaki Kenichi
"""

N, M= map(int,input().split())

#P,Y = [input().split() for i in range(M)]
#P = [int(P[i]) for i in range(M)]
#Y = [int(Y[i]) for i in range(M)]

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

#counta = [0]*N
a = [[] for i in range(N)]
for j in range(M):
#    for i in range(1,N+1):
#        if C[j][0] == i:
#            counta[i-1] +=1
    a[C[j][0]-1].append(C[j][1])

for i in range(N):
    a[i].sort()

ans = []
for j in range(M):
        
    l = '0'*(6-len(str(C[j][0])))+str(C[j][0])
    r1 = a[C[j][0]-1].index(C[j][1])+1
    r = '0'*(6-len(str(r1)))+str(str(r1))
    ans = l + r 
    print(ans)



### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Fri Jan  4 20:10:14 2019

@author: Yamazaki Kenichi
"""
import bisect

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

a = [[] for i in range(N)]
for j in range(M):
    a[C[j][0]-1].append(C[j][1])

for i in range(N):
    a[i].sort()

ans = []
for j in range(M):
    l = '0'*(6-len(str(C[j][0])))+str(C[j][0])
    r1 = bisect.bisect_left(a[C[j][0]-1],(C[j][1]))+1
    r = '0'*(6-len(str(r1)))+str(str(r1))
    ans = l + r 
    print(ans)
### BUGGY CODE ###

def main():
    n,q = map(int, input().split())
    S = input()
    array = [list(map(int,input().split())) for _ in range(q)]

    for i in range(q):
        count = 0
        S_temp = S[array[i][0]-1:array[i][1]]
        S_temp_len = len(S_temp)
        for j in range(S_temp_len-1):
            if S_temp[j:j+2] == 'AC':
                count += 1
        print(count)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n,q = map(int, input().split())
    S = input()
    N = [0]*(n+1)

    for i in range(n):
        N[i+1] += N[i]
        if S[i:i+2] == 'AC':
            N[i+1] += 1
    for i in range(q):
        l,r = map(int,input().split())
        print(N[r-1]-N[l-1])


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

N, K = map(int, input().split())
h = list(map(int, input().split()))
inf = float("inf")
dp = [inf] * N
dp[0] = 0


def chmin(table: list, num: int, sbn: int):
    table[num + sbn] = min((table[num + sbn], table[num] + abs(h[i + sbn] - h[num])))


for i in range(N):
    for sbn in range(K):
        try:
            chmin(dp, i, sbn + 1)
        except IndexError:
            break
print(dp[-1])


### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
inf = 10**9
dp = [inf] * N
dp[0] = 0


def chmin(num: int, sbn: int):
    dp[num + sbn] = min((dp[num + sbn], dp[num] + abs(h[i + sbn] - h[num])))


for i in range(N):
    for sbn in range(K):
        try:
            chmin(i, sbn + 1)
        except IndexError:
            break
print(dp[-1])
### BUGGY CODE ###

n = int(input())
s = input()

count_w =[s[:i].count('W') for i in range(n)]
count_e =[s[::-1][:i].count('E') for i in range(n)]

ninzu = n
for i in range(n):
    ninzu = min(ninzu, count_w[i]+count_e[-(i+1)])
print(ninzu)

### FIXED CODE ###

n = int(input())
s = input()

ruiseki_w = [0]
ruiseki = 0
for i in s[:-1]:
    if i == 'W':
        ruiseki += 1
        ruiseki_w.append(ruiseki)
    else:
        ruiseki_w.append(ruiseki)

ruiseki_e = [0]
ruiseki = 0
for i in s[::-1][:-1]:
    if i == 'E':
        ruiseki += 1
        ruiseki_e.append(ruiseki)
    else:
        ruiseki_e.append(ruiseki)
ruiseki_e.reverse()
        
ninzu = [ruiseki_w[i] + ruiseki_e[i] for i in range(n)]
print(min(ninzu))
### BUGGY CODE ###

N = int(input())
S = input()
color = [[], [], []]
for i in range(N):
    if S[i] == 'R':
        color[0].append(i)
    elif S[i] == 'G':
        color[1].append(i)
    elif S[i] == 'B':
        color[2].append(i)
rn = len(color[0])
gn = len(color[1])
bn = len(color[2])
mi = 0
for i in color[0]:
    for j in color[1]:
        for k in color[2]:
            if k == 2*j-i:
                mi += 1
            if k == (j-i)/2+i:
                mi += 1
            if k == 2*i-j:
                mi += 1
print(rn*gn*bn-mi)

### FIXED CODE ###

N = int(input())
S = input()
color = [[], [], []]
for i in range(N):
    if S[i] == 'R':
        color[0].append(i)
    elif S[i] == 'G':
        color[1].append(i)
    elif S[i] == 'B':
        color[2].append(i)
rn = len(color[0])
gn = len(color[1])
bn = len(color[2])
mi = 0
for i in range(N):
    p = 0
    while i + 2*p <= N-1:
        if S[i] != S[i+p] and S[i+p] != S[i+2*p] and S[i] != S[i+2*p]:
           mi += 1
        p += 1
print(rn*gn*bn-mi)
### BUGGY CODE ###

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

count = {}
for a in A:
    count[a] = count.get(a, 0) + 1

q = int(input())
result = []
for i in range(q):
    b, c = list(map(int, input().split()))
    if count.get(b):
        count[c] = count.get(c, 0) + count.pop(b)
    sum = 0
    for key, value in count.items():
        sum += key * value
    result.append(str(sum))
print('\n'.join(result))

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
num = [0] * (10 ** 5 + 1)

for a in A:
    num[a] += 1
_sum = sum(A)

result = []
q = int(input())
for i in range(q):
    b, c = list(map(int, input().split()))
    _sum += (c - b) * num[b]
    num[c] += num[b]
    num[b] = 0
    result.append(str(_sum))
print('\n'.join(result))
### BUGGY CODE ###

N = int(input())
p = list(map(float,input().split()))

dp = [[0]*(N+1) for i in range(N+1)]

dp[0][0] = 1-p[0]
dp[0][1] = p[0]

for i in range(1,N):
  dp[i][0] = dp[i-1][0]*(1-p[i])
  for j in range(1,i+2):
    dp[i][j] = dp[i-1][j]*(1-p[i]) + dp[i-1][j-1]*p[i]
    
ans=0
A=int((N+1)/2)

for j in range(A,N+1):
   ans += dp[N-1][j]
    
print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(float,input().split()))

#dp[投げたコイン枚数][表のコイン枚数] 
dp = [[0]*(n+1) for i in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
  dp[i][0] = dp[i-1][0]*(1-p[i-1])
  dp[i][i] = dp[i-1][i-1]*p[i-1]
  for j in range(1,i):
    dp[i][j] = dp[i-1][j]*(1-p[i-1])+dp[i-1][j-1]*p[i-1]
print(sum(dp[n][(n+1)//2:]))
### BUGGY CODE ###

import sys
import math
import collections
from collections import deque
#n = int(input())
#a, b = map(int, input().split())
s = input()
#x = list(map(int, input().split()))
q = int(input())
d = deque([])
for i in range(len(s)):
    d.append(s[i])

rev = 1
for i in range(q):
    que = sys.stdin.readline().split()
    if que[0] == "1":
        rev *= -1

    else:
        if rev == 1:
            if que[1] == "1":
                d.appendleft(que[2])
            else:
                d.append(que[2])

        else:
            if que[1] == "1":
                d.append(que[2])
            else:
                d.appendleft(que[2])


if rev == 1:
    for i in range(len(d)):
        print(d[i], end="")
else:
    for i in range(len(d)):
        print(d[len(d) - i - 1], end="")




### FIXED CODE ###

import sys
import math
import collections
from collections import deque
def main():
    #n = int(input())
    #a, b = map(int, input().split())
    s = input()
    #x = list(map(int, input().split()))
    q = int(input())
    d = deque([])
    for i in range(len(s)):
        d.append(s[i])

    rev = 1
    for i in range(q):
        que = sys.stdin.readline().split()
        if que[0] == "1":
            rev *= -1

        else:
            if rev == 1:
                if que[1] == "1":
                    d.appendleft(que[2])
                else:
                    d.append(que[2])

            else:
                if que[1] == "1":
                    d.append(que[2])
                else:
                    d.appendleft(que[2])


    if rev == 1:
        for i in range(len(d)):
            print(d.popleft(), end="")
    else:
        for i in range(len(d)):
            print(d.pop(), end="")

main()
### BUGGY CODE ###

N = int(input())

l = 0
j = 0
r = N -1

print(0, flush=True)
a = input()
if a == 'Vacant':
  exit()
b = a
while r > l:
  i = (r + l)//2
  print(i, flush=True)
  a = input()
  if a == 'Vacant':
    exit()
  if abs(i-j)%2 == 0:
    if a == b:
      l = i + 1
    else:
      r = i - 1
  else:
    if a == b:
      r = i - 1
    else:
      l = i + 1
  b = a
  j = i
print(l, flush=True)

### FIXED CODE ###

N = int(input())

l = 0
j = 0
r = N -1

print(0, flush=True)
a = input()
if a == 'Vacant':
  exit()
b = a
while r - l > 1:
  i = (r + l)//2
  print(i, flush=True)
  a = input()
  if a == 'Vacant':
    exit()
  if abs(i-j)%2 == 0:
    if a == b:
      if i > j:
        l = i
      else:
        r = i
    else:
      if i > j:
        r = i
      else:
        l = i
  else:
    if a == b:
      if i > j:
        r = i
      else:
        l = i
    else:
      if i > j:
        l = i
      else:
        r = i
      
  b = a
  j = i

print(l, flush=True)
a = input()
if a == 'Vacant':
  exit()
  
print(r, flush=True)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
for i in range(N):
    if i!=0 and i!= N-1:
        ans = max(max(A[:i]),max(A[i+1:]))
    elif i == 0:
        ans = max(A[i+1:])
    else:
        ans = max(A[:i])
    print(ans)


### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
first = sorted(A)[-1]
second = sorted(A)[-2]
if first == second:
    for i in range(N):
        print(first)
else:
    idx = A.index(first)
    for i in range(N):
        if i == idx:
            print(second)
        else:
            print(first)
### BUGGY CODE ###

import itertools
N = int(input())
A =  list(map(int, input().split()))
r = 0
m = 10**9+7
for x in itertools.combinations(A, 2):
    r += x[0]*x[1]
    r = r % m
print(r)

### FIXED CODE ###

import itertools
N = int(input())
A =  list(map(int, input().split()))
sa = sum(A)
r = 0
xx = sa
m = 10**9+7
for x in A:
    xx -= x
    r += x*xx
    r = r % m
print(r)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N=int(input())
ans=0
for i in range(N):
    ans=ans+i
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
N=int(input())
ans=((N-1)**2-(N-1))//2+(N-1)
print(ans)
### BUGGY CODE ###

n,k,q = map(int,input().split())
score = [k for i in range(n)]

for i in range(q):
    a_i = int(input())-1
    for j in range(len(score)):
        if(j == a_i):
            pass
        else:
            score[j] -= 1
    

for i in range(len(score)):
    if(score[i] > 0):
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

import sys
n,k,q = map(int,input().split())
score = [k-q for i in range(n)]
a_i = [int(input())-1 for i in range(q)]


for i in range(len(a_i)):
    score[a_i[i]] += 1



for i in score:
    if(i > 0):
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n=int(input())
a_list=[0]
for i in range(n):
    a_list.append(int(input()))
S=sum(a_list)
dp=[]
dp_1=[]
mod=998244353
for i in range(n+1):
    sub_list=[0]*(S+1)
    dp.append(sub_list)
    sub_list=[0]*(S+1)
    dp_1.append(sub_list)
dp[0][0]=1
dp_1[0][0]=1
for i in range(1,n+1):
    for j in range(S+1):
        if j>=a_list[i]:
            dp[i][j]=(dp[i-1][j]*2+dp[i-1][j-a_list[i]])%mod
            dp_1[i][j]=dp_1[i-1][j]+dp_1[i-1][j-a_list[i]]
        else:
            dp[i][j]=dp[i-1][j]*2
            dp_1[i][j]=dp_1[i-1][j]
Sum=0
for i in range(S+1):
    if i>S/2:
        Sum=Sum+dp[n][i]*3
    elif i==S/2:
        Sum=Sum+dp[n][i]*3-dp_1[n][i]*3
ans=(pow(3,n,mod)-Sum)%mod
print(ans)



### FIXED CODE ###

n=int(input())
a_list=[0]
for i in range(n):
    a_list.append(int(input()))
S=sum(a_list)
dp=[]
dp_1=[]
mod=998244353
for i in range(n+1):
    sub_list=[0]*(S+1)
    dp.append(sub_list)
    sub_list=[0]*(S+1)
    dp_1.append(sub_list)
dp[0][0]=1
dp_1[0][0]=1
for i in range(1,n+1):
    for j in range(S+1):
        if j>=a_list[i]:
            dp[i][j]=(dp[i-1][j]*2+dp[i-1][j-a_list[i]])%mod
            dp_1[i][j]=(dp_1[i-1][j]+dp_1[i-1][j-a_list[i]])%mod
        else:
            dp[i][j]=dp[i-1][j]*2%mod
            dp_1[i][j]=dp_1[i-1][j]%mod
Sum=0
for i in range(S+1):
    if i>S/2:
        Sum=(Sum+dp[n][i]*3)%mod
    elif i==S/2:
        Sum=Sum+dp[n][i]*3-dp_1[n][i]*3
ans=(pow(3,n,mod)-Sum)%mod
print(ans)
### BUGGY CODE ###

import numpy as np
MOD = 10**9 + 7
def solve(s, p=13):
    s = s[::-1]
    n = len(s)
    cur = np.zeros(p, dtype=np.uint64)
    if s[0] == "?":
        cur[:10] = 1
    else:
        cur[int(s[0])] = 1
    D = {str(i): [i] for i in range(10)}
    D["?"] = list(range(10))
    q = [(10**i) % p for i in range(6)]
    for i in range(1,n):
        next = np.zeros(p, dtype=np.uint64)
        for x in D[s[i]]:
            for j in range(p):
                k = (j + x * q[i%6]) % p
                next[k] += cur[j]
        cur = next % MOD
    return cur[5]

s = input()
print(solve(s))

### FIXED CODE ###

MOD = 10**9 + 7

def solve(s, p=13):
    a = [0] * p
    a[0] = 1
    for c in s:
        b = [0] * p
        for i in range(p):
            b[(i*10)%p] = a[i] % MOD
        b += b
        if c == "?":
            for i in range(p):
                a[i] = sum(b[i+4:i+p+1])
        else:
            for i in range(p):
                a[i] = b[i+p-int(c)]
    return a[5] % MOD

s = input()
print(solve(s))
### BUGGY CODE ###

import numpy as np
import math
X,Y = map(int,input().split())
 
 
c1 = (2*Y-X)
if c1%3!=0:
  print(0)
 
else:
  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
  
  c1 = c1//3
  c2 = Y-2*c1
  c3 = c1+c2+1
  mod = 10**9+7
  c4 = min(c1,c2)
  x = 1
  y = 1
  for i in range(1,c4+1):
    x = (x * (c3-i)) % mod
    y = (y * i) % mod
    
  result = 1
  for _ in range(mod-2):
    result = (result * y) % mod
    
  result = (result * x) % mod
 
  print(result)

### FIXED CODE ###

import numpy as np
import math
X,Y = map(int,input().split())


c1 = (2*Y-X)
if c1%3!=0:
  print(0)

else:
  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
  
  c1 = c1//3
  c2 = Y-2*c1
  c3 = c1+c2
  mod = 10**9+7
  g1 = [1, 1]
  g2 = [1, 1]
  inverse = [0, 1]
  for i in range( 2,c3+1):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

  a = cmb(c3,c1,mod)

  print(a)
### BUGGY CODE ###

#!/usr/bin/env python3
n, m = map(int, input().split())

w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [0] * (m + 1)
for j in range(w[0], m + 1):
    dp[j] = v[0]

for i in range(n - 1):
    vi = v[i + 1]
    wi = w[i + 1]
    for j in reversed(range(w[i + 1], m + 1)):
        dp[j] = max(vi + dp[j - wi], dp[j])

print(dp[-1])


### FIXED CODE ###

#!/usr/bin/env python3
import sys, os
range = xrange

def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]

    w, v = inp[2::2], inp[3::2]

    dp = [0] * (m + 1)
    for j in range(w[0], m + 1):
        dp[j] = v[0]

    for i in range(n - 1):
        vi = v[i + 1]
        wi = w[i + 1]
        for j in reversed(range(wi, m + 1)):
            dp[j] = max(vi + dp[j - wi], dp[j])

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
for _ in range(M):
    A.sort()
    B, C = map(int, input().split())
    i = 0
    while i < B:
        if A[i] < C:
            A[i] = C
            i += 1
        else:
            break
        
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
array = []
for _ in range(M):
    tmp = list(map(int, input().split()))
    array.append(tmp)
array.sort(key=lambda x: x[1], reverse=True)

_sum = 0
_num = 0

for i in range(N+M):
    if A[0] > array[0][1]:
        _sum += A.pop(0)
        _num += 1
        
    else:
        a = array[0][0] if array[0][0] < N - _num else N - _num
        _sum += array.pop(0)[1] * a
        _num += a
        if not array:
            break
        
    if _num == N:
        break
    
if _num != N:
    while _num < N:
        _sum += A.pop(0)
        _num += 1
        
print(_sum)
### BUGGY CODE ###

import fractions
from functools import reduce


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm(numbers):
    return reduce(lcm_base, numbers, 1)

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

l = lcm(a)
answer = 0
for aa in a:
    answer += l // aa
    answer = answer % (10 ** 9 + 7)

print(answer)


### FIXED CODE ###

# import math
# import fractions

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

mod = 10 ** 9 + 7


def prime_factorize(n):
    a = {}
    while n % 2 == 0:
        if 2 not in a:
          a[2] = 0
        a[2] += 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            if f not in a:
              a[f] = 0
            a[f] += 1
            n //= f
        else:
            f += 2
    if n != 1:
      if n not in a:
        a[n] = 0
      a[n] += 1
    return a


# 最小公倍数を素因数分解した形で持つ
l = prime_factorize(a[0])
# print(l)
# xs = {}
# xs[a[0]] = prime_factorize(a[0])
for i in range(1, n):
  ps = prime_factorize(a[i])
  # print(ps)
  # xs[a[i]] = ps
  for k, v in ps.items():
    if k in l:
      l[k] = max(v, l[k])
    else:
      l[k] = v

# print(l)
# print(xs)

L = 1
for k, v in l.items():
  L = L * pow(k, v, mod) % mod

answer = 0
for x in a:
  answer = (answer + L * pow(x, mod - 2, mod)) % mod
print(answer)
### BUGGY CODE ###

N = int(input())
nums = [int(input()) for _ in range(N)]

i = 0
n = N
while i < n:
    num = nums[i]
    cnt = nums.count(num)
    if cnt == 1:
        i += 1
    elif cnt % 2 == 0:
        for _ in range(cnt):
            nums.remove(num)
        i += 1
        n = len(nums)
    else:
        for _ in range(cnt-1):
            nums.remove(num)
        i += 1
        n = len(nums)

print(n)

### FIXED CODE ###

n = int(input())
nums = [int(input()) for _ in range(n)]
cnt = {}
ans = 0
for x in nums:
    if x not in cnt:
        cnt[x] = 1
    else:
        cnt[x] += 1
for y in cnt.values():
    if y % 2 != 0:
        ans += 1

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

'''
参考: https://beta.atcoder.jp/contests/agc026/submissions/2849460
'''

n = int(input())
s = input()

s_left = s[:n]
s_right = s[n:]
m = dict()

for i in range(1 << n):
    s_red, s_blue = '', ''
    for j in range(n):
        if i & (1 << j):
            s_red = s_red  + s_left[j]
        else:
            s_blue = s_left[j] + s_blue
    if (s_red, s_blue) in m:
        m[(s_red, s_blue)] += 1
    else:
        m[(s_red, s_blue)] = 1

ans = 0
for i in range(1 << n):
    s_red, s_blue = '', ''
    for j in range(n):
        if i & (1 << j):
            s_red = s_right[j] + s_red
        else:
            s_blue = s_blue + s_right[j]
   
    if (s_red, s_blue) in m:
        ans += m[(s_red, s_blue)]
print(ans)


### FIXED CODE ###

def main():
    from collections import defaultdict

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

    L, R = S[:N], S[N * 2 - 1:N - 1:-1]

    def make_counter(s: str) -> defaultdict(int):
        ret = defaultdict(int)
        for bit in range(1 << N):
            red, blue = '', ''
            for j in range(N):
                if (bit >> j) & 1:
                    red += s[j]
                else:
                    blue += s[j]

            ret[red + '_' + blue] += 1
        return ret

    ld = make_counter(L)
    rd = make_counter(R)

    print(sum(ld[key] * rd[key] for key in ld))


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

R, C, k = map(int, input().split())
grid = [[0] * C for _ in range(R)]

for _ in range(k):
    ri, ci, v = map(int, input().split())
    grid[ri - 1][ci - 1] = v


dp = []
for _ in range(4):
    dp.append([[0] * (C + 1) for _ in range(R + 1)])


mx = 0
for row in range(1, R + 1):
    for col in range(1, C + 1):
        for level in range(4):
            dp[0][row][col] = max(dp[0][row][col], dp[level][row - 1][col])
            dp[1][row][col] = max(dp[1][row][col], dp[level][row - 1][col] + grid[row - 1][col - 1])
        for level in range(1, 4):
            dp[level][row][col] = max(
                dp[level][row][col],
                dp[level - 1][row][col - 1] + grid[row - 1][col - 1],
                dp[level][row][col - 1],
            )
            mx = max(mx, dp[level][row][col])

print(mx)


### FIXED CODE ###

import sys
import time
s1 = time.time()
*data, = map(int, sys.stdin.read().split()[::-1])

def inp():
    global data
    return data.pop()
R, C, k = inp(), inp(), inp()
grid = [[0] * C for _ in range(R)]

for _ in range(k):
    ri, ci, v = inp(), inp(), inp()
    grid[ri - 1][ci - 1] = v


dp = []
for _ in range(4):
    dp.append([[0] * (C + 1) for _ in range(R + 1)])

# print(time.time() - s1)
mx = 0
for row in range(1, R + 1):
    for col in range(1, C + 1):
        level = 0
        dp[1][row][col] = max(dp[1][row][col], dp[3][row - 1][col] + grid[row - 1][col - 1])
        dp[0][row][col] = max(dp[0][row][col], dp[3][row - 1][col])
        level = 1
        v = grid[row - 1][col - 1]
        while level < 4:
            dp[level][row][col] = max(
                dp[level - 1][row][col],
                dp[level][row][col],
                dp[level][row][col - 1],
                dp[level - 1][row][col - 1] + v,
            )
            mx = max(mx, dp[level][row][col])
            level += 1

# print(time.time() - s1)
print(mx)
### BUGGY CODE ###

import collections

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

S = input()[::-1]
keta = 1
A_num = 0
x = 0
mod = [0]*2019
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[0])
x += ConZ(mod[0])
del mod[0]

for j in range(len(mod)):
    x+=ConN(mod[j])
print(x)

### 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 ###

K = str(input())
S = '7'*len(K)
ans = 0

if int(K)%2 == 0 or int(K)%5 == 0:
    ans = 2

while ans == 0:
    if int(S)%int(K) == 0:
        ans = 1
    else:
        S += '7'

if ans == 1:
    print(len(S))
else:
    print('-1')


### FIXED CODE ###

k = int(input())
ans = 7%k

for i in range(1, 10**6 + 1):
  if ans%k == 0:
    print(i)
    exit()
  else:
    ans = (ans*10 + 7)%k
print(-1)
### BUGGY CODE ###

import math

def convert_bagOfWords(S):
    BOW = [0 for i in range(26)]

    for s in S:
        num = (ord(s) - ord('a')) % 26
        BOW[num] += 1
    
    return(BOW)

N = int(input())
bow_vec = []
N_anagram = [0] * N
new_words = []

for i in range(N):
    bow_vec.append(convert_bagOfWords(input()))

for i in range(N):
    # if (new_words.any(bow_vec[i]) == True):
    if (sum(s == bow_vec[i] for s in new_words) > 0):
        index = new_words.index(bow_vec[i])
        N_anagram[index] += 1
    
    else:
        new_words.append(bow_vec[i])

N_anagram = [i+1 for i in N_anagram if (i > 0)]

answer = 0

for i in N_anagram:
    answer += math.factorial(i) / (2 * math.factorial(i - 2))

print(int(answer))

### FIXED CODE ###

N = int(input())
l = []

for i in range(N):
    l.append(''.join(sorted(input())))

l.sort()
count = ans = 0

for i in range(N-1):
    if (l[i] == l[i+1]):
        count += 1
        ans += count
    else:
        count = 0

print(ans)