Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
H, W = map(int, input().split())
N = int(input())
a = list(map(int, input().split()))

result = [[None] * W for _ in range(H)]
d = 1
x, y = 0, 0
for i in range(N):
    t = a[i]
    while t > 0:
        result[y][x] = i + 1
        if x == 0 or x == W - 1:
            d = -d
            y += 1
        else:
            x += d
        t -= 1

for i in range(H):
    print(*result[i])


Fixed submission:
H, W = map(int, input().split())
N = int(input())
a = list(map(int, input().split()))

result = [[None] * W for _ in range(H)]
d = 1
x, y = 0, 0
for i in range(N):
    t = a[i]
    while t > 0:
        result[y][x] = i + 1
        x += d
        if x == -1 or x == W:
            x -= d
            d = -d
            y += 1
        t -= 1

for i in range(H):
    print(*result[i])
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
l = list(map(int, input().split()))

l.sort()
print(sum(l[-K:])


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

l.sort(reverse=True)
print(sum(l[:K]))
Buggy python submission (verdict: Runtime Error):
H, W = map(int, input())

print('#' * (W + 2))
for i in range(H):
    print('#%s#' % (input()))
print('#' * (W + 2))

Fixed submission:
H, W = map(int, input().split())

print('#' * (W + 2))
for i in range(H):
    print('#%s#' % (input()))
print('#' * (W + 2))
Buggy python submission (verdict: Runtime Error):
from sys import stdin
from itertools import accumulate
readline = stdin.readline

N, W = map(int, input().split())
vs = [[] for _ in range(4)]
w, v = map(int, input().split())
w1 = w
vs[0].append(v)
for _ in range(N - 1):
    w, v = map(int, input().split())
    vs[w - w1].append(v)

for i in range(4):
    vs[i].sort(reverse=True)
    vs[i] = [0] + list(accumulate(vs[i]))

result = 0
for i in range(len(vs[0]) + 1):
    a = W - w1 * i
    if a < 0:
        break
    for j in range(len(vs[1]) + 1):
        b = a - (w1 + 1) * j
        if b < 0:
            break
        for k in range(len(vs[2]) + 1):
            c = b - (w1 + 2) * k
            if c < 0:
                break
            t = vs[0][i] + vs[1][j] + vs[2][k]
            for l in range(len(vs[3]) + 1):
                d = c - (w1 + 3) * l
                if d < 0:
                    break
                result = max(result, t + vs[3][l])
print(result)


Fixed submission:
from sys import stdin
from itertools import accumulate
readline = stdin.readline

N, W = map(int, input().split())
vs = [[] for _ in range(4)]
w, v = map(int, input().split())
w1 = w
vs[0].append(v)
for _ in range(N - 1):
    w, v = map(int, input().split())
    vs[w - w1].append(v)

for i in range(4):
    vs[i].sort(reverse=True)
    vs[i] = list(accumulate(vs[i]))

result = 0
for i in range(len(vs[0]) + 1):
    a = W - w1 * i
    if a < 0:
        break
    for j in range(len(vs[1]) + 1):
        b = a - (w1 + 1) * j
        if b < 0:
            break
        for k in range(len(vs[2]) + 1):
            c = b - (w1 + 2) * k
            if c < 0:
                break
            t = 0
            if i != 0:
              t += vs[0][i - 1]
            if j != 0:
              t += vs[1][j - 1]
            if k != 0:
              t += vs[2][k - 1]
            for l in range(len(vs[3]) + 1):
                d = c - (w1 + 3) * l
                if d < 0:
                    break
                if l == 0:
                    result = max(result, t)
                else:
                    result = max(result, t + vs[3][l -1])
print(result)
Buggy python submission (verdict: Runtime Error):
package main

import (
	"fmt"
	"strings"
)

func main() {
	var s string
	fmt.Scanln(&s)
	r := []rune(s)
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		r[i], r[j] = r[j], r[i]
	}
	words := [][]rune{[]rune("maerd"), []rune("remaerd"), []rune("esare"), []rune("resare")}
	for {
		if len(r) == 0 {
			fmt.Println("YES")
			return
		}
		fail := 0
		for _, w := range words {
			if strings.HasPrefix(r, w) {
				r = r[len(w):]
				break
			} else {
				fail++
			}
		}
		if fail == len(words) {
			fmt.Println("NO")
			return
		}
	}
}


