Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [0] + list(map(int, input().split())) + [N+1]
B = list(map(int, input().split()))
B_store = B.copy()


def do(A, B):
    ans = []
    ida = 1
    res = True
    while ida < N+1:
        a = A[ida]
        c = 1
        while ida+c < N+2 and A[ida+c] == a:
            c += 1
        
        ida += c
        temp = []
        while c:
            if len(B) == 0:
                res = False
                break
            b = B.pop()
            if b != a:
                ans.append(b)
                c -= 1
            else:
                temp.append(b)
        
        B += temp
        if not res:
            break

    if res:
        return ans
    else:
        return False

ans = do(A, B)
if ans:
    print('Yes')
    print(*ans)

ans = do(A[::-1], B_store[::-1])[::-1]
if ans:
    print('Yes')
    print(*ans)

else:
    print('No')

Fixed submission:
import numpy as np

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

count = [0] * (N+1)
for a, b in zip(A, B):
    count[a] += 1
    count[b] += 1

for i in range(N+1):
    if count[i] > N:
        print('No')
        quit()

diff = 0
checked = set()
ida = 0
for i, b in enumerate(B):
    if b in checked:
        continue
    checked.add(b)
    while ida < N and A[ida] <= b:
        ida += 1
    diff = max(diff, ida - i)


idx = (np.arange(N) - diff) % N
print('Yes')
print(*np.array(B)[idx])
Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())
sx, sy = map(int, input().split())
sx -= 1; sy -= 1
tx, ty = map(int, input().split())
tx -= 1; ty -= 1

S = [input() for _ in range(H)]


dxy = [(-1, 0), (0, -1), (1, 0), (0, 1)]
dist = {(sx, sy) : 0}
next_points = set([(sx, sy)])
def bfs(d):
    global dist, next_points
    stack = list(next_points)
    next_points = set()
    while stack:
        x, y = stack.pop()
        dist[(x, y)] = d
        count = 0
        for dx, dy in dxy:
            xx = x + dx; yy = y + dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy] == '.':
                count += 1
                if (xx, yy) not in dist:
                    dist[(xx, yy)] = d
                    stack.append((xx, yy))
        
        if count < 4:
            for dx in range(-2, 3):
                xx = x + dx
                for dy in range(-2, 3):
                    yy = y + dy
                    if (xx, yy) not in dist and 0 <= xx < H and 0 <= yy < W and S[xx][yy] == '.':
                        next_points.add((xx, yy))

d = 0
while (tx, ty) not in dist:
    bfs(d)
    d += 1
    if len(next_points) == 0:
        if (tx, ty) in dist:
            print(dist[(tx, ty)])
        else:
            print(-1)
        quit()

print(dist[(tx, ty)])

Fixed submission:
H, W = map(int, input().split())
sx, sy = map(int, input().split())
sx -= 1; sy -= 1
tx, ty = map(int, input().split())
tx -= 1; ty -= 1

S = [input() for _ in range(H)]


dxy = [(-1, 0), (0, -1), (1, 0), (0, 1)]
dist = {}
next_points = set([(sx, sy)])
def bfs(d):
    global dist, next_points
    stack = list(next_points)
    next_points = set()
    while stack:
        x, y = stack.pop()
        if (x, y) in dist and dist[(x, y)] < d:
            continue
        dist[(x, y)] = d
        count = 0
        for dx, dy in dxy:
            xx = x + dx; yy = y + dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy] == '.':
                count += 1
                if (xx, yy) not in dist:
                    dist[(xx, yy)] = d
                    stack.append((xx, yy))
        
        if count < 4:
            for dx in range(-2, 3):
                xx = x + dx
                for dy in range(-2, 3):
                    yy = y + dy
                    if (xx, yy) not in dist and 0 <= xx < H and 0 <= yy < W \
                            and S[xx][yy] == '.':
                        next_points.add((xx, yy))

