Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from collections import Counter
import sys
input = sys.stdin.readline

N = int(input())
AB = [[int(i) for i in input().split()] for _ in range(N)]

mod = 10 ** 9 + 7

def gcd(a, b) :
  if b > a : 
    a, b = b, a
  
  while b != 0 :
    a, b = b, a % b
  return a

p = []
for i, (a, b) in enumerate(AB) :
  g = gcd(a, b)
  a //= g
  b //= g
  if a < 0 :
    a *= -1
    b *= -1
  p.append((a, b))

ret = 1
visited = set()
cnt = Counter(p)
for k, v in cnt.items() :
  a, b = k
  c, d = b, -a
  if c < 0 :
    c *= -1
    d *= -1
  if cnt[(c, d)] == 0 :
    ret *= pow(2, v, mod)
  else :
    if not (c, d) in visited :
      u = cnt[(c, d)]
      ret *= (pow(2, u, mod) +  pow(2, v, mod) - 1)
      visited.add((a, b))
      visited.add((c, d))
  ret %= mod

print(ret - 1)

Fixed submission:
from collections import Counter
import sys
input = sys.stdin.readline

N = int(input())
AB = [[int(i) for i in input().split()] for _ in range(N)]

mod = 10 ** 9 + 7

def gcd(a, b) :
  if b > a : 
    a, b = b, a
  
  while b != 0 :
    a, b = b, a % b
  return a

p = []
both = 0
zeroa = 0
zerob = 0
for a, b in AB :
  if a == 0 and b == 0 :
    both += 1
    continue
  elif a == 0 :
    zeroa += 1
    continue
  elif b == 0 :
    zerob += 1
    continue
    
  g = gcd(abs(a), abs(b))
  a //= g
  b //= g
  if a < 0 :
    a *= -1
    b *= -1
  p.append((a, b))

ret = 1
visited = set()
cnt = Counter(p)
for k, v in cnt.items() :
  a, b = k
  c, d = b, -a
  if c < 0 :
    c *= -1
    d *= -1
  if cnt[(c, d)] == 0 :
    ret *= pow(2, v, mod)
  else :
    if not (c, d) in visited :
      u = cnt[(c, d)]
      ret *= (pow(2, u, mod) + pow(2, v, mod) - 1)
      visited.add((a, b))
      visited.add((c, d))
  ret %= mod

ret *= pow(2, zeroa, mod) + pow(2, zerob, mod) - 1
ret %= mod

print((ret - 1 + both) % mod)
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left, bisect_right
from collections import defaultdict

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

pos = defaultdict(lambda: [])
for i, s in enumerate(S) :
  pos[s].append(i)

def color(a, b) :
  for c in 'RGB' :
    if c != S[a] and c != S[b] :
      return c