Fixed submission:
import sys
s = raw_input()
ts = ['']
while True:
  nts= []
  for t in ts:
    for w in ['dreamer', 'eraser', 'dream', 'erase']:
      if s == t + w:
        print 'YES'
        sys.exit()
      if s.startswith(t + w):
        nts.append(t + w)
  if len(nts) == 0:
    print 'NO'
    sys.exit()
  ts = nts
Buggy python submission (verdict: Runtime Error):
S = {}
S['A'] = input()
S['B'] = input()
S['C'] = input()

turn = 'A'
while True:
    if S[turn] == '':
        print(turn)
        break
    turn = S[turn].pop(0).upper()


Fixed submission:
S = {}
S['A'] = input()
S['B'] = input()
S['C'] = input()

turn = 'A'
while True:
    if S[turn] == '':
        print(turn)
        break
    t = S[turn][0].upper()
    S[turn] = S[turn][1:]
    turn = t
Buggy python submission (verdict: Runtime Error):
a,b = (int(x) for x in input().split())
if b % a == 0:
  print(a+b)
 else:
  print(a-b)

Fixed submission:
a,b = (int(x) for x in input().split())
if b % a == 0:
  print(a+b)
else:
  print(b-a)
Buggy python submission (verdict: Time Limit Exceeded):
class SegTree:
    def __init__(self,arr,func,unit):
        self.func = func
        self.unit = unit
        n = 1
        while n < len(arr):
            n *= 2
        self.n = n
        nodes = [unit]*(2*n-1)
        nodes[n-1:n-1+len(arr)] = arr
        for i in range(n-2,-1,-1):
            nodes[i] = func(nodes[2*i+1],nodes[2*i+2])
        self.nodes = nodes

    def update(self,i,val):
        i += self.n-1
        self.nodes[i] = val
        while i >= 0:
            i = (i - 1) // 2
            self.nodes[i] = self.func(self.nodes[2*i+1], self.nodes[2*i+2])

    def query(self,l,r):
        l += self.n
        r += self.n
        s = self.unit
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(self.nodes[r-1], s)
            if l & 1:
                s = self.func(s, self.nodes[l-1])
                l += 1
            l >>= 1
            r >>= 1
        return s

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

MAX = 300001

segt = SegTree([0] * MAX, lambda x, y: max(x, y), 0)
for a in A:
    l = max(0, a - k)
    r = min(MAX, a + k + 1)
    m = segt.query(l, r)
    segt.update(a, m + 1)

print(segt.query(0, MAX))


Fixed submission:
class SegTree:
    def __init__(self,arr,func,unit):
        self.func = func
        self.unit = unit
        n = 1
        while n < len(arr):
            n *= 2
        self.n = n
        nodes = [unit]*(2*n-1)
        nodes[n-1:n-1+len(arr)] = arr
        for i in range(n-2,-1,-1):
            nodes[i] = func(nodes[2*i+1],nodes[2*i+2])
        self.nodes = nodes

    def update(self,i,val):
        i += self.n-1
        self.nodes[i] = val
        while i >= 0:
            i = (i - 1) // 2
            self.nodes[i] = self.func(self.nodes[2*i+1], self.nodes[2*i+2])

    def query(self,l,r):
        l += self.n
        r += self.n
        s = self.unit
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(self.nodes[r-1], s)
            if l & 1:
                s = self.func(s, self.nodes[l-1])
                l += 1
            l >>= 1
            r >>= 1
        return s

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

MAX = 300001

segt = SegTree([0] * MAX, lambda x, y: max(x, y), 0)
for a in A:
    l = max(0, a - k)
    r = min(MAX, a + k + 1)
    m = segt.query(l, r)
    segt.update(a, m + 1)

print(segt.query(0, MAX))
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(k)]

MOD = 998244353

dp = [0] * n
dp[0] = 1

for i in range(n):
  for l, r in LR:
    for j in range(l, r + 1):
      if i - j >= 0:
        dp[i] += dp[i - j]
        dp[i] %= MOD

print(dp[-1])

Fixed submission:
n, k = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(k)]

MOD = 998244353

dp = [0] * n
dp[0] = 1

ruidp = [0] * (n + 1)
ruidp[1] = 1