d = 0
while (tx, ty) not in dist:
    bfs(d)
    d += 1
    if len(next_points) == 0:
        if (tx, ty) in dist:
            print(dist[(tx, ty)])
        else:
            print(-1)
        quit()

print(dist[(tx, ty)])
Buggy python submission (verdict: Time Limit Exceeded):
A, B, C, D = map(int, input().split())
MOD = 998244353
dp = [[0]*(D+1) for i in range(C+1)]
for i in range(A, C+1):
    for j in range(B, D+1):
        if (i, j) == (A, B):
            dp[i][j] = 1
        else:
            dp[i][j] = (dp[i-1][j]*j + dp[i][j-1]*i - dp[i-1][j-1]*(i-1)*(j-1)) % MOD

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

Fixed submission:
A, B, C, D = map(int, input().split())
MOD = 998244353
dp = [[0]*(D+1) for i in range(C+1)]
for i in range(A, C+1):
    for j in range(B, D+1):
        if (i, j) == (A, B):
            dp[i][j] = 1
        else:
            dp[i][j] = (dp[i-1][j]*j + dp[i][j-1]*i - dp[i-1][j-1]*(i-1)*(j-1)) % MOD

print(dp[-1][-1])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
A.sort()

is_prime = [True] * (10**6 + 1)
pre_a = 0
for a in A:
    if a == pre_a:
        is_prime[a] = False
    j = 2 * a
    while j <= 10**6:
        is_prime[j] = False
        j += a
    
    pre_a = a

ans = 0
for a in A:
    if is_prime[a]:
        ans += 1

