Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict as dd
import bisect
n, m = map(int, input().split())
A = sorted(list(map(int, input().split())))
BC = dd(lambda: 0)
for i in range(m):
  b, c = map(int, input().split())
  BC[b] += c
print(BC)  

right_dic = {}
leht_dic = {}
for key in sorted(BC.keys(), reverse=True):
  

Fixed submission:
from collections import defaultdict as dd
from collections import deque
from collections import Counter as cnt
import bisect
n, m = map(int, input().split())
A = list(map(int, input().split()))
temoti_dic = cnt(A)

add_card_dic = dd(lambda: 0)
for i in range(m):
    b, c = map(int, input().split())
    add_card_dic[c] += b

temoti_dq = deque(sorted(temoti_dic.keys()))

total = 0
for add_card in sorted(add_card_dic.keys(), reverse=True):
    pointer = bisect.bisect_left(temoti_dq, add_card)
    #print(temoti_dic, temoti_dq, add_card, add_card_dic[add_card], pointer)
    if pointer == 0:
        break
    else:
        i = 0
        add_card_num = add_card_dic[add_card]
        while add_card_num > 0 and i < pointer:
            least_temoti = temoti_dq[0]
            least_temoti_num = temoti_dic[least_temoti]
            if least_temoti_num <= add_card_num:
                total += least_temoti_num * add_card
                temoti_dq.popleft()
                del temoti_dic[least_temoti]
                add_card_num -= least_temoti_num
            else:
                temoti_dic[least_temoti] -= add_card_num
                total += add_card_num * add_card
                add_card_num = 0
            i += 1

#print(temoti_dic)
for key in temoti_dq:
    total += key * temoti_dic[key]

print(total)
Buggy python submission (verdict: Time Limit Exceeded):
r, g, b, n = [int(num) for num in input().split()]