for i in range(n):
  for l, r in LR:
    dp[i] += (ruidp[max(i - l + 1, 0)] - ruidp[max(i - r, 0)])
    dp[i] %= MOD
  ruidp[i + 1] = ruidp[i] + dp[i] 
  ruidp[i + 1] %= MOD

print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(k)]

MOD = 998244353

dp = [0] * n
dp[0] = 1

for i in range(n):
  for l, r in LR:
    for j in range(l, r + 1):
      if i - j >= 0:
        dp[i] += dp[i - j]
        dp[i] %= MOD

print(dp[-1])

Fixed submission:
n, k = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(k)]

MOD = 998244353

dp = [0] * n
dp[0] = 1

ruidp = [0] * (n + 1)
ruidp[1] = 1


for i in range(n):
  for l, r in LR:
    dp[i] += (ruidp[max(i - l + 1, 0)] - ruidp[max(i - r, 0)])
    dp[i] %= MOD
  ruidp[i + 1] = ruidp[i] + dp[i] 
  ruidp[i + 1] %= MOD

print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

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

P = [p - 1 for p in P]
SB = defaultdict(int)

sumC = sum(C) 

# if sumC > 0:
#   d, k = divmod(k, n)
#   if d > 0:
#     pscore = (d - 1) * sumC
#     k += n 
#   else:
#     pscore = 0
# else:
#   k = min(k, n * 2)
pscore = 0

for p in P: 
  cnt = 0
  score = 0
  mv = - 10 ** 19
  s = p
  while cnt < k:
    score += C[s]
    s = P[s]
    cnt += 1
    mv = max(mv, score)
  
  SB[p] = mv

ans = max(SB.values()) + pscore
print(ans)

Fixed submission:
from collections import defaultdict

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

P = [p - 1 for p in P]

# Pの要素の中で循環するモノ同士をまとめる
sep = []
visited = [0] * n
for i in range(n):
  s = i
  box = []
  while visited[s] == 0:
    box.append(s)
    visited[s] = 1
    s = P[s]
  if box != []:
    sep.append(box)

ans = - 10 ** 19
for sp in sep:
  SB = defaultdict(int)
  sumC = sum([C[i] for i in sp]) 
  sn = len(sp)

  if sumC > 0:
    d, mk = divmod(k, sn)
    if d > 0:
      pscore = (d - 1) * sumC
      mk += sn 
    else:
      pscore = 0
  else:
    mk = min(k, sn * 2)
    pscore = 0

  for p in sp: 
    cnt = 0
    score = 0
    mv = - 10 ** 19
    s = p
    while cnt < mk:
      score += C[s]
      s = P[s]
      cnt += 1
      mv = max(mv, score)
    
    SB[p] = mv

  ans = max(ans, max(SB.values()) + pscore)
  
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict

k = int(input())

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

def f(k):
  if k % 2 == 0 or k % 5 == 0:
    return -1    

  val = 7
  cnt = 1
  while True:
    if val % k == 0:
      break
    cnt += 1
    val = val * 10 + 7
  return cnt
    
li = prime_factorize(k)

ans = 1
for k, v in li.items():
  if k <= 10000:
    ans *= f(k) ** v
  else:
    ans *= (l - 1) ** v
    
if ans < 0:
  print(-1)
else:
  print(ans)

Fixed submission:
k = int(input())

def f(k):
  if k % 2 == 0 or k % 5 == 0:
    return -1    

  val = 7
  cnt = 1
  while cnt < 10 ** 6:
    val %= k
    if val % k == 0:
      break
    cnt += 1
    val = val * 10 + 7
  else:
    return -1
  return cnt
    
print(f(k))
Buggy python submission (verdict: Runtime Error):
x, n = map(int, input().split())
P = list(map(int, input().split()))

koho = [i for i in range(1, 101) if i not in P]

koho.sort(key=lambda a: (abs(a - x), a))

print(koho[0])

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

koho = [i for i in range(-100, 200) if i not in P]

koho.sort(key=lambda a: (abs(a - x), a))

print(koho[0])
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
A = list(map(int, input().split()))