print(ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
S = set(A)
M = max(A)
A.sort()

pre_a = 0
for a in A:
    if a == pre_a:
        S.discard(a)
    if a in S:
        j = a * 2
        while j <= M:
            S.discard(j)
            j += a
    pre_a = a

print(len(S))

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

is_prime = [True] * (10**6 + 1)
pre_a = 0
for a in A:
    if a == pre_a:
        is_prime[a] = False
    j = 2 * a
    while j <= 10**6:
        is_prime[j] = False
        j += a
    
    pre_a = a

ans = 0
for a in A:
    if is_prime[a]:
        ans += 1

print(ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
S = set(A)
M = max(A)
A.sort()

pre_a = 0
for a in A:
    if a == pre_a:
        S.discard(a)
    if a in S:
        j = a * 2
        while j <= M:
            S.discard(j)
            j += a
    pre_a = a

print(len(S))
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate

N, K = map(int, input().split())
A = list(map(int, input().split()))

def do(A):
  B = [0] * (N+2)
  for i, a in enumerate(A, 1):
    l = max(i - a, 0)
    r = min(i + a + 1, N+1)
    B[l] += 1
    B[r] -= 1
  B = list(accumulate(B))
  return B[1:-1]

def check(A):
  for a in A:
    if a < N:
      return False
  return True

for i in range(K):
  A = do(A)
  if check(A):
    print(*A)
    quit()

print(*A)

Fixed submission:
from itertools import accumulate

N, K = map(int, input().split())
A = list(map(int, input().split()))

def do(A):
  B = [0] * (N+2)
  for i, a in enumerate(A, 1):
    l = max(i - a, 0)
    r = min(i + a + 1, N+1)
    B[l] += 1
    B[r] -= 1
  B = list(accumulate(B))
  return B[1:-1]

def check(A):
  for a in A:
    if a < N:
      return False
  return True

for i in range(K):
  A = do(A)
  if check(A):
    print(*A)
    quit()

print(*A)
Buggy python submission (verdict: Time Limit Exceeded):
N, S = map(int, input().split())
MOD = 998244353
A = list(map(int, input().split()))

dp = [[0]*(S+1) for i in range(N+1)]
dp[0][0] = 1
for i, a in  enumerate(A, 1):
  for s in range(S+1):
    dp[i][s] = 2*dp[i-1][s]
    if a <= s:
      dp[i][s] += dp[i-1][s-a]
    dp[i][s] %= MOD

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

Fixed submission:
N, S = map(int, input().split())
MOD = 998244353
A = list(map(int, input().split()))

dp = [[0]*(S+1) for i in range(N+1)]
dp[0][0] = 1
for i, a in  enumerate(A, 1):
  for s in range(S+1):
    dp[i][s] = 2*dp[i-1][s]
    if a <= s:
      dp[i][s] += dp[i-1][s-a]
    dp[i][s] %= MOD

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

Buggy python submission (verdict: Time Limit Exceeded):
# 100% TLE

N, S = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353

dp = [[[0]*(S+1) for j in range(N+1)] for i in range(N+1)]
dp[0][0][0] = 1
for i, a in enumerate(A, 1):
    for j in range(N+1):
        for s in range(S+1):
            dp[i][j][s] = dp[i-1][j][s]
            if s >= a:
                dp[i][j][s] = (dp[i][j][s] + dp[i-1][j-1][s-a] % MOD)


ans = 0
for j in range(N+1):
    ans += dp[-1][j][-1] * pow(2, N-j, MOD) % MOD
    ans %= MOD

print(ans)

Fixed submission:
N, S = map(int, input().split())
MOD = 998244353
A = list(map(int, input().split()))

dp = [[0]*(S+1) for i in range(N+1)]
dp[0][0] = 1
for i, a in  enumerate(A, 1):
  for s in range(S+1):
    dp[i][s] = 2*dp[i-1][s]
    if a <= s:
      dp[i][s] += dp[i-1][s-a]
    dp[i][s] %= MOD

print(dp[-1][-1])
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
from math import gcd

N = int(input())
MOD = 1000000007
d = defaultdict(int)
pow2 = [1]
for i in  range(N):
  pow2.append(pow2[-1] * 2 % MOD)

def to_idx(a, b):
  return tuple(sorted(((a, b), (-a, -b))))

ans = 0
for i in range(N):
  a, b = map(int, input().split())
  g = gcd(a, b)
  a //= g; b //= g
  d[to_idx(a, b)] += 1

memo = []
key_set = set(d.keys())
while key_set:
  k = key_set.pop()
  v1, v2 = k
  a, b = v1
  idx = to_idx(-b, a)
  memo.append((pow2[d[k]] + pow2[d[idx]] - 1) % MOD)
  key_set.discard(idx)

ans = 1
for m in memo:
  ans *= m
  ans %= MOD

print((ans - 1) % MOD)

Fixed submission:
from collections import defaultdict
from math import gcd

N = int(input())
MOD = 1000000007
d = defaultdict(int)
num_00 = 0
pow2 = [1]
for i in range(N):
  pow2.append((pow2[-1] * 2) % MOD)

def to_idx(a, b):
  if a == 0 and b != 0:
    return ((0, -1), (0, 1))
  elif a != 0 and b == 0:
    return ((-1, 0), (1, 0))
  else:
    return tuple(sorted(((a, b), (-a, -b))))

ans = 0
for i in range(N):
  a, b = map(int, input().split())
  if a*b == 0 and a != b:
    d[to_idx(a, b)] += 1
  elif a == b == 0:
    num_00 += 1
  else:
    g = gcd(a, b)
    a //= g; b //= g
    d[to_idx(a, b)] += 1

memo = []
key_set = set(d.keys())
while key_set:
  k = key_set.pop()
  v1, v2 = k
  a, b = v1
  idx = to_idx(-b, a)
  memo.append((pow2[d[k]] + pow2[d[idx]] - 1) % MOD)
  key_set.discard(idx)

ans = 1
for m in memo:
  ans *= m
  ans %= MOD

print((ans - 1 + num_00) % MOD)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))

stack = [1]
s = {1}

def dfs(a, k):
  global stack
  global s
  if k == 0:
    return a
  next_a = A[a]
  if next_a in s:
    idx = stack.index(next_a)
    n = len(stack)
    k = (k - 1)%(n - idx)
    return stack[idx + k]
  else:
    stack.append(next_a)
    s.add(next_a)
    res = dfs(next_a, k-1)
  return res