ret = 0
for a in range(N) :
  for b in range(a + 2, N) :
    if S[a] == S[b] : continue
    c = color(a, b)
    ret += bisect_right(pos[c], b) - 1
    ret -= bisect_right(pos[c], a) - 1
    if (a + b) % 2 == 0 and S[(a + b) // 2] == c :
      ret -= 1
      
print(ret)

Fixed submission:
from collections import defaultdict
from itertools import permutations

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

pos = defaultdict(lambda: [])
for i, s in enumerate(S) :
  pos[s].append(i)

ret = 0
for a, b, c in (permutations('RGB')) :
  for center in pos[b] :
    cnt = [0] * (N + 1)
    left, right = 0, 0
    for l in pos[a] :
      if l >= center :
        break
      cnt[center-l] += 1
      left += 1
    for r in pos[c][::-1] :
      if r <= center :
        break
      cnt[r-center] += 1
      right += 1
    ret += left * right - cnt.count(2)
     

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

H, W, K = map(int, input().split())
S = [[int(i) for i in input()[:-1]] for _ in range(H)]

m = float('inf')
for i in range(1 << (H - 1)) :
  pos = [0] * H
  x = 0
  for j in range(H - 1) :
    if i & (1 << j) :
      x += 1
    pos[j+1] = x
      
  x = 0
  cnt = [0] * H
  ret = bin(i)[2:].count('1')
  while x < W :
    for y in range(H) :
      cnt[pos[y]] += S[y][x]
      if cnt[pos[y]] > K :
        cnt = [0] * H
        ret += 1
        break
    else :
      x += 1
      
  m = min(m, ret)
  
print(m)

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

H, W, K = map(int, input().split())
S = [[int(i) for i in input()[:-1]] for _ in range(H)]

m = float('inf')
for i in range(1 << (H - 1)) :
  pos = [0] * H
  x = 0
  for j in range(H - 1) :
    if i & (1 << j) :
      x += 1
    pos[j+1] = x
  
  ret = x
  x = 0
  cnt = [0] * H
  flag = 0
  while x < W :
    for y in range(H) :
      cnt[pos[y]] += S[y][x]
      if cnt[pos[y]] > K :
        cnt = [0] * H
        ret += 1
        flag += 1
        break
    else :
      x += 1
      flag = 0
      
    if flag == 2 :
      ret = float('inf')
      break
  
  m = min(m, ret)
  
print(m)

Buggy python submission (verdict: Time Limit Exceeded):
H, W, K = map(int, input().split())
S = [[int(i) for i in input()] for _ in range(H)]

m = float('inf')
for i in range(1 << (H - 1)) :
  pos = [0] * H
  x = 0
  for j in range(H - 1) :
    if i & (1 << j) :
      x += 1
    pos[j+1] = x
      
  x = 0
  cnt = [0] * H
  ret = bin(i)[2:].count('1')
  while x < W :
    for y in range(H) :
      cnt[pos[y]] += S[y][x]
      if cnt[pos[y]] > K :
        cnt = [0] * H
        ret += 1
        break
    else :
      x += 1
      
  m = min(m, ret)
  
print(m)

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

H, W, K = map(int, input().split())
S = [[int(i) for i in input()[:-1]] for _ in range(H)]

m = float('inf')
for i in range(1 << (H - 1)) :
  pos = [0] * H
  x = 0
  for j in range(H - 1) :
    if i & (1 << j) :
      x += 1
    pos[j+1] = x
  
  ret = x
  x = 0
  cnt = [0] * H
  flag = 0
  while x < W :
    for y in range(H) :
      cnt[pos[y]] += S[y][x]
      if cnt[pos[y]] > K :
        cnt = [0] * H
        ret += 1
        flag += 1
        break
    else :
      x += 1
      flag = 0
      
    if flag == 2 :
      ret = float('inf')
      break
  
  m = min(m, ret)
  
print(m)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
Q = int(input())

prefix = ''
suffix = ''
mode = 0
for _ in range(Q) :
  Query = list(input().split())
  if Query[0] == '1' :
    mode ^= 1
  else :
    _, F, C = Query
    F = int(F) - 1
    
    if mode != F :
      suffix += C
    else :
      prefix += C
      

if mode == 0 :
  print(prefix[::-1] + S + suffix)
else :
  print(suffix[::-1] + S[::-1] + prefix)

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

prefix = ''
suffix = ''
mode = 0
for _ in range(Q) :
  Query = list(input().split())
  if Query[0] == '1' :
    mode ^= 1
  else :
    _, F, C = Query
    F = int(F) - 1
    
    if mode != F :
      suffix += C
    else :
      prefix += C
      

if mode == 0 :
  print(prefix[::-1] + S + suffix)
else :
  print(suffix[::-1] + S[::-1] + prefix)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict

N, P = map(int, input().split())
S = input()

mem = defaultdict(int)
mem[0] += 1
T = [0]
dec = 1
x = 0
for s in S[::-1] :
  s = int(s)
  x = (dec * s + x) % P
  dec = dec * 10 % P
  T.append(x)
  mem[x] += 1

inv = pow(10, P - 2, P)
dec = 1
ret = 0
for i, t in enumerate(T) :
  if dec % P =  0 :
    ret += len(T) - i - 1
  else :
    ret += mem[t] - 1
  mem[t] -= 1
  dec = dec * inv % P
  
print(ret)


Fixed submission:
from collections import defaultdict

N, P = map(int, input().split())
S = input()

if P == 2 or P == 5 :
  ret = 0
  for i, v in enumerate(S) :
    if int(v) % P == 0 :
      ret += i + 1
  print(ret)

else :
  mem = defaultdict(int)
  mem[0] += 1

  T = [0]
  dec = 1
  x = 0
  for s in S[::-1] :
    s = int(s)
    x = (dec * s + x) % P
    dec = dec * 10 % P
    T.append(x)
    mem[x] += 1

  ret = 0
  for i, t in enumerate(T) :
    ret += mem[t] - 1
    mem[t] -= 1
    
  print(ret)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
xyc = [[int(i) for i in input().split()] for _ in range(N)]

def check(n) :
  global K
  for i in range(N) :
    xi, yi, ci = xyc[i]
    ri = n / ci
    for j in range(i + 1, N) :
      xj, yj, cj = xyc[j]
      xj -= xi
      yj -= yi
      rj = n / cj
      a = (xj ** 2 + yj ** 2 + ri ** 2 - rj ** 2) / 2
      root = (xj ** 2 + yj ** 2) * (ri ** 2) - a ** 2
      if root + eps < 0 : continue
      for sgn in [1, -1] :
        cnt = 0
        X = (a * xj + sgn * yj * (root ** 0.5)) / (xj ** 2 + yj ** 2) + xi
        Y = (a * yj - sgn * xj * (root ** 0.5)) / (xj ** 2 + yj ** 2) + yi
        for x, y, c in xyc :
          if (x - X) ** 2 + (y - Y) ** 2 <= (n / c) ** 2 + eps :
            cnt += 1
        if cnt >= K :
          return True
  
  for X, Y, _ in xyc :
    cnt = 0
    for x, y, c in xyc :
      if (x - X) ** 2 + (y - Y) ** 2 + eps <= (n / c) ** 2 :
        cnt += 1
    if cnt >= K :
      return True
      
  return False

eps = 1e-7
ng, ok = -1, 10 ** 6
while ok - ng > eps :
  n = (ng + ok) / 2
  if check(n) :
    ok = n
  else :
    ng = n
 
print(ok)

Fixed submission:
N, K = map(int, input().split())
xyc = [[int(i) for i in input().split()] for _ in range(N)]

def check(n) :
  for i in range(N) :
    xi, yi, ci = xyc[i]
    ri = n / ci
    for j in range(i + 1, N) :
      xj, yj, cj = xyc[j]
      xj -= xi
      yj -= yi
      rj = n / cj
      a = (xj ** 2 + yj ** 2 + ri ** 2 - rj ** 2) / 2
      root = max(0, (xj ** 2 + yj ** 2) * (ri ** 2) - a ** 2) ** 0.5
      for sgn in [1, -1] :
        cnt = 0
        X = (a * xj + sgn * yj * root) / (xj ** 2 + yj ** 2) + xi
        Y = (a * yj - sgn * xj * root) / (xj ** 2 + yj ** 2) + yi
        for x, y, c in xyc :
          if (x - X) ** 2 + (y - Y) ** 2 <= (n / c) ** 2 + eps :
            cnt += 1
        if cnt >= K :
          return True
  
  for X, Y, _ in xyc :
    cnt = 0
    for x, y, c in xyc :
      if (x - X) ** 2 + (y - Y) ** 2 <= (n / c) ** 2 + eps :
        cnt += 1
    if cnt >= K :
      return True
      
  return False

eps = 1e-8
ng, ok = 0, 10 ** 6
while ok - ng > eps :
  n = (ng + ok) / 2
  if check(n) :
    ok = n
  else :
    ng = n
 
print(ok)
Buggy python submission (verdict: Time Limit Exceeded):
r1, c1, r2, c2 = map(int, input().split())
mod = 10 ** 9 + 7

# 求めるものは
# sum[i,r1,r2]sum[j,c1,c2] f(i, j) ・・・ (1)
# g(x, y) = sum[i,0,x]sum[j,0,y](i+j)choose(i) とすると
# (1) = g(r2, c2) - g(r2, c1-1) - g(r1-1, c2) + g(r1-1, c1-1)
# と変形できる
# ここでsum[j,0,y](i+j)choose(i) = (i+y+1)choose(i+1)と変形できる
# これ解けた人って上記の変形を知識として知っていたんですか？その場で算出したんですか？後者ならすごすぎる・・・。
# 詳細はけんちょんさんのブログが凄くわかりやすいです
# よってg(x, y) = sum[i,0,x](i+y+1)choose(i+1)と変形できる

fac = [1]
inv = [1]
for i in range(1, r2 + c2 + 10) :
  fac.append(fac[-1] * i % mod)
  inv.append(pow(fac[-1], mod - 2, mod))

def comb(n, r) :
  return fac[n] * inv[n-r] * inv[r] % mod

def g(x, y) :
  s = 0
  for i in range(x + 1) :
    s += comb(i + y + 1, i + 1)
  return s

ret = g(r2, c2) - g(r2, c1-1) - g(r1-1, c2) + g(r1-1, c1-1)
ret %= mod

print(ret)

Fixed submission:
r1, c1, r2, c2 = map(int, input().split())
mod = 10 ** 9 + 7

fac = [1]
inv = [1]
for i in range(1, r2 + c2 + 10) :
  fac.append(fac[-1] * i % mod)
  inv.append(pow(fac[-1], mod - 2, mod))

def comb(n, r) :
  return fac[n] * inv[n-r] * inv[r] % mod

def g(x, y) :
  return comb(x + y, y)

ret = g(r2+1, c2+1) - g(r2+1, c1) - g(r1, c2+1) + g(r1, c1)
ret %= mod

print(ret)
Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left

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

A.sort()
mem = dict()

ng, ok = 0, A[-1] * 2 + 1
while ok - ng > 1 :
  m = (ok + ng) // 2
  c = 0
  for i in range(N) :
    c += N - bisect_left(A, m - A[i])
  mem[m] = c
  if c <= M :
    ok = m
  else :
    ng = m
  
S = [A[0]]
for i in range(1, N) :
  S.append(S[-1] + A[i])
S.append(0)

all = sum(A)
ret = 0
for i in range(N) :
  ret += all - S[bisect_left(A, m - A[i])-1]
  ret += A[i] * (N - bisect_left(A, m - A[i]))
ret += (M - mem[ok]) * (ok - 1)
print(ret)

Fixed submission:
from bisect import bisect_left

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

A.sort()

def calc(m) :
  c = 0
  for i in range(N) :
    c += N - bisect_left(A, m - A[i])
  return c

ng, ok = 0, A[-1] * 2 + 1
while ok - ng > 1 :
  m = (ok + ng) // 2

  if calc(m) <= M :
    ok = m
  else :
    ng = m
  
S = [A[0]]
for i in range(1, N) :
  S.append(S[-1] + A[i])
S.append(0)
S.append(0)

all = sum(A)
ret = 0
for i in range(N) :
  ret += all - S[bisect_left(A, ng - A[i])-1]
  ret += A[i] * (N - bisect_left(A, ng - A[i]))
ret -= (calc(ng) - M) * (ng)
print(ret)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

H, W = map(int, input().split())
A = [[int(i) for i in input().split()] for _ in range(H)]
B = [[int(i) for i in input().split()] for _ in range(H)]

pdp = [set() for _ in range(W)]
pdp[0] = set([0])
for y in range(H) :
    ndp = [set() for _ in range(W)]
    for x in range(W) :
        s = set([i + A[y][x] - B[y][x] for i in pdp[x]] + [i + B[y][x] - A[y][x] for i in pdp[x]])
        if y < H - 1 :
            for i in pdp[x] :
                ndp[x] |= s
        if x < W - 1 :
            for i in pdp[x] :
                pdp[x+1] |= s
    
    if y == H - 1 :
        ret = float('inf')
        for i in pdp[-1] :
            ret = min(ret, abs(i + A[H-1][W-1] - B[H-1][W-1]))
            ret = min(ret, abs(i + B[H-1][W-1] - A[H-1][W-1]))
        print(ret)
    pdp = ndp

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

H, W = map(int, input().split())
A = [[int(i) for i in input().split()] for _ in range(H)]
B = [[int(i) for i in input().split()] for _ in range(H)]
C = [[abs(A[y][x] - B[y][x]) for x in range(W)] for y in range(H)]

N = 13000
half = N // 2

dp = [[0] * W for _ in range(H)]
dp[0][0] = (1 << (half - C[0][0])) | (1 << (half + C[0][0]))

for y in range(H) :
    for x in range(W) :
        if y != 0 :
            dp[y][x] |= (dp[y-1][x] >> C[y][x]) | (dp[y-1][x] << C[y][x])
                    
        if x != 0 :
            dp[y][x] |= (dp[y][x-1] >> C[y][x]) | (dp[y][x-1] << C[y][x])

b = bin(dp[-1][-1])[2:][::-1]
ret = float('inf')
for k, v in enumerate(b) :
    if v == '1' :
        ret = min(ret, abs(k - half))
        
print(ret)
Buggy python submission (verdict: Time Limit Exceeded):
M = int(input())
dc = [[int(i) for i in input().split()] for _ in range(M)]

digit = [0] * 10
for d, c in dc :
    digit[d] += c

ret = digit[0]
digit[0] = 0
while sum(digit) != 1 :
    for a in range(1, 10) :
        for b in range(1, 10) :
            if a + b >= 10 :
                na = (a + b) // 10
                nb = (a + b) % 10
                if a == b :
                    x = digit[a] // 2
                    digit[na] += x
                    digit[nb] += x
                    digit[a] -= 2 * x
                else :
                    x = min(digit[a], digit[b])
                    digit[na] += x
                    digit[nb] += x
                    digit[a] -= x
                    digit[b] -= x
                ret += x
            else :
                if a == b :
                    x = digit[a] // 2
                    digit[a+b] += x
                    digit[a] -= 2 * x
                else :
                    x = min(digit[a], digit[b])
                    digit[a+b] += x
                    digit[a] -= x
                    digit[b] -= x

for d, c in dc :
    if d != 0 :
        ret += c
        
print(ret - 1)

Fixed submission:
M = int(input())
dc = [[int(i) for i in input().split()] for _ in range(M)]

ret = 0
s = 0
for d, c in dc :
    s += d * c
    t = s // 10
    ret += t
    s %= 10
    s += t
    
while s >= 10 :
    t = s // 10
    ret += t
    s %= 10
    s += t

for d, c in dc :
    ret += c
        
print(ret - 1)
Buggy python submission (verdict: Runtime Error):
X, Y = map(int, input().split())
mod = 10 ** 9 + 7

if (X + Y) % 3 == 0 : 
    n = (X + Y) // 3
    a = 2 * n - X
    
    if 0 <= a <= N and a * 2 + (n - a) == Y :
        fac = [1]
        inv = [1]
        for i in range(1, n + 1) :
            fac.append(fac[-1] * i % mod)
            inv.append(pow(fac[-1], mod - 2, mod))
        print(fac[n] * inv[n-a] * inv[a] % mod)
    
    else :
        print(0)
        
else :
    print(0)

Fixed submission:
X, Y = map(int, input().split())
mod = 10 ** 9 + 7

if (X + Y) % 3 == 0 : 
    n = (X + Y) // 3
    a = 2 * n - X
    
    if 0 <= a <= n and a * 2 + (n - a) == Y :
        fac = [1]
        inv = [1]
        for i in range(1, n + 1) :
            fac.append(fac[-1] * i % mod)
            inv.append(pow(fac[-1], mod - 2, mod))
        print(fac[n] * inv[n-a] * inv[a] % mod)
    
    else :
        print(0)
        
else :
    print(0)

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

if (X + Y) % 3 == 0 : 
    n = (X + Y) // 3
    a = 2 * n - X
    
    if a * 2 + (n - a) == Y :
        fac = [1]
        inv = [1]
        for i in range(1, n + 1) :
            fac.append(fac[-1] * i % mod)
            inv.append(pow(fac[-1], mod - 2, mod))
        print(fac[n] * inv[n-a] * inv[a] % mod)
    
    else :
        print(0)
        
else :
    print(0)

Fixed submission:
X, Y = map(int, input().split())
mod = 10 ** 9 + 7

if (X + Y) % 3 == 0 : 
    n = (X + Y) // 3
    a = 2 * n - X
    
    if 0 <= a <= n and a * 2 + (n - a) == Y :
        fac = [1]
        inv = [1]
        for i in range(1, n + 1) :
            fac.append(fac[-1] * i % mod)
            inv.append(pow(fac[-1], mod - 2, mod))
        print(fac[n] * inv[n-a] * inv[a] % mod)
    
    else :
        print(0)
        
else :
    print(0)
Buggy python submission (verdict: Time Limit Exceeded):
A, B = map(int, input().split())

def gcd(m, n) :
    while n :
        m, n = n, m % n
    return m

ret = 0
x = gcd(A, B)
if x % 2 == 0 :
    ret += 1
    while x % 2 == 0 :
        x //= 2
        
i = 3
while x != 1 :
    if x % i == 0 :
        ret += 1
        x //= i
        
    while x % i == 0 :
        x //= i
        
    i += 2
        
print(ret + 1)


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

def gcd(m, n) :
    while n :
        m, n = n, m % n
    return m

ret = 0
x = gcd(A, B)
if x % 2 == 0 :
    ret += 1
    while x % 2 == 0 :
        x //= 2
        
i = 3
while i * i <= x :
    if x % i == 0 :
        ret += 1
        x //= i
        
    while x % i == 0 :
        x //= i
        
    i += 2

if x != 1 :
    ret += 1
print(ret + 1)

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

def gcd(m, n) :
    while n :
        m, n = n, m % n
    return m

ret = 0
x = gcd(A, B)
if x % 2 == 0 :
    ret += 1
    while x % 2 == 0 :
        x //= 2
        
i = 3
while x != 1 :
    flg = False
    while x % i == 0 :
        x //= i
        flg = True
        
    if flg :
        ret += 1
    i += 2
        
print(ret + 1)


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

def gcd(m, n) :
    while n :
        m, n = n, m % n
    return m

ret = 0
x = gcd(A, B)
if x % 2 == 0 :
    ret += 1
    while x % 2 == 0 :
        x //= 2
        
i = 3
while i * i <= x :
    if x % i == 0 :
        ret += 1
        x //= i
        
    while x % i == 0 :
        x //= i
        
    i += 2

if x != 1 :
    ret += 1
print(ret + 1)

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

def gcd(m, n) :
    while n :
        m, n = n, m % n
    return m

ret = 0
i = 2
x = gcd(A, B)
while x != 1 :
    flg = False
    while x % i == 0 :
        x //= i
        flg = True
        
    if flg :
        ret += 1
    i += 1
        
print(ret + 1)

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

def gcd(m, n) :
    while n :
        m, n = n, m % n
    return m

ret = 0
x = gcd(A, B)
if x % 2 == 0 :
    ret += 1
    while x % 2 == 0 :
        x //= 2
        
i = 3
while i * i <= x :
    if x % i == 0 :
        ret += 1
        x //= i
        
    while x % i == 0 :
        x //= i
        
    i += 2

if x != 1 :
    ret += 1
print(ret + 1)

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

ret = 0
i = 2
while A >= i and B >= i :
    flg = False
    while A % i == 0 and B % i == 0 :
        A //= i
        B //= i
        flg = True
        
    if flg :
        ret += 1
    i += 1
        
print(ret + 1)

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

def gcd(m, n) :
    while n :
        m, n = n, m % n
    return m

ret = 0
x = gcd(A, B)
if x % 2 == 0 :
    ret += 1
    while x % 2 == 0 :
        x //= 2
        
i = 3
while i * i <= x :
    if x % i == 0 :
        ret += 1
        x //= i
        
    while x % i == 0 :
        x //= i
        
    i += 2

if x != 1 :
    ret += 1
print(ret + 1)
Buggy python submission (verdict: Time Limit Exceeded):
# ローリングハッシュ
class RollingHash() :
    def __init__(self, S, base=26, mod=2**61-1) :
        hash = [0]
        pow = [1]
        for s in S :
            hash.append((hash[-1] * base + ord(s)) % mod)
            pow.append(pow[-1] * base % mod)

        self.hash = hash
        self.pow = pow
        self.mod = mod
        
    def get(self, l, r) :
        return (self.hash[r+1] - self.hash[l] * self.pow[r+1-l]) % self.mod
        
N = int(input())
S = input()

RH = RollingHash(S)

def solve() :
    for k in range(N // 2, 0, -1) :
        for i in range(N - 2 * k + 1) :
            for j in range(i + k, N - k + 1) :
                if RH.get(i, i+k-1) == RH.get(j, j+k-1) :
                    return k
    return 0
print(solve())

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

mod = 10 ** 9 + 7
hash = [0]
pow = [1]
for s in S :
    hash.append((hash[-1] * 26 + ord(s) - 97) % mod)
    pow.append(pow[-1] * 26 % mod)

M = 0
for i in range(N + 1) :
    for j in range(i + 1, N + 1) :
        for k in range(M + 1, N - j + 1) :
            if i + k > j :
                break
            if (hash[j+k] - hash[j] * (pow[k])) % mod == (hash[i+k] - hash[i] *  pow[k]) % mod :
                M += 1
            else :
                break
                
print(M)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

mod = 10 ** 9 + 7
hash = [ord(S[0])-97]
for s in S[1:] :
    hash.append((hash[-1] * 26 + ord(s) - 97) % mod)
hash = [0] + hash

M = 0
for i in range(N + 1) :
    for j in range(i + 1, N + 1) :
        for k in range(M+1, N - j + 1) :
            if i + k > j :
                break
            if (hash[j+k] - hash[j] * (26 ** k)) % mod == (hash[i+k] - hash[i] *  (26 ** k)) % mod :
                M += 1
            else :
                break
                
print(M)

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

mod = 10 ** 9 + 7
hash = [0]
pow = [1]
for s in S :
    hash.append((hash[-1] * 26 + ord(s) - 97) % mod)
    pow.append(pow[-1] * 26 % mod)

M = 0
for i in range(N + 1) :
    for j in range(i + 1, N + 1) :
        for k in range(M + 1, N - j + 1) :
            if i + k > j :
                break
            if (hash[j+k] - hash[j] * (pow[k])) % mod == (hash[i+k] - hash[i] *  pow[k]) % mod :
                M += 1
            else :
                break
                
print(M)
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left

N = int(input())
S = [int(i) for i in input().split()]

def solve() :
    S.sort()
    T = [S.pop()]
    for i in range(N) :
        T.sort(reverse=True)
        for j in range(2**i) :
            if S[0] >= T[j] :
                return 'No'
            
            pos = bisect_left(S, T[j])
            T.append(S.pop(pos-1))
            
    return 'Yes'
    
print(solve())

Fixed submission:
N = int(input())
S = [int(i) for i in input().split()]

def solve() :
    S.sort()
    par = [S.pop()]
    rst = S
    for _ in range(N) :
        n_par = []
        n_rst = []
        
        for p in par[::-1] :
            flg = True
            while rst :
                if rst[-1] < p :
                    n_par.append(rst.pop())
                    flg = False
                    break
                else :
                    n_rst.append(rst.pop())
            if flg :
                return 'No'
                
        par += n_par
        par.sort()
        rst += n_rst
        rst.sort()
            
    return 'Yes'
    
print(solve())