for i in range(1, 100):
  imos = [0] * (n + 1)
  for j in range(n):
    imos[max(0, j - A[j])] += 1
    imos[min(n, j + A[j] + 1)] -= 1
  
  nA = [0] * n
  nA[0] = imos[0]
  for j in range(1, n):
    nA[j] = nA[j - 1] + imos[j]

  A = nA[:]
  if i >= k:
    break

print(*A)

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

for i in range(1, 100):
  imos = [0] * (n + 1)
  for j in range(n):
    imos[max(0, j - A[j])] += 1
    imos[min(n, j + A[j] + 1)] -= 1
  
  nA = [0] * n
  nA[0] = imos[0]
  for j in range(1, n):
    nA[j] = nA[j - 1] + imos[j]

  A = nA[:]
  if i >= k:
    break

print(*A)
Buggy python submission (verdict: Time Limit Exceeded):
n, s = map(int, input().split())
A = list(map(int, input().split()))

MOD = 998244353
 
# dp[i][j] = i 番目までの選択をして、1 つめの選択肢を選んだ k に対する ak の和が j であるような場合の数
dp = [[0] * (s + 1) for _ in range(n + 1)]
dp[0][0] = 1

for i in range(n):
  for j in range(s + 1):
    dp[i + 1][j] += dp[i][j] * 2
    dp[i + 1][j] %= MOD
    if j + A[i] <= s:
      dp[i + 1][j + A[i]] += dp[i][j]
      dp[i + 1][j + A[i]] %= MOD

print(dp[-1][-1])

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

MOD = 998244353
 
# dp[i][j] = i 番目までの選択をして、1 つめの選択肢を選んだ k に対する ak の和が j であるような場合の数
dp = [[0] * (s + 1) for _ in range(n + 1)]
dp[0][0] = 1

for i in range(n):
  for j in range(s + 1):
    dp[i + 1][j] += dp[i][j] * 2
    dp[i + 1][j] %= MOD
    if j + A[i] <= s:
      dp[i + 1][j + A[i]] += dp[i][j]
      dp[i + 1][j + A[i]] %= MOD

print(dp[-1][-1])
Buggy python submission (verdict: Runtime Error):
n = int(input())
A = list(map(int, input().split()))

# A[0]との和 - idxの差の数
box = [0] * (n - 1)

for i in range(n - 1):
  box[A[0] + A[i + 1] - i - 1] += 1 

ans = 0
for a in A:
  ans += sum(i if itr == (A[0] - a) else 0 for itr, i in enumerate(box))

print(ans)

Fixed submission:
from collections import Counter

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

L = [i + a for i, a in enumerate(A)]
R = [i - a for i, a in enumerate(A)]

cL = Counter(L)
cR = Counter(R)

ans = 0
for i in cL.keys():
  ans += cL[i] * cR[i]

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = list(map(int, input().split()))

ans = 0
for i in range(n):
  for j in range(A[i] + 1, n - i):
    if A[i] + A[i + j] == j:
      ans += 1

print(ans)

Fixed submission:
from collections import Counter

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

L = [i + a for i, a in enumerate(A)]
R = [i - a for i, a in enumerate(A)]

cL = Counter(L)
cR = Counter(R)

ans = 0
for i in cL.keys():
  ans += cL[i] * cR[i]

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = list(map(int, input().split()))

ans = 0

for i in range(n):
  ans += sum([A[i] + A[i + j] == j for j in range(1, n - i)])
  
print(ans)

Fixed submission:
from collections import Counter

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

L = [i + a for i, a in enumerate(A)]
R = [i - a for i, a in enumerate(A)]

cL = Counter(L)
cR = Counter(R)

ans = 0
for i in cL.keys():
  ans += cL[i] * cR[i]

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = list(map(int, input().split()))

ans = 0
for i in range(n):
  for j in range(1, n - i):
    if A[i] + A[i + j] == j:
      ans += 1

print(ans)

Fixed submission:
from collections import Counter

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

L = [i + a for i, a in enumerate(A)]
R = [i - a for i, a in enumerate(A)]

cL = Counter(L)
cR = Counter(R)

ans = 0
for i in cL.keys():
  ans += cL[i] * cR[i]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
S = list(map(int, list(input())))

mods = [0 for _ in range(2019)]
mods[0] = 1

num = 0
for itr, s in enumerate(S[::-1]):
  num = s * 10 ** itr + num
  num %= 2019
  mods[num] += 1
  