print(dfs(1, K))

Fixed submission:
N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))

d = {1:0}
pre_a = 0
a = 1
c = 0
while K:
    K -= 1
    next_a = A[a]
    c += 1
    if next_a in d:
        idx = d[next_a]
        n = len(d)
        K %= (n - idx)
        K += 1
        break
    else:
        d[next_a] = c
        pre_a = a
        a = next_a

while K:
    pre_a = a
    a = A[a]
    K -= 1

print(a)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)

N, K = map(int, input().split())
A = list(map(int, input().split()))

stack = [0]
def dfs(a, k):
    global stack
    if k == 0:
        return a
    if k == -1:
        return stack[-1]
    next_a = A[a]-1
    if next_a in stack:
        idx = stack.index(next_a)
        n = len(stack)
        k %= (n - idx)
        res = dfs(next_a, k - 1)
    else:
        stack.append(next_a)
        res = dfs(next_a, k-1)
    return res

print(dfs(0, K) + 1)

Fixed submission:
N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))

d = {1:0}
pre_a = 0
a = 1
c = 0
while K:
    K -= 1
    next_a = A[a]
    c += 1
    if next_a in d:
        idx = d[next_a]
        n = len(d)
        K %= (n - idx)
        K += 1
        break
    else:
        d[next_a] = c
        pre_a = a
        a = next_a

while K:
    pre_a = a
    a = A[a]
    K -= 1

print(a)

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
A = list(map(int, input().split()))

stack = [0]
def dfs(a, k):
    global stack
    if k == 0:
        return a
    if k == -1:
        return stack[-1]
    next_a = A[a]-1
    if next_a in stack:
        idx = stack.index(next_a)
        n = len(stack)
        k %= (n - idx)
        res = dfs(next_a, k - 1)
    else:
        stack.append(next_a)
        res = dfs(next_a, k-1)
    return res

print(dfs(0, K) + 1)

Fixed submission:
N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))

d = {1:0}
pre_a = 0
a = 1
c = 0
while K:
    K -= 1
    next_a = A[a]
    c += 1
    if next_a in d:
        idx = d[next_a]
        n = len(d)
        K %= (n - idx)
        K += 1
        break
    else:
        d[next_a] = c
        pre_a = a
        a = next_a

while K:
    pre_a = a
    a = A[a]
    K -= 1

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

memo1 = []
memo2 = []
for i in range(N):
  S = input()
  sum_n = min_n = 0
  for s in S:
    if s == ')':
      sum_n -= 1
      min_n = min(min_n, sum_n)
    else:
      sum_n += 1
  if sum_n >= 0:
    memo1.append([min_n, sum_n])
  else:
    memo2.append([min_n-sum_n, -sum_n])

memo1.sort(reverse=True)
left = 0
for min_n, sum_n in memo1:
  if left + min_n < 0:
    print('No')
    quit()
  else:
    left += sum_n

memo2.sort(reverse=True)
right = 0
for min_n, sum_n in memo2:
  if right + min_n < 0:
    print('No')
    quit()
  else:
    right += sum_n

if left == right:
  print('Yes')
else:
  print('No')

Fixed submission:
N = int(input())

memo1 = []
memo2 = []
for i in range(N):
  S = input()
  sum_n = min_n = 0
  for s in S:
    if s == ')':
      sum_n -= 1
      min_n = min(min_n, sum_n)
    else:
      sum_n += 1
  if sum_n >= 0:
    memo1.append([min_n, sum_n])
  else:
    memo2.append([min_n-sum_n, -sum_n])

memo1.sort(reverse=True)
left = 0
for min_n, sum_n in memo1:
  if left + min_n < 0:
    print('No')
    quit()
  else:
    left += sum_n

memo2.sort(reverse=True)
right = 0
for min_n, sum_n in memo2:
  if right + min_n < 0:
    print('No')
    quit()
  else:
    right += sum_n

if left == right:
  print('Yes')
else:
  print('No')
