Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
S = list(str(input()))
S = [int(s) for s in S]
n = len(S)

S.reverse()

cum1 = [-1]*(n+1)
cum1[0] = 0
for i in range(n):
    temp = cum1[i]+S[i]*10**i
    cum1[i+1] = temp%673
#print(cum1)

cum2 = [-1]*(n+1)
cum2[0] = 0
for i in range(n):
    temp = cum2[i]+S[i]*10**i
    cum2[i+1] = temp%3
#print(cum2)

d = {}
ans = 0
for i in range(n+1):
    c1 = cum1[i]
    c2 = cum2[i]
    if (c1, c2) in d:
        ans += d[(c1, c2)]
        d[(c1, c2)] += 1
    else:
        d[(c1, c2)] = 1
print(ans)


Fixed submission:
S = list(str(input()))
S = [int(s) for s in S]
n = len(S)

S.reverse()

def power(a, n, mod):
  bi=str(format(n,"b")) #2進数
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res

cum1 = [-1]*(n+1)
cum1[0] = 0
for i in range(n):
    temp = cum1[i]+S[i]*power(10, i, 673)
    cum1[i+1] = temp%673
#print(cum1)

cum2 = [-1]*(n+1)
cum2[0] = 0
for i in range(n):
    temp = cum2[i]+S[i]*power(10, i, 3)
    cum2[i+1] = temp%3
#print(cum2)

d = {}
ans = 0
for i in range(n+1):
    c1 = cum1[i]
    c2 = cum2[i]
    if (c1, c2) in d:
        ans += d[(c1, c2)]
        d[(c1, c2)] += 1
    else:
        d[(c1, c2)] = 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S = list(str(input()))
n = len(S)

S.reverse()

cum1 = [-1]*(n+1)
cum1[0] = 0
for i in range(n):
    temp = cum1[i]+int(S[i])*10**i
    cum1[i+1] = temp%673
#print(cum1)

cum2 = [-1]*(n+1)
cum2[0] = 0
for i in range(n):
    temp = cum2[i]+int(S[i])*10**i
    cum2[i+1] = temp%3
#print(cum2)

d1 = {}
d2 = {}
ans = 0
for i in range(n+1):
    if cum1[i] in d1 and cum2[i] in d2:
        temp = d1[cum1[i]] & d2[cum2[i]]
        ans += len(temp)
    if cum1[i] not in d1:
        d1[cum1[i]] = {i}
    else:
        d1[cum1[i]].add(i)
    if cum2[i] not in d2:
        d2[cum2[i]] = {i}
    else:
        d2[cum2[i]].add(i)
print(ans)


Fixed submission:
S = list(str(input()))
S = [int(s) for s in S]
n = len(S)

S.reverse()

def power(a, n, mod):
  bi=str(format(n,"b")) #2進数
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res

cum1 = [-1]*(n+1)
cum1[0] = 0
for i in range(n):
    temp = cum1[i]+S[i]*power(10, i, 673)
    cum1[i+1] = temp%673
#print(cum1)

cum2 = [-1]*(n+1)
cum2[0] = 0
for i in range(n):
    temp = cum2[i]+S[i]*power(10, i, 3)
    cum2[i+1] = temp%3
#print(cum2)

d = {}
ans = 0
for i in range(n+1):
    c1 = cum1[i]
    c2 = cum2[i]
    if (c1, c2) in d:
        ans += d[(c1, c2)]
        d[(c1, c2)] += 1
    else:
        d[(c1, c2)] = 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, p = map(int, input().split())
s =list(str(input()))
s = [int(c) for c in s]
s.reverse()

if p == 2 or p == 5:
    ans = 0
    for i in range(n):
        if s[i]%p == 0:
            ans += n-1-i+1
    print(ans)
    exit()


#print(s)

#s = [0] + s
#from itertools import accumulate
#cum =list(accumulate(s))
#cum = [c%p for c in cum]

def power(a, n, mod):
  bi=str(format(n,"b")) #2進数
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res

temp = 0
cum = [0]*n
for i in range(n):
    temp += s[i]*10**i
    temp += s[i]*power(10, i, p)
    temp = temp%p
    cum[i] = temp
cum = [0]+cum

#print(cum)

d = {}
ans = 0
for i in range(n+1):
  if cum[i] not in d:
    d[cum[i]] = 1
  else:
    ans += d[cum[i]]
    d[cum[i]] += 1
print(ans)


Fixed submission:
n, p = map(int, input().split())
s =list(str(input()))
s = [int(c) for c in s]
s.reverse()