ans = 0
for m in mods:
  ans += m * (m - 1) // 2

print(ans)


Fixed submission:
S = list(map(int, list(input())))

MOD = 2019

mods = [0 for _ in range(2019)]
mods[0] = 1

num = 0
digit = 1
for s in S[::-1]:
  num = s * digit + num
  num %= MOD
  mods[num] += 1
  digit = (digit * 10) % MOD
  
ans = 0
for m in mods:
  ans += m * (m - 1) // 2

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S = list(map(int, list(input())))

mods = [0 for _ in range(2019)]
mods[0] = 1

num = 0
for itr, s in enumerate(S[::-1]):
  num = s * 10 ** itr + num
  num %= 2019
  mods[num] += 1
  
ans = 0
for m in mods:
  ans += m * (m - 1) // 2

print(ans)


Fixed submission:
S = list(map(int, list(input())))

MOD = 2019

mods = [0 for _ in range(2019)]
mods[0] = 1

num = 0
digit = 1
for s in S[::-1]:
  num = s * digit + num
  num %= MOD
  mods[num] += 1
  digit = (digit * 10) % MOD
  
ans = 0
for m in mods:
  ans += m * (m - 1) // 2

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S = list(map(int, list(input())))

mods = [0 for _ in range(2019)]
mods[0] = 1

num = 0
for itr, s in enumerate(S[::-1]):
  num = s * 10 ** itr + num
  mo = num % 2019
  mods[mo] += 1

#  print(itr, s, num, mo)
  
ans = 0
for m in mods:
  ans += m * (m - 1) // 2

print(ans)


Fixed submission:
S = list(map(int, list(input())))

MOD = 2019

mods = [0 for _ in range(2019)]
mods[0] = 1

num = 0
digit = 1
for s in S[::-1]:
  num = s * digit + num
  num %= MOD
  mods[num] += 1
  digit = (digit * 10) % MOD
  
ans = 0
for m in mods:
  ans += m * (m - 1) // 2

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = list(map(int, input().split()))

p = []
for i, v in enumerate(A):
  p.append((v, i))
  
p.sort(reverse=True)

dp = [[0] * (n + 1) for _ in range(n + 1)]

for i in range(n):
  k = p[i][0]
  r = p[i][1]
  for x in range(i + 1):
    y = i - x
    dp[x + 1][y] = max(dp[x + 1][y], dp[x][y] + abs(r - x) * k)
    dp[x][y + 1] = max(dp[x][y + 1], dp[x][y] + abs(r - (n - 1 - y)) * k)

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

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

p = []
for i, v in enumerate(A):
  p.append((v, i))
  
p.sort(reverse=True)

dp = [[0] * (n + 1) for _ in range(n + 1)]

for i in range(n):
  k = p[i][0]
  r = p[i][1]
  for x in range(i + 1):
    y = i - x
    dp[x + 1][y] = max(dp[x + 1][y], dp[x][y] + abs(r - x) * k)
    dp[x][y + 1] = max(dp[x][y + 1], dp[x][y] + abs(r - (n - 1 - y)) * k)

ans = 0
for i in range(n):
  ans = max(ans, dp[i][n-i])
  
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
S = input()

def c(s1, s2, s3, i, s):
  cnt = 0
  L = S[:i]
  R = S[i+1:]
  # print(s1, s2, s3, L, R)
  if s == s1:
    lc = 0
    for l in L:
      if l == s2:
        lc += 1
    rc = 0
    for r in R:
      if r == s3:
        rc += 1
    cnt += lc * rc 
  for i, j in zip(R, L[::-1]):
    if s1 == s and i == s3 and j == s2:
      cnt -= 1
  # print(cnt)
  return cnt

ans = 0
for i, s in enumerate(S):
  ans += c("R", "B", "G", i, s) 
  ans += c("R", "G", "B", i, s) 
  ans += c("B", "R", "G", i, s) 
  ans += c("B", "G", "R", i, s) 
  ans += c("G", "R", "B", i, s) 
  ans += c("G", "B", "R", i, s) 

print(ans)

Fixed submission:
n = int(input())
S = input()