Buggy python submission (verdict: Runtime Error):
import bisect

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

tree = [[] for i in range(N)]
for i in range(N-1):
  u, v = map(int, input().split())
  tree[u-1].append(v-1)
  tree[v-1].append(u-1)


ans = [0] * N
ans[0] = 1
dp = []
def dfs(node, par, dp):
  global ans
  children = tree[node]
  for child in children:
    if child == par:
      continue
    num = A[child]
    idx = bisect.bisect_left(dp, num)
    if idx == len(dp):
      _dp = dp.copy() + [num]
      ans[child] = idx + 1
      dfs(child, node, _dp)
    else:
      _dp = dp.copy()
      _dp[idx] = num
      ans[child] = idx + 1
      dfs(child, node, _dp)

dp = [A[0]]
dfs(0, -1, dp)
print(*ans, sep='\n')

Fixed submission:
import bisect
import sys
sys.setrecursionlimit(10**9)

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

tree = [[] for i in range(N)]
for i in range(N-1):
  u, v = map(int, input().split())
  tree[u-1].append(v-1); tree[v-1].append(u-1)


ans = [0] * N
ans[0] = 1
INF = 10**10
dp = [INF] * N
dp[0] = A[0]
stack = []
def dfs(node, par):
  global ans
  global dp
  global stack
  children = tree[node]
  for child in children:
    if child == par:
      continue
    num = A[child]
    idx = bisect.bisect_left(dp, num)
    stack.append([idx, dp[idx]])
    dp[idx] = num
    ans[child] = bisect.bisect_left(dp, INF)
    dfs(child, node)
    # 巻き戻し
    idx, num = stack.pop()
    dp[idx] = num

dfs(0, -1)
print(*ans, sep='\n')
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
MOD = 10**9 + 7

dp = [0] * (K + 1)
ans = 0
for k in range(K, 0, -1):
    num = K // k
    dp[k] = pow(num, N)
    for n in range(2, num+1):
        if n*k <= K:
            dp[k] -= dp[n*k]
            dp[k] %= MOD

    ans += dp[k] * k % MOD
    ans %= MOD

print(ans)

Fixed submission:
N, K = map(int, input().split())
MOD = 10**9 + 7

dp = [0] * (K + 1)
ans = 0
for k in range(K, 0, -1):
    num = K // k
    dp[k] = pow(num, N, MOD)
    for n in range(2, num+1):
        if n*k <= K:
            dp[k] -= dp[n*k]
            dp[k] %= MOD

    ans += dp[k] * k % MOD
    ans %= MOD

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)

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

def solve_even(a, n):
  s = sum(a[::2])
  ans = s
  i = n - 2
  while i >= 0:
    s += a[i+1] - a[i]
    ans = max(ans, s)
    i -= 2
  return ans

def solve_odd(a, n):
  if n == 1:
    return 0
  ans = solve_even(a[:-1], n-1)
  s = a.pop()
  a.pop()
  ans = max(ans, s + solve_odd(a, n-2))
  return ans
  

if N%2 == 0:
  print(solve_even(A, N))
else:
  print(solve_odd(A, N))

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

dp = [0] * (N + 1)
dp[2] = max(A[0], A[1])
s = A[0]
for i, a in enumerate(A, 1):
  if i <= 2:
    continue
  if i%2: # 奇数
    dp[i] = max(dp[i-1], a+dp[i-2])
    s += a
  else: # 偶数
    dp[i] = max(a+dp[i-2], s)

print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)

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

def solve_even(a, n):
  s = sum(a[::2])
  ans = s
  i = n - 2
  while i >= 0:
    s += a[i+1] - a[i]
    ans = max(ans, s)
    i -= 2
  return ans

def solve_odd(a, n):
  if n == 1:
    return 0
  ans = solve_even(a[:-1], n-1)
  s = a.pop()
  a.pop()
  ans = max(ans, s + solve_odd(a, n-2))
  return ans
  

if N%2 == 0:
  print(solve_even(A, N))