if p == 2 or p == 5:
    ans = 0
    for i in range(n):
        if s[i]%p == 0:
            ans += n-1-i+1
    print(ans)
    exit()


#print(s)

#s = [0] + s
#from itertools import accumulate
#cum =list(accumulate(s))
#cum = [c%p for c in cum]

def power(a, n, mod):
  bi=str(format(n,"b")) #2進数
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res

temp = 0
cum = [0]*n
for i in range(n):
    temp += s[i]*power(10, i, p)
    temp = temp%p
    cum[i] = temp
cum = [0]+cum

#print(cum)

d = {}
ans = 0
for i in range(n+1):
  if cum[i] not in d:
    d[cum[i]] = 1
  else:
    ans += d[cum[i]]
    d[cum[i]] += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n, p = map(int, input().split())
s =list(str(input()))
s = [int(c) for c in s]
s.reverse()

if p == 2 or p == 5:
    ans = 0
    for i in range(n):
        if s[i]%p == 0:
            ans += n-1-i+1
    print(ans)
    exit()


#print(s)

#s = [0] + s
#from itertools import accumulate
#cum =list(accumulate(s))
#cum = [c%p for c in cum]
temp = 0
cum = [0]*n
for i in range(n):
    temp += s[i]*10**i
    cum[i] = temp
    cum[i] = cum[i]%p
cum = [0]+cum

#print(cum)

d = {}
ans = 0
for i in range(n+1):
  if cum[i] not in d:
    d[cum[i]] = 1
  else:
    ans += d[cum[i]]
    d[cum[i]] += 1
print(ans)


Fixed submission:
n, p = map(int, input().split())
s =list(str(input()))
s = [int(c) for c in s]
s.reverse()

if p == 2 or p == 5:
    ans = 0
    for i in range(n):
        if s[i]%p == 0:
            ans += n-1-i+1
    print(ans)
    exit()


#print(s)

#s = [0] + s
#from itertools import accumulate
#cum =list(accumulate(s))
#cum = [c%p for c in cum]

def power(a, n, mod):
  bi=str(format(n,"b")) #2進数
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res

temp = 0
cum = [0]*n
for i in range(n):
    temp += s[i]*power(10, i, p)
    temp = temp%p
    cum[i] = temp
cum = [0]+cum

#print(cum)

d = {}
ans = 0
for i in range(n+1):
  if cum[i] not in d:
    d[cum[i]] = 1
  else:
    ans += d[cum[i]]
    d[cum[i]] += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
n, a, b = map(int, input().split())
mod = 10**9+7
 
def cmb2(n, r, mod):
    res = 1
    temp = 1
    for k in range(1, r+1):
        res *= (n-k+1)
        temp *= k
        res %= mod
        temp %= mod
    res *= pow(temp,(mod-2),mod)
    res %= mod
    return res

def power(a, n, mod):
  	bi=str(format(n,"b")) #2進数
  	res=1
  	for i in range(len(bi)):
    	res=(res*res) %mod
    	if bi[i]=="1":
      		res=(res*a) %mod
  	return res

ans = power(2, n, mod) - cmb2(n, a, mod) - cmb2(n, b, mod) -1
ans %= mod
print(ans)

Fixed submission:
n, a, b = map(int, input().split())
mod = 10**9+7

#print(x*pow(y,(mod-2),mod)%mod)

def conv(n, x, mod):
    X = 1
    for i in range(x):
        k = i+1
        X *= (n-k+1)*pow(k,(mod-2),mod)%mod
        X %= mod
    return X

def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

#print(conv(n, a, mod))
#print(conv(n, b, mod))

ans = power_func(2, n, mod) - conv(n, a, mod) - conv(n, b, mod) - 1
ans %= mod
print(ans)

Buggy python submission (verdict: Runtime Error):
n, a, b = map(int, input().split())
mod = 10**9+7

#print(x*pow(y,(mod-2),mod)%mod)

def conv(n, x, mod):
    X = 1
    for i in range(x):
        k = i+1
        X *= (n-k+1)*pow(k,(mod-2),mod)%mod
        X %= mod
    return X

def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

#print(conv(n, a, mod))
#print(conv(n, b, mod))

ans = power_func(2, n, mod) - conv(n, a, mod) - conv(n, b, mod) - 1
ans %= mod
print(ans)n, a, b = map(int, input().split())
mod = 10**9+7

#print(x*pow(y,(mod-2),mod)%mod)