#総当たり
counter = 0
for r_c in range(0, n // r + 1):
  for g_c in range(0, n // g + 1):
    for b_c in range(0, n // b + 1):
      if (r_c * r + g_c * g + b_c * b) == n:
        counter += 1
print(counter)

Fixed submission:
r, g, b, n = [int(num) for num in input().split()]
arr = [r, g, b]
arr.sort()

#総当たり
counter = 0
for c_1 in range(0, n // arr[-1] + 1):
  for c_2 in range(0, n // arr[-2] + 1):
      if n - c_1 * arr[-1] - c_2 * arr[-2] < 0:
        break
      if (n - c_1 * arr[-1] - c_2 * arr[-2]) % arr[-3] == 0:
        counter += 1
print(counter)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict as dd
from math import ceil
n = int(input())
A = list(map(int, input().split()))

def Prime_factorization(num):
  ans_dic = dd(lambda: 0)
  for divisor in range(2, ceil(num**0.5) + 2):
    while num % divisor == 0:
      num //= divisor
      ans_dic[divisor] += 1
  else:
    if len(ans_dic.keys()) == 0:
      ans_dic[num] += 1
  return ans_dic

GCDs = {}
for num in A:
  GCDs[num] = Prime_factorization(num)
#print(GCDs)
    
def marge(A, GCDs, skip):
  keys = set()
  #keyを作成
  for i in range(len(A)):
    if i != skip:
      keys = keys | set(GCDs[A[i]].keys())
  #print(keys)
  #gcdを計算
  #各keyの個数の最小数を算出
  gcd = 1
  for prime in keys:
    min_num_prime = 10**9
    for i in range(len(A)):
      if i != skip:
        min_num_prime = min(GCDs[A[i]][prime], min_num_prime)
    gcd *= prime**min_num_prime
  return gcd  
  
max_gcd = 0
for i in range(len(A)):
  max_gcd = max(marge(A, GCDs, skip=i), max_gcd)
print(max_gcd)

Fixed submission:
from fractions import gcd
n = int(input())
A = list(map(int, input().split()))

L = {}
R = {}

L[0] = A[0]
#print("L", 0, L[0])
for i in range(n-1):
  L[i+1] = gcd(L[i], A[i+1])
  #print("L", i+1, L[i+1])

R[n-1] = A[n-1]
#print("R", n-1, R[n-1])
for i in range(n-1):
  R[n-2-i] = gcd(R[n-1-i], A[n-2-i])
  #print("R", n-2-i, R[n-2-i])
  
max_gcd = 0
for i in range(1, n-1):
  max_gcd = max(gcd(L[i-1], R[i+1]), max_gcd)
  #print(i, L[i-1], R[i+1], gcd(L[i-1], R[i+1]))
max_gcd = max((max_gcd, L[n-2], R[1]))
print(max_gcd)

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

from fractions import gcd
from functools import reduce
max_gcd = 0

for i in range(n+1):
  max_gcd = max(max_gcd, reduce(gcd, A[:i] + A[i+1:]))
print(max_gcd)  

Fixed submission:
from fractions import gcd
n = int(input())
A = list(map(int, input().split()))

L = {}
R = {}

L[0] = A[0]
#print("L", 0, L[0])
for i in range(n-1):
  L[i+1] = gcd(L[i], A[i+1])
  #print("L", i+1, L[i+1])

R[n-1] = A[n-1]
#print("R", n-1, R[n-1])
for i in range(n-1):
  R[n-2-i] = gcd(R[n-1-i], A[n-2-i])
  #print("R", n-2-i, R[n-2-i])
  
max_gcd = 0
for i in range(1, n-1):
  max_gcd = max(gcd(L[i-1], R[i+1]), max_gcd)
  #print(i, L[i-1], R[i+1], gcd(L[i-1], R[i+1]))
max_gcd = max((max_gcd, L[n-2], R[1]))
print(max_gcd)
Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
S = input()

Sev = [0] * n
for i in range(n-1):
  if S[i] == "A" and S[i+1] == "C":
    Sev[i] = 1

for i in range(q):
  l, r = map(int, input().split())
  l = l-1
  r = r-1
  print(sum(Sev[l:r]))

Fixed submission:
n, q = map(int, input().split())
S = input()

Sev = [0] * n
for i in range(n-1):
  if S[i] == "A" and S[i+1] == "C":
    Sev[i] = 1

Simos = [0] * n
Simos[0] = Sev[0]
for i in range(1, n):
  Simos[i] = Simos[i-1] + Sev[i]
    
for i in range(q):
  l, r = map(int, input().split())
  l = l-1
  r = r-1
  r = r-1
  if l == 0:
    print(Simos[r])
  else:
    print(Simos[r] - Simos[l-1])

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

for i in range(q):
  l, r = map(int, input().split())
  l = l-1
  r = r-1
  counter = 0
  for j in range(r - l):
    if S[l+j] == "A" and S[l+j+1] == "C":
      counter += 1
  print(counter)
    

Fixed submission:
n, q = map(int, input().split())
S = input()

Sev = [0] * n
for i in range(n-1):
  if S[i] == "A" and S[i+1] == "C":
    Sev[i] = 1

Simos = [0] * n
Simos[0] = Sev[0]
for i in range(1, n):
  Simos[i] = Simos[i-1] + Sev[i]
    
for i in range(q):
  l, r = map(int, input().split())
  l = l-1
  r = r-1
  r = r-1
  if l == 0:
    print(Simos[r])
  else:
    print(Simos[r] - Simos[l-1])

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

for i in range(q):
  l, r = map(int, input().split())
  l = l-1
  r = r-1
  if r - l < 1:
    print(0)
  else:
    counter = 0
    for j in range(r - l):
      if S[l+j] == "A" and S[l+j+1] == "C":
        counter += 1
    print(counter)
    

Fixed submission:
n, q = map(int, input().split())
S = input()

Sev = [0] * n
for i in range(n-1):
  if S[i] == "A" and S[i+1] == "C":
    Sev[i] = 1

Simos = [0] * n
Simos[0] = Sev[0]
for i in range(1, n):
  Simos[i] = Simos[i-1] + Sev[i]
    
for i in range(q):
  l, r = map(int, input().split())
  l = l-1
  r = r-1
  r = r-1
  if l == 0:
    print(Simos[r])
  else:
    print(Simos[r] - Simos[l-1])

Buggy python submission (verdict: Runtime Error):
n, q = map(int, input().split())
s = input()
for i in range(q):
  l, r = map(int, input().split())
  substring = s[1 - 1 : r]
  print(substring)
  sp = substring.replace('AC', '+')
  print(sp)
  print(sp.count("+"))

  

Fixed submission:
n, q = map(int, input().split())
S = input()

Sev = [0] * n
for i in range(n-1):
  if S[i] == "A" and S[i+1] == "C":
    Sev[i] = 1

Simos = [0] * n
Simos[0] = Sev[0]
for i in range(1, n):
  Simos[i] = Simos[i-1] + Sev[i]
    
for i in range(q):
  l, r = map(int, input().split())
  l = l-1
  r = r-1
  r = r-1
  if l == 0:
    print(Simos[r])
  else:
    print(Simos[r] - Simos[l-1])
Buggy python submission (verdict: Time Limit Exceeded):
s = list(input())
counter = 0
flag = True
while flag:
  for pointer in range(0, len(s)-1):
    if s[pointer] != s[pointer + 1]:
      del s[pointer:pointer+2]
      counter += 2
      break
  else:
    flag = False
print(counter)

Fixed submission:
s = list(input())
r = s.count("0")
b = s.count("1")
print(min(r, b) * 2)
Buggy python submission (verdict: Time Limit Exceeded):
a, b, q = map(int, input().split())
S = [0] * a
T = [0] * b
X = [0] * q
for i in range(a):
  S[i] = int(input())
S = [-10**10*2-1] + S + [10**10*2+1]
for i in range(b):
  T[i] = int(input())
T = [-10**10*2-1] + T + [10**10*2+1]
for i in range(q):
  X[i] = int(input())
#print(S)  
#print(T)  
from bisect import bisect_left
from bisect import bisect_right
for i in range(q):
  s_left = bisect_right(S, X[i]) - 1
  s_right = bisect_right(S, X[i])
  t_left = bisect_right(T, X[i]) - 1
  t_right = bisect_right(T, X[i])
  #print(X[i], S[s_left], S[s_right], T[t_right], T[t_left])
  l_rr = max(S[s_right] - X[i], T[t_right] - X[i])
  l_ll = max(X[i] - S[s_left], X[i] - T[t_left])
  l_rslt = (S[s_right] - X[i]) + (S[s_right] - T[t_left])
  l_rtls = (T[t_right] - X[i]) + (T[t_right] - S[s_left])
  l_lsrt = (X[i] - S[s_left]) + (T[t_right] - S[s_left])
  l_ltrs = (X[i] - T[t_left]) + (S[s_right] - T[t_left])
  print(min(l_rr, l_ll, l_rslt, l_rtls, l_lsrt, l_ltrs))
  

Fixed submission:
a, b, q = map(int, input().split())
S = [0] * a
T = [0] * b
X = [0] * q
for i in range(a):
  S[i] = int(input())
S = [-10**10*2-1] + S + [10**10*2+1]
for i in range(b):
  T[i] = int(input())
T = [-10**10*2-1] + T + [10**10*2+1]
for i in range(q):
  X[i] = int(input())
#print(S)  
#print(T)  
from bisect import bisect_right
for i in range(q):
  x = X[i]
  s_left = bisect_right(S, x) - 1
  s_right = bisect_right(S, x)
  t_left = bisect_right(T, x) - 1
  t_right = bisect_right(T, x)
  sl = S[s_left]
  sr = S[s_right]
  tl = T[t_left]
  tr = T[t_right]
  #print(X[i], S[s_left], S[s_right], T[t_right], T[t_left])
  l_rr = max(sr - x, tr - x)
  l_ll = max(x - sl, x - tl)
  l_rslt = (sr - x) + (sr - tl)
  l_rtls = (tr - x) + (tr - sl)
  l_lsrt = (x - sl) + (tr - sl)
  l_ltrs = (x - tl) + (sr - tl)
  print(min(l_rr, l_ll, l_rslt, l_rtls, l_lsrt, l_ltrs))
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
X = sorted(list(map(int, input().split())))
Diffs = [0] + [X[i] - X[i-1] for i in range(1, m)]
for i in range(n-1):
  m = Diffs.index(max(Diffs))
  Diffs[m] = 0
print(sum(Diffs))


Fixed submission:
n, m = map(int, input().split())
X = sorted(list(map(int, input().split())))
Diffs = [0] + [X[i] - X[i-1] for i in range(1, m)]

if n >= m:
  print(0)
elif n == 1:
  Diffs.sort()
  print(sum(Diffs))
else:
  Diffs.sort()
  print(sum(Diffs[:-(n-1)]))
Buggy python submission (verdict: Time Limit Exceeded):
s = list(input())
counter = 0
flag = False
while flag == False:
  for i in range(len(s) - 1):
    if s[i] == "B" and s[i+1] == "W":
      s[i] = "W"
      s[i+1] = "B"
      counter += 1
      break
  else:
    flag = True
print(counter)

Fixed submission:
s = list(input())
total_l = 0
for i in range(len(s)):
  if s[i] == "W":
    total_l += i
minus = sum(list(range(s.count("W"))))
print(total_l - minus)
Buggy python submission (verdict: Time Limit Exceeded):
n, x = map(int, input().split())
def burger(x):
  if x == 0:
    return "P"
  else:
    return "B" + burger(x-1) + "P" + burger(x-1) + "B"
print(burger(n)[:x].count("P"))

Fixed submission:
n, x = map(int, input().split())
L = [1] * n
P_num = [1] * n

for i in range(n-1):
  L[i + 1] = L[i] * 2 + 3
  P_num[i + 1] = P_num[i] * 2 + 1

def pati_num(n, x):
  if n == 0:
    if x >= 1:
      return 1
    else:
      return 0
  elif x <= 1 + L[n-1]:
    return pati_num(n-1, x-1)
  else:
    return P_num[n-1] + 1 + pati_num(n-1, x-2-L[n-1])
print(pati_num(n, x))
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
from collections import defaultdict as dd
from bisect import insort
PY = dd(lambda:[0])
IMP = [[]] * m
for i in range(m):
  p, y = map(int, input().split())
  Year_lis = PY[p]
  insort(Year_lis, y)
  PY[p] = Year_lis
  IMP[i] = [p, y]
#print(PY)
#for key in PY.keys():
#  PY[key] = sorted(PY[key])
for imp in IMP:
  print("{:0=6}".format(imp[0]), end="")
  pos = PY[imp[0]].index(imp[1])
  print("{:0=6}".format(pos))

Fixed submission:
n, m = map(int, input().split())
L = []
for i in range(m):
  L.append([i] + list(map(int, input().split() + ["000000000000"])))
L.sort(key=lambda x:(x[1], x[2]))
#print(L)

counter = 1
city = 0
for i in range(m):
  if city == L[i][1]:
    counter += 1
  else:
    counter = 1
  L[i][3] = str(L[i][1]).zfill(6) + str(counter).zfill(6)
  city = L[i][1]
#print(L)
L.sort(key=lambda x:x[0])
for i in range(m):
  print(L[i][3])

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
from collections import defaultdict as dd
PY = dd(lambda:[])
IMP = [[]] * m
for i in range(m):
  p, y = map(int, input().split())
  PY[p] += [y]
  IMP[i] = [p, y]
#print(PY)
for key in PY.keys():
  PY[key] = sorted(PY[key])
for imp in IMP:
  print("{:0=6}".format(imp[0]), end="")
  pos = PY[imp[0]].index(imp[1])
  print("{:0=6}".format(pos+1))

Fixed submission:
n, m = map(int, input().split())
L = []
for i in range(m):
  L.append([i] + list(map(int, input().split() + ["000000000000"])))
L.sort(key=lambda x:(x[1], x[2]))
#print(L)

counter = 1
city = 0
for i in range(m):
  if city == L[i][1]:
    counter += 1
  else:
    counter = 1
  L[i][3] = str(L[i][1]).zfill(6) + str(counter).zfill(6)
  city = L[i][1]
#print(L)
L.sort(key=lambda x:x[0])
for i in range(m):
  print(L[i][3])

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

lis = [""] * (m * 4)
set_P = set() 
for i in range(0, m * 4, 4):
  p, y = map(int, input().split())
  lis[i] = i // 4
  lis[i+1] = p
  lis[i+2] = y
  set_P.add(p)

for p in list(set_P):
  y_lis = []
  for i in range(0, m * 4, 4):
    if lis[i + 1] == p:
      y_lis.append([lis[i], lis[i+2]])
  y_lis.sort(key=lambda y_lis:(y_lis[1]))
  for i, city in enumerate(y_lis):
    lis[city[0]*4 + 3] = i + 1
    
for i in range(0, m*4, 4):
  print("{:0=6}".format(lis[i+1]) + "{:0=6}".format(lis[i+3]))

Fixed submission:
n, m = map(int, input().split())
L = []
for i in range(m):
  L.append([i] + list(map(int, input().split() + ["000000000000"])))
L.sort(key=lambda x:(x[1], x[2]))
#print(L)

counter = 1
city = 0
for i in range(m):
  if city == L[i][1]:
    counter += 1
  else:
    counter = 1
  L[i][3] = str(L[i][1]).zfill(6) + str(counter).zfill(6)
  city = L[i][1]
#print(L)
L.sort(key=lambda x:x[0])
for i in range(m):
  print(L[i][3])
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict as dd
import sys
import math
n, m = map(int, input().split())
dic = dd(int)

#M=1
if m == 1:
    print(1)
    sys.exit()
elif n == 1:
    print(1)
    sys.exit()

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

for i in range(2, math.ceil(m**0.5) + 3):
    while m % i == 0:
        m //= i
        dic[i] += 1
else:
    if m != 1:
        dic[m] = 1
#print(dic)

ans = 1
mod = 10**9 + 7
for count in dic.values():
    ans *= combinations_count(count + n - 1, n-1) % mod

print(ans % mod)

Fixed submission:
from collections import defaultdict as dd
from sys import exit
import math
n, m = map(int, input().split())
dic = dd(int)

#M=1
if m == 1:
    print(1)
    exit()

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

for i in range(2, math.ceil(m**0.5) + 3):
    while m % i == 0:
        m //= i
        dic[i] += 1
if m != 1:
    dic[m] = 1
#print(dic)

ans = 1
mod = 10**9 + 7
for count in dic.values():
    ans *= combinations_count(count + n - 1, n-1) % mod

print(ans % mod)

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict as dd
import sys
import math
n, m = map(int, input().split())
dic = dd(int)

#M=1
if m == 1:
    print(1)
    sys.exit()
elif n == 1:
    print(1)
    sys.exit()

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

for i in range(2, math.ceil(m**0.5) + 3):
    while m % i == 0:
        m //= i
        dic[i] += 1
else:
    m != 1:
        dic[m] = 1
#print(dic)

ans = 1
mod = 10**9 + 7
for count in dic.values():
    ans *= combinations_count(count + n - 1, n-1) % mod

print(ans % mod)

Fixed submission:
from collections import defaultdict as dd
from sys import exit
import math
n, m = map(int, input().split())
dic = dd(int)

#M=1
if m == 1:
    print(1)
    exit()

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

for i in range(2, math.ceil(m**0.5) + 3):
    while m % i == 0:
        m //= i
        dic[i] += 1
if m != 1:
    dic[m] = 1
#print(dic)

ans = 1
mod = 10**9 + 7
for count in dic.values():
    ans *= combinations_count(count + n - 1, n-1) % mod

print(ans % mod)
Buggy python submission (verdict: Runtime Error):
h, w = [int(num) for num in input().split()]
lis = []
for i in range(h):
  lis.append([a for a in input()])

def h_remove():
  pop_list = []
  h_c = 0
  pop_flag = False
  global h, w, lis
  while h_c < h:
    if lis[h_c].count("#") == w  or  lis[h_c].count(".") == w:
      lis.pop(h_c)
      h -= 1
      pop_flag = True
    else:
      h_c += 1
  return pop_flag

def transpose(list):
  return [[arr_w[i] for arr_w in list] for i in range(len(list[0]))]

def w_remove():
  global h, w, lis
  lis = transpose(lis)
  h, w = w, h
  pop_flag = h_remove()
  lis = transpose(lis)
  h, w = w, h
  return pop_flag

lis = transpose(transpose(lis))

pop_h, pop_w = True, True
while (pop_h == True) or (pop_w == True):
  pop_h = h_remove()
  pop_w = w_remove()
print(lis)

Fixed submission:
h, w = map(int, input().split())

pic = [""] * h
for i in range(h):
  pic[i] = input()

row = [False] * h
col = [False] * w
for i in range(h):
  for j in range(w):
    if pic[i][j] == "#":
      row[i] = True
      col[j] = True

for i in range(h):
  if row[i] == True:
    for j in range(w):
      if col[j] == True:
        print(pic[i][j], end = "")
    print()
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
X = list(map(int, input().split()))

for i in range(n):
  if X[i] > 0:
    over_zero = i
    break
else:
  over_zero = n

min_cost = 10**8
#プラス側でトライ
if over_zero + k - 1 < n:
  min_cost = X[over_zero + k - 1]
#マイナス側でトライ
if over_zero - k >= 0:
  min_cost = min(X[over_zero - k], min_cost)
for i in range(0, k+1):
  #マイナスサーチ
  if over_zero - i >= 0:
    minus_cost = -(X[over_zero - i])
  else:
    continue
  #プラスサーチ
  if over_zero + k - i - 1 < n:
    plus_cost = (X[over_zero + k - i - 1])
  else:
    continue
  cost = plus_cost + minus_cost + min(plus_cost, minus_cost) 
  min_cost = min(cost, min_cost)

print(min_cost)

Fixed submission:

n,k=map(int,input().split())
x=sorted(list(map(int,input().split())))
print(min((min(abs(x[i])+abs(x[i+k-1]-x[i]),abs(x[i+k-1])+abs(x[i]-x[i+k-1]))) for i in range(n-k+1)))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = [int(val) - (i + 1) for i, val in zip(range(n), input().split())]

b = int(round(sum(A) / len(A)))
sad = 0
Sad = []
for j in range(min(A), max(A)+1):
  b_ = j
  for i in range(n):
    sad += abs(A[i] - b_)
  Sad.append(sad)
  sad = 0
print(min(Sad))

Fixed submission:
n = int(input())
A = sorted([int(val) - (i + 1) for i, val in zip(range(n), input().split())])

b = A[len(A)//2]
sad = 0
for i in range(n):
  sad += abs(A[i] - b)
print(sad)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
L6 = []
L9 = []
for i in range(1, 100):
  num = 6 ** i
  if num <= n:
    L6.append(num)
  else:
    break
for i in range(1, 100):
  num = 9 ** i
  if num <= n:
    L9.append(num)
  else:
    break

from itertools import product
iter6 = product(range(0, 6), repeat=len(L6))
Res6 = []
for iter in iter6:
  total = 0
  counter = 0
  for num, l in zip(iter, L6):
    total += num * l
    counter += num
  if n - total >= 0:
    Res6.append([n - total, counter])
#print(Res6)

iter9 = product(range(0, 9), repeat=len(L9))
Res9 = []
for iter in iter9:
  total = 0
  counter = 0
  for num, l in zip(iter, L9):
    total += num * l
    counter += num
  if n - total >= 0:
    Res9.append([total, counter])

#print(list(product(Res6, Res9)))
Res9.sort(key = lambda x:x[0])

min_x = n
for cand6 in Res6:
  for cand9 in Res9:
    if cand6[0] - cand9[0] >= 0:
      x = cand6[0] - cand9[0] + cand6[1] + cand9[1]
      min_x = min(min_x, x)
    else:
      break
print(min_x)


Fixed submission:
n = int(input())

L6 = []
for i in range(1, 100):
  if 6**i <= n:
    L6.append(6**i)
  else:
    break

L9 = []
for i in range(1, 100):
  if 9**i <= n:
    L9.append(9**i)
  else:
    break

dp = [0] * (n+1)
    
for i in range(1, n+1):
  dp[i] = dp[i-1] + 1
  for l6 in L6:
    if i - l6 >= 0:
      dp[i] = min(dp[i], dp[i - l6] + 1)
  for l9 in L9:
    if i - l9 >= 0:
      dp[i] = min(dp[i], dp[i - l9] + 1)
print(dp[n])

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
L6 = []
L9 = []
for i in range(1, 100):
  num = 6 ** i
  if num <= n:
    L6.append(num)
  else:
    break
for i in range(1, 100):
  num = 9 ** i
  if num <= n:
    L9.append(num)
  else:
    break

from itertools import product
iter6 = product(range(0, 6), repeat=len(L6))
Res6 = []
for iter in iter6:
  total = 0
  counter = 0
  for num, l in zip(iter, L6):
    total += num * l
    counter += num
  if n - total >= 0:
    Res6.append([n - total, counter])
#print(Res6)

iter9 = product(range(0, 9), repeat=len(L9))
Res9 = []
for iter in iter9:
  total = 0
  counter = 0
  for num, l in zip(iter, L9):
    total += num * l
    counter += num
  Res9.append([total, counter])

#print(list(product(Res6, Res9)))

min_x = n
for pairs in product(Res6, Res9):
  if pairs[0][0] - pairs[1][0] >= 0:
    x = pairs[0][0] - pairs[1][0] + pairs[0][1] + pairs[1][1]
    min_x = min(min_x, x)
print(min_x)


Fixed submission:
n = int(input())

L6 = []
for i in range(1, 100):
  if 6**i <= n:
    L6.append(6**i)
  else:
    break

L9 = []
for i in range(1, 100):
  if 9**i <= n:
    L9.append(9**i)
  else:
    break

dp = [0] * (n+1)
    
for i in range(1, n+1):
  dp[i] = dp[i-1] + 1
  for l6 in L6:
    if i - l6 >= 0:
      dp[i] = min(dp[i], dp[i - l6] + 1)
  for l9 in L9:
    if i - l9 >= 0:
      dp[i] = min(dp[i], dp[i - l9] + 1)
print(dp[n])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()

min_ = n
for i in range(n):
  temp = s[:i].count("W") + s[i+1:].count("E")
  min_ = min(temp, min_)
print(min_)

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

min_ = n
A = [0] * n
for i in range(n):
  if s[i] == "W":
    A[i] = A[i-1] + 1
  else:
    A[i] = A[i-1]

val = (n-1 - (A[-1] - A[0]))
min_ = min(min_, val)
for i in range(1, n):
  val = A[i-1] + (n-1 - i - (A[-1] - A[i]))
  min_ = min(val, min_)
print(min_)
Buggy python submission (verdict: Time Limit Exceeded):
S = list(input())
k = int(input())
S_sorted = "".join(sorted(list(set(S))))
#print(S_sorted[:5])
Ans = []
counter = 0
for counter in range(0, 10000000):
  Ans_temp = []
  moji = S_sorted[counter]
  Index = [i for i, chr in enumerate(S) if moji == chr]
  for index in Index:
    for j in range(0, len(S) + 1):
      if len(S[index : index+j]) != 0:
        Ans_temp.append("".join(S[index : index+j]))
#  print(Ans_temp)
  Ans = Ans + sorted(list(set(Ans_temp)))
  if len(Ans) >= k:
    break
print(Ans[k-1])

Fixed submission:
S = list(input())
k = int(input())
S_sorted = "".join(sorted(list(set(S))))
#print(S_sorted[:5])
Ans = []
counter = 0
for counter in range(0, 10000000):
  Ans_temp = []
  moji = S_sorted[counter]
  Index = [i for i, chr in enumerate(S) if moji == chr]
  for j in range(0, k + 1):
    for index in Index:
      if len(S[index : index+j]) != 0:
        Ans_temp.append("".join(S[index : index+j]))
#  print(Ans_temp)
  Ans = Ans + sorted(list(set(Ans_temp)))
  if len(Ans) >= k:
    break
print(Ans[k-1])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
L = list(map(int, input().split()))
sL = sorted(L)
for i in range(n):
  ind = sL.index(L[i])
  if ind < n // 2:
    print(sL[n//2])
  else:
    print(sL[n//2 - 1])

Fixed submission:
n = int(input())
L = list(map(int, input().split()))
sL = sorted(L)
for i in range(n):
  if L[i] <= sL[n // 2 - 1]:
    print(sL[n//2])
  else:
    print(sL[n//2 - 1])