else:
  print(solve_odd(A, N))

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

dp = [0] * (N + 1)
dp[2] = max(A[0], A[1])
s = A[0]
for i, a in enumerate(A, 1):
  if i <= 2:
    continue
  if i%2: # 奇数
    dp[i] = max(dp[i-1], a+dp[i-2])
    s += a
  else: # 偶数
    dp[i] = max(a+dp[i-2], s)

print(dp[-1])
Buggy python submission (verdict: Runtime Error):
cands = [1, 2, 3, 4, 5, 6, 7, 8, 9]

def add_v(v):
  global cands
  global K
  v0 = v % 10
  v0 = int(v[-1])
  if v0 == 0:
    cands += [v*10, v*10+1]
    K -=2
  elif v0 == 9:
    cands += [v*10+8, v*10+9]
    K -= 2
  else:
    cands += [v*10+v0-1, v*10+v0, v*10+v0+1]
    K -= 3

K = int(input())
idk = K
K -= 9
idx = 0
while K >= 0:
  add_v(cands[idx])
  idx += 1

print(cands[idk-1])

Fixed submission:
cands = [1, 2, 3, 4, 5, 6, 7, 8, 9]

def add_v(v):
  global cands
  global K
  v = str(v)
  v0 = int(v[-1])
  if v0 == 0:
    cands += [int(v+'0'), int(v+'1')]
    K -=2
  elif v0 == 9:
    cands += [int(v+'8'), int(v+'9')]
    K -= 2
  else:
    cands += [int(v+str(v0-1)), int(v+str(v0)), int(v+str(v0+1))]
    K -= 3

K = int(input())
idk = K
K -= 9
idx = 0
while K >= 0:
  add_v(cands[idx])
  idx += 1

print(cands[idk-1])
Buggy python submission (verdict: Runtime Error):
N = int(input())

def check(p):
  _N = N
  while _N%p == 0:
    _N //= p
  return (_N-1)%p == 0