def conv(n, x, mod):
    X = 1
    for i in range(x):
        k = i+1
        X *= (n-k+1)*pow(k,(mod-2),mod)%mod
        X %= mod
    return X

def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

#print(conv(n, a, mod))
#print(conv(n, b, mod))

ans = power_func(2, n, mod) - conv(n, a, mod) - conv(n, b, mod) - 1
ans %= mod
print(ans)

Fixed submission:
n, a, b = map(int, input().split())
mod = 10**9+7

#print(x*pow(y,(mod-2),mod)%mod)

def conv(n, x, mod):
    X = 1
    for i in range(x):
        k = i+1
        X *= (n-k+1)*pow(k,(mod-2),mod)%mod
        X %= mod
    return X

def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

#print(conv(n, a, mod))
#print(conv(n, b, mod))

ans = power_func(2, n, mod) - conv(n, a, mod) - conv(n, b, mod) - 1
ans %= mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
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

mod = 10**9+7 #出力の制限
N = 10**6 +1
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 )

if k >= n-1:
    print(cmb(2*n-1, n-1, mod))
    exit()

ans = 0
for i in range(k):
    j = i+1
    for r in range(1, j+1):
        ans += cmb(n, j, mod) * cmb(n-j, r, mod) * cmb(j-1, r-1, mod)
        ans %= mod
    #if j >= 2:
        #ans += 1
        #ans %= mod
print(ans+1)


Fixed submission:

def cmb1(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

mod = 10**9+7 #出力の制限
N = 10**6
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 )

n, k = map(int, input().split())
mod = 10**9+7
ans = 0
k_ = min(n-1, k)
for i in range(k_+1):
    ans += cmb1(n, i, mod) * cmb1(n-i-1+i, i, mod)
    ans %= mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())
dp = [float('inf')]*(2*(10**4)+1)
dp[0] = 0
l = [list(map(int, input().split())) for _ in range(n)]

for i in range(n):
  for j in range(h):
    dp[j+l[i][0]] = min(dp[j+l[i][0]], dp[j]+l[i][1])
    
print(min(dp[h:]))

Fixed submission:
h, n = map(int, input().split())
dp = [float('inf')]*(2*(10**4)+1)
dp[0] = 0
l = [list(map(int, input().split())) for _ in range(n)]

for i in range(n):
  for j in range(h):
    dp[j+l[i][0]] = min(dp[j+l[i][0]], dp[j]+l[i][1])
    
print(min(dp[h:]))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = list(map(int, input().split()))

l.sort(reverse=True)
kmax = len(format(l[0], 'b'))

l0 = [0]*kmax
l1 = [0]*kmax

for i in range(n):
  a = format(l[i], 'b')
  a = ''.join(list(reversed(a)))
  for j in range(kmax):
    if j > len(a)-1:
      l0[j] += 1
    elif a[j] == '0':
      l0[j] += 1
    else:
      l1[j] += 1

ans = 0
for k in range(kmax):
  ans += l0[k]*l1[k]*(2**k)
  ans %= 10**9+7
print(ans)

Fixed submission:
n = int(input())
l = list(map(int, input().split()))

l.sort(reverse=True)
kmax = len(format(l[0], 'b'))

l0 = [0]*kmax
l1 = [0]*kmax

for i in range(n):
  a = format(l[i], 'b')
  a = ''.join(list(reversed(a)))
  for j in range(kmax):
    if j > len(a)-1:
      l0[j] += 1
    elif a[j] == '0':
      l0[j] += 1
    else:
      l1[j] += 1