def c(s1, s2, s3, i, s):
  cnt = 0
  L = S[:i]
  R = S[i+1:]
  # print(s1, s2, s3, L, R)
  if s == s1:
    lc = 0
    for l in L:
      if l == s2:
        lc += 1
    rc = 0
    for r in R:
      if r == s3:
        rc += 1
    cnt += lc * rc 
  for i, j in zip(R, L[::-1]):
    if s1 == s and i == s3 and j == s2:
      cnt -= 1
  # print(cnt)
  return cnt

ans = 0
for i, s in enumerate(S):
  ans += c("R", "B", "G", i, s) 
  ans += c("R", "G", "B", i, s) 
  ans += c("B", "R", "G", i, s) 
  ans += c("B", "G", "R", i, s) 
  ans += c("G", "R", "B", i, s) 
  ans += c("G", "B", "R", i, s) 

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# E - Sum of gcd of Tuples (Hard)
# https://atcoder.jp/contests/abc162/tasks/abc162_e

MOD = 10 ** 9 + 7

n, k = map(int, input().split())
dic = {}

ans = 0
for i in range(k, 0, -1):
  num = pow(k // i, n, MOD)
  for key, val in dic.items():
    if key % i == 0:
      num -= val
  dic[i] = num
  ans += num * i
  ans %= MOD

print(ans)



Fixed submission:
# E - Sum of gcd of Tuples (Hard)
# https://atcoder.jp/contests/abc162/tasks/abc162_e

MOD = 10 ** 9 + 7

n, k = map(int, input().split())
dic = [0] * (k + 1)

ans = 0
for i in range(k, 0, -1):
  dic[i] = pow(k // i, n, MOD)

for i in range(k, 0, -1):
  for j in range(i * 2, k + 1, i):
    dic[i] -= dic[j]
    dic[i] %= MOD

ans = 0
for i in range(1, k + 1):
  ans += dic[i] * i
  ans %= MOD

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# E - Sum of gcd of Tuples (Hard)
# https://atcoder.jp/contests/abc162/tasks/abc162_e

MOD = 10 ** 9 + 7

n, k = map(int, input().split())
dic = {}

ans = 0
for i in range(k, 0, -1):
  num = (k // i) ** n
  for key, val in dic.items():
    if key % i == 0:
      num -= val
  dic[i] = num
  ans += num * i
  ans %= MOD

print(ans)



Fixed submission:
# E - Sum of gcd of Tuples (Hard)
# https://atcoder.jp/contests/abc162/tasks/abc162_e

MOD = 10 ** 9 + 7

n, k = map(int, input().split())
dic = [0] * (k + 1)

ans = 0
for i in range(k, 0, -1):
  dic[i] = pow(k // i, n, MOD)

for i in range(k, 0, -1):
  for j in range(i * 2, k + 1, i):
    dic[i] -= dic[j]
    dic[i] %= MOD

ans = 0
for i in range(1, k + 1):
  ans += dic[i] * i
  ans %= MOD

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

N = int(input())
md = make_divisors(N)
mdd = make_divisors(N-1)
se = set(md+mdd)
li = list(se)
ans = 0
for i in li:
  if i != 1:
    n = N
    while n >= i:
      if n % i == 0:
        n = n // i
      else:
        n = n - i
    if n == 1:
      ans += 1
print(ans)

Fixed submission:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

N = int(input())
md = make_divisors(N)
mdd = make_divisors(N-1)
se = set(md + mdd)
li = list(se)
ans = 0
for i in li:
  if i != 1:
    n = N
    while n >= i:
      if n % i == 0:
        n = n // i
      else:
        n = n % i
    if n == 1:
      ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

N = int(input())
md = make_divisors(N)
mdd = make_divisors(N-1)
se = set(md+mdd)
li = list(se)
ans = 0
for i in li:
  if i != 1:
    n = N
    while n >= i:
      if n % i == 0:
        n = n // i
      else:
        n = n - i
    if n == 1:
      ans += 1
print(ans)

Fixed submission:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

N = int(input())
md = make_divisors(N)
mdd = make_divisors(N-1)
se = set(md + mdd)
li = list(se)
ans = 0
for i in li:
  if i != 1:
    n = N
    while n >= i:
      if n % i == 0:
        n = n // i
      else:
        n = n % i
    if n == 1:
      ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
li = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
k = input()
print(li[k-1])

Fixed submission:
li = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
k = int(input())
print(li[k-1])