n = int(N**0.5) + 1
P0 = set([N])
P1 = set([N-1])
for i in range(2, n+1):
  if (N-1)%i == 0:
    P1.add(i)
    P1.add((N-1)//i)
  if N%i == 0:
    P0.add(i)
    P0.add(N//i)

P2.discard(1)
P1.discard(1)
ans = len(P1)
for p in P0:
  ans += check(p)

print(ans)

Fixed submission:
N = int(input())

def check(p):
  _N = N
  while _N%p == 0:
    _N //= p
  return (_N-1)%p == 0

n = int(N**0.5) + 1
P0 = set([N])
P1 = set([N-1])
for i in range(2, n+1):
  if (N-1)%i == 0:
    P1.add(i)
    P1.add((N-1)//i)
  if N%i == 0:
    P0.add(i)
    P0.add(N//i)

P0.discard(1)
P1.discard(1)
ans = len(P1)
for p in P0:
  ans += check(p)

print(ans)

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

def check(p):
  _N = N
  while _N%p == 0:
    _N //= p
  return ((_N-1)%p == 0) or (_N == 1)

n = int(N**0.5) + 1
P0 = set([N])
P1 = set([N-1])
for i in range(2, n+1):
  if (N-1)%i == 0:
    P1.add(i)
    P1.add((N-1)//i)
  if N%i == 0:
    P0.add(i)
    P0.add(N//i)

ans = len(P1)
for p in P0:
  ans += check(p)

print(ans)

Fixed submission:
N = int(input())

def check(p):
  _N = N
  while _N%p == 0:
    _N //= p
  return (_N-1)%p == 0

n = int(N**0.5) + 1
P0 = set([N])
P1 = set([N-1])
for i in range(2, n+1):
  if (N-1)%i == 0:
    P1.add(i)
    P1.add((N-1)//i)
  if N%i == 0:
    P0.add(i)
    P0.add(N//i)

P0.discard(1)
P1.discard(1)
ans = len(P1)
for p in P0:
  ans += check(p)

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

# 横の割り方を全通り試す(2**(H-1))
ans = float('inf')
for i in range(2**(H-1)):
    _ans = bin(i).count('1')
    chocos = [list(map(int, S[0]))]
    for j in range(H-1):
        if i >> j & 1:
            chocos.append(list(map(int, S[j+1])))
        else:
            for w in range(W):
                chocos[-1][w] += int(S[j+1][w])
    
    ns = len(chocos)
    nums = [0] * ns
    is_next = False
    flag = False
    for w in range(W):
        for j in range(ns):
            nums[j] += chocos[j][w]
            if chocos[j][w] > K:
                _ans = float('inf')
                flag = True
                break
            if nums[j] > K:
                _ans += 1
                is_next = True
                break
        if flag:
          flag = False
          break        
        if is_next:
            for j in range(ns):
                nums[j] = chocos[j][w]
            is_next = False
    
    ans = min(ans, _ans)

print(ans)

Fixed submission:
H, W, K = map(int, input().split())
S = [input() for h in range(H)]

# 横の割り方を全通り試す(2**(H-1))
ans = float('inf')
for i in range(2**(H-1)):
    _ans = bin(i).count('1')
    chocos = [list(map(int, S[0]))]
    for j in range(H-1):
        if i >> j & 1:
            chocos.append(list(map(int, S[j+1])))
        else:
            for w in range(W):
                chocos[-1][w] += int(S[j+1][w])
    
    ns = len(chocos)
    nums = [0] * ns
    is_next = False
    for w in range(W):
        for j in range(ns):
            nums[j] += chocos[j][w]
            if chocos[j][w] > K:
                _ans = float('inf')
            if nums[j] > K:
                _ans += 1
                is_next = True
                break
        
        if is_next:
            for j in range(ns):
                nums[j] = chocos[j][w]
            is_next = False
    
    ans = min(ans, _ans)

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

# dp[i][s] : Rをiに固定した時に、和がsとなる整数列の組が何回現れるか
dp = [[0]*(S+1) for i in range(N+1)]
ans = 0

for i, a in enumerate(A, 1):
  for s in range(S+1):
    dp[i][s] = dp[i-1][s]
    dp[i][s] += s==0 or s==a
    if s >= a:
      dp[i][s] = (dp[i][s] + dp[i-1][s-a]) % MOD
  ans = (ans + dp[i][-1]) % MOD # R=i, L=1,2,...i(=R)のf(L, R)を加算

print(ans)

Fixed submission:
N, S = map(int, input().split())
MOD = 998244353
A = list(map(int, input().split()))

# dp[i][s] : Rをiに固定した時に、和がsとなる整数列の組が何回現れるか
dp = [[0]*(S+1) for i in range(N+1)]
ans = 0

for i, a in enumerate(A, 1):
  for s in range(S+1):
    dp[i][s] = dp[i-1][s]
    dp[i][s] += s==0 or s==a
    if s >= a:
      dp[i][s] = (dp[i][s] + dp[i-1][s-a]) % MOD
  ans = (ans + dp[i][-1]) % MOD

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

inv = 0
for i in range(Q):
  query = input().split()
  if query == ['1']:
    inv = (inv + 1)%2
  else:
    f, c = query[1], query[2]
    if f == '1':
      if inv:
        S += c
      else:
        S = c + S
    else:
      if inv:
        S = c + S
      else:
        S += c

if inv:
  print(S[::-1])
else:
  print(S)

Fixed submission:
from collections import deque

S = deque(list(input()))
Q = int(input())

inv = 0
for i in range(Q):
  query = input().split()
  if query == ['1']:
    inv = (inv + 1)%2
  else:
    f, c = query[1], query[2]
    if f == '1':
      if inv:
        S.append(c)
      else:
        S.appendleft(c)
    else:
      if inv:
        S.appendleft(c)
      else:
        S.append(c)

S = list(S)
if inv:
  print(''.join(S[::-1]))
else:
  print(''.join(S))