ans = 0
for k in range(kmax):
  ans += l0[k]*l1[k]*(2**k)
  ans %= 10**9+7
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
g = [[] for _ in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  g[a].append([b, i])
  g[b].append([a, i])
  
ans = [0]*(n-1)
  
def dfs(v, c=-1, p=-1):
  k = 1
  for u, ei in g[v]:
    if u == p:
      continue
    if k == c:
      k += 1
    ans[ei] = k
    k += 1
    dfs(u, ans[ei], v)

dfs(0)
print(max(ans))
for i in range(n-1):
  print(ans[i])

Fixed submission:
import sys
sys.setrecursionlimit(1000000)

n = int(input())
g = [[] for _ in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  g[a].append([b, i])
  g[b].append([a, i])
  
ans = [0]*(n-1)
  
def dfs(v, c=-1, p=-1):
  k = 1
  for u, ei in g[v]:
    if u == p:
      continue
    if k == c:
      k += 1
    ans[ei] = k
    k += 1
    dfs(u, ans[ei], v)
 
dfs(0)
print(max(ans))
for i in range(n-1):
  print(ans[i])
Buggy python submission (verdict: Time Limit Exceeded):
n, t = map(int, input().split())
l = [[0, 0] for _ in range(n)]
 
for i in range(n):
  a, b = map(int, input().split())
  l[i][0] = a
  l[i][1] = b

l.sort()
#print(l)

ans = 0
dp = [[0]*(t+1) for _ in range(n+1)]
for i in range(n):
  for j in range(t):
    dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    nj = j+l[i][0]
    if nj < t:
      dp[i+1][nj] = max(dp[i+1][nj], dp[i][j]+l[i][1])
  now = dp[i][t-1] + l[i][1]
  ans = max(ans, now)
#print(dp)
print(ans)

Fixed submission:
n, t = map(int, input().split())
l = [[0, 0] for _ in range(n)]
 
for i in range(n):
  a, b = map(int, input().split())
  l[i][0] = a
  l[i][1] = b

l.sort()
#print(l)

ans = 0
dp = [[0]*(t+1) for _ in range(n+1)]
for i in range(n):
  for j in range(t):
    dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    nj = j+l[i][0]
    if nj < t:
      dp[i+1][nj] = max(dp[i+1][nj], dp[i][j]+l[i][1])
  now = dp[i][t-1] + l[i][1]
  ans = max(ans, now)
#print(dp)
print(ans)
Buggy python submission (verdict: Runtime Error):
a, b, x = map(int, input().split())

if x <= a**2*b/2:
  t = (2*x)/(a*b**2)
else:
  t = (a**3)/(2*(a**2*b-x))
#print(t)

import math
a = math.atan(t)
a = math.degrees(a)
print(90-a)


Fixed submission:
a, b, x = map(int, input().split())

if x == a**2*b:
  print(0)
  exit()

if x <= a**2*b/2:
  t = (2*x)/(a*b**2)
else:
  t = (a**3)/(2*(a**2*b-x))
#print(t)

import math
a = math.atan(t)
a = math.degrees(a)
print(90-a)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
a = list(map(int, input().split()))
f = list(map(int, input().split()))

a.sort()
f.sort(reverse=True)

l = -1
r = 10**12

while l+1 < r:
  c = (l+r)//2
  s = 0
  for i in range(n):
    s += max(0, a[i] - c//f[i])
  if s <= k:
    r = c
  else:
    l = c
print(r)


Fixed submission:
n, k = map(int, input().split())
a = list(map(int, input().split()))
f = list(map(int, input().split()))

a.sort()
f.sort(reverse=True)

l = -1
r = 10**12

while l+1 < r:
  c = (l+r)//2
  s = 0
  for i in range(n):
    s += max(0, a[i] - c//f[i])
  if s <= k:
    r = c
  else:
    l = c
print(r)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = list(map(int, input().split()))

l.sort(reverse=True)
#print(l)

ans = 0
for i in range(n-2):
  a = l[i]
  for j in range(i+1,n-1):
    b = l[j]
    for k in range(j+1, n):
      c = l[k]
      if a<b+c:
        #print(a, b, c)
        ans += 1
      else:
        break

print(ans)


Fixed submission:
n = int(input())
l = list(map(int, input().split()))

l.sort(reverse=True)
m = sorted(l)
#print(l)
# print(m)

import bisect

ans = 0
for i in range(n-2):
  a = l[i]
  for j in range(i+1,n-1):
    b = l[j]
    x = a-b
    ind = bisect.bisect_right(m,x)
    #print(a, b, j, ind)
    if n-1-j-ind >= 0:
      ans += n-1-j-ind

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def warshal_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j] = min(d[i][j], d[i][k]+d[k][j])
        
  return d

n, m, l = map(int, input().split())
d = [[float('inf') for i in range(n)] for j in range(n)]
for i in range(n):
  d[i][i] = 0

for i in range(m):
  a, b, c = map(int, input().split())
  a, b = a-1, b-1
  d[a][b] = c
  d[b][a] = c
  
d = warshal_floyd(d)

d2 = [[float('inf') for i in range(n)] for j in range(n)]
for i in range(n):
  d2[i][i] = 0
  
for i in range(n):
  for j in range(n):
    if d[i][j] <= l:
      d2[i][j] = 1

d2 = warshal_floyd(d2)

q = int(input())
for i in range(q):
  s, t = map(int, input().split())
  s, t = s-1, t-1
  if d2[s][t] == float('inf'):
    print(-1)
  else:
    print(d2[s][t]-1)
  

Fixed submission:
import sys
input = sys.stdin.readline

def warshal_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j] = min(d[i][j], d[i][k]+d[k][j])
        
  return d

n, m, l = map(int, input().split())
d = [[float('inf') for i in range(n)] for j in range(n)]
for i in range(n):
  d[i][i] = 0

for i in range(m):
  a, b, c = map(int, input().split())
  a, b = a-1, b-1
  d[a][b] = c
  d[b][a] = c
  
d = warshal_floyd(d)

d2 = [[float('inf') for i in range(n)] for j in range(n)]
for i in range(n):
  d2[i][i] = 0
  
for i in range(n):
  for j in range(n):
    if d[i][j] <= l:
      d2[i][j] = 1

d2 = warshal_floyd(d2)

q = int(input())
for i in range(q):
  s, t = map(int, input().split())
  s, t = s-1, t-1
  if d2[s][t] == float('inf'):
    print(-1)
  else:
    print(d2[s][t]-1)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())

A = [0]*m
C = [0]*m
for i in range(m):
    a, b = map(int, input().split())
    A[i] = a
    cs = list(map(int, input().split()))
    c = 0
    for c_ in cs:
        c += 1 << (c_-1)
    C[i] = c

dp = [float('inf')]*(1 << n)
dp[0] = 0
for i in range(1 << n):
    for j in range(m):
        c = C[j]
        dp[i|c] = min(dp[i|c], dp[i]+A[j])

if dp[-1] != float('inf'):
    print(dp[-1])
else:
    print(-1)

Fixed submission:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())

dp = [float('inf')]*(1<<n)
dp[0] = 0

for i in range(m):
  a, b = map(int, input().split())
  c = 0
  for j in list(map(int, input().split())):
    c += 1<<(j-1)
  
  for k in range(1<<n):
    dp[k|c] = min(dp[k|c], dp[k]+a)
    
if dp[-1] == float('inf'):
  print(-1)
else:
  print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
n, m = map(int, input().split())

dp = [float('inf')]*(1<<n)
dp[0] = 0

for i in range(m):
  a, b = map(int, input().split())
  c = 0
  for j in list(map(int, input().split())):
    c += 1<<(j-1)
  
  for k in range(1<<n):
    dp[k|c] = min(dp[k|c], dp[k]+a)
    
if dp[-1] == float('inf'):
  print(-1)
else:
  print(dp[-1])

Fixed submission:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())

dp = [float('inf')]*(1<<n)
dp[0] = 0

for i in range(m):
  a, b = map(int, input().split())
  c = 0
  for j in list(map(int, input().split())):
    c += 1<<(j-1)
  
  for k in range(1<<n):
    dp[k|c] = min(dp[k|c], dp[k]+a)
    
if dp[-1] == float('inf'):
  print(-1)
else:
  print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = str(input())

def z_algorithm(s):
    n = len(s)
    Z = [0]*n
    Z[0] = n
    i = 1
    j = 0
    while i < n:
        while i+j < n and s[j] == s[i+j]:
            j += 1
        Z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < n and k+Z[k] < j:
            Z[i+k] = Z[k]
            k += 1
        i += k
        j -= k
    return Z

ans = 0
for i in range(n):
    t = s[i:]
    z = z_algorithm(t)
    for j in range(len(z)):
        if z[j] <= j:
            ans = max(ans, z[j])
print(ans)


Fixed submission:
n = int(input())
s = str(input())

dp = [[0]*(n+1) for i in range(n+1)]
#dp[n-1][n-1] = 1

for i in reversed(range(n)):
  for j in reversed(range(n)):
    if s[i] == s[j]:
      dp[i][j] = dp[i+1][j+1]+1

#print(dp)

ans = 0
for i in range(n-1):
  for j in range(i, n):
    ans = max(ans, min(dp[i][j], j-i))
    
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = str(input())

dp = [[0]*(n+1) for i in range(n+1)]
#dp[n-1][n-1] = 1

for i in reversed(range(n)):
  for j in reversed(range(n)):
    if s[i] == s[j]:
      dp[i][j] = dp[i+1][j+1]+1

#print(dp)

ans = 0
for i in range(n-1):
  for j in range(i, n):
    ans = max(ans, min(dp[i][j], j-i))
    
print(ans)


Fixed submission:
n = int(input())
s = str(input())

dp = [[0]*(n+1) for i in range(n+1)]
#dp[n-1][n-1] = 1

for i in reversed(range(n)):
  for j in reversed(range(n)):
    if s[i] == s[j]:
      dp[i][j] = dp[i+1][j+1]+1

#print(dp)

ans = 0
for i in range(n-1):
  for j in range(i, n):
    ans = max(ans, min(dp[i][j], j-i))
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = list(str(input()))
t = list(str(input()))

t.reverse()

S = set(list(s))
for c in t:
    if c not in S:
        print(-1)
        exit()

cnt = 0
#print(s)
#print(t)
while True:
    for i in range(len(s)):
        if t:
            if s[i] == t[-1]:
                t.pop()
        else:
            break
    else:
        cnt += 1
        continue
    break
print(cnt*len(s)+i)


Fixed submission:
S = list(str(input()))
T = list(str(input()))

S_ = set(list(S))
T_ = set(list(T))
for c in T:
    if c not in S_:
        print(-1)
        exit()

d = [[] for _ in range(26)]
for i, s in enumerate(S):
    d[ord(s)-ord('a')].append(i)
#print(d)

q = 0
pre = -1
import bisect
for t in T:
    j = ord(t)-ord('a')
    idx = bisect.bisect_right(d[j], pre)
    if idx == len(d[j]):
        q += 1
        pre = d[j][0]
    else:
        pre = d[j][idx]
print(q*len(S)+pre+1)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = [str(input()) for _ in range(n)]
# l = set(l)

m = [-1]*n
ans = 0

for i in range(n-1):
  if m[i] >= 0:
    continue
  else:
    si = l[i]
    m[i] = i
    temp  = 0
    for j in range(i+1, n):
      if m[j] >= 0:
        continue
      else:
        sj = l[j]
        if sorted(si) == sorted(sj): 
          temp += 1
          m[j] = i
          #print(i, temp)
  ans += (temp+1)*temp/2

print(int(ans))




Fixed submission:
n = int(input())
l = [str(sorted(str(input()))) for _ in range(n)]

d = {}

for i in range(n):
  s = l[i]
  # print(s)
  if s in d:
    d[s] += 1
  else:
    d[s] = 1

ans = 0
for x in d.values():
  ans += x*(x-1)/2
print(int(ans))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = [str(input()) for _ in range(n)]
# l = set(l)

m = [-1]*n
ans = 0

for i in range(n-1):
  if m[i] >= 0:
    continue
  else:
    si = l[i]
    m[i] = i
    temp  = 0
    for j in range(i+1, n):
      if m[j] >= 0:
        continue
      else:
        sj = l[j]
        for k in range(10):
          sj = sj.replace(si[k], '', 1)
        if sj == '':
          temp += 1
          m[j] = i
          #print(i, temp)
  ans += (temp+1)*temp/2

print(int(ans))




Fixed submission:
n = int(input())
l = [str(sorted(str(input()))) for _ in range(n)]

d = {}

for i in range(n):
  s = l[i]
  # print(s)
  if s in d:
    d[s] += 1
  else:
    d[s] = 1

ans = 0
for x in d.values():
  ans += x*(x-1)/2
print(int(ans))

Buggy python submission (verdict: Time Limit Exceeded):
import itertools

n = int(input())
l = [str(input()) for _ in range(n)]
l = set(l)

ans = 0

for si, sj in itertools.combinations(l, 2):
  for k in range(10):
    sj = sj.replace(si[k], '', 1)
  if sj == '':
    ans += 1

print(ans)

Fixed submission:
n = int(input())
l = [str(sorted(str(input()))) for _ in range(n)]

d = {}

for i in range(n):
  s = l[i]
  # print(s)
  if s in d:
    d[s] += 1
  else:
    d[s] = 1

ans = 0
for x in d.values():
  ans += x*(x-1)/2
print(int(ans))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = [str(input()) for _ in range(n)]

ans = 0

for i in range(n-1):
  si = l[i]
  for j in range(i+1, n):
    sj = l[j]
    for k in range(10):
      sj = sj.replace(si[k], '', 1)
    if sj == '':
      ans += 1

print(ans)

Fixed submission:
n = int(input())
l = [str(sorted(str(input()))) for _ in range(n)]

d = {}

for i in range(n):
  s = l[i]
  # print(s)
  if s in d:
    d[s] += 1
  else:
    d[s] = 1

ans = 0
for x in d.values():
  ans += x*(x-1)/2
print(int(ans))