Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N, A, B, C = list(map(int, input().split()))
L = [int(input()) for _ in range(N)]

from itertools import permutations


def min_cost(g_list):
    g1, g2, g3 = g_list
    return abs(g1 - A) + abs(g2 - B) + abs(g3 - C)


ans = []
for LL in permutations(L):
    for p1 in range(1, N - 1):
        for p2 in range(p1+1, N):
            for p3 in range(p2 + 1, N+1):
                g1, g2, g3 = sum(LL[:p1]), sum(LL[p1:p2]), sum(LL[p2:p3])
                syn = [len(
                    L[:p1])-1, len(L[p1:p2])-1, len(L[p2:p3])-1]
                # print(g1, g2, g3)
                # print(p1, p2, p3)
                # print(syn)
                ans.append(min_cost([g1, g2, g3]) + sum(syn) * 10)
    # break

print(min(ans))
# print(ans)


Fixed submission:
N, A, B, C = list(map(int, input().split()))
L = [int(input()) for _ in range(N)]

from itertools import permutations, combinations


def dellist(items, contents):
    items = items.copy()
    for rm in contents:
        # print(rm)
        items.remove(rm)
    return items


ans = []
L_temp = L.copy()

for n_g1 in range(1, N):
    for n_g2 in range(1, N - n_g1+1):
        for n_g3 in range(1, N - n_g1 - n_g2 + 1):
            # print(n_g1, n_g2, n_g3)
            L_temp = L.copy()
            for G1 in combinations(L_temp, n_g1):
                L_temp = L.copy()
                L_temp = dellist(L_temp, G1)
                # print('G1', L_temp)
                for G2 in combinations(L_temp, n_g2):
                    L_temp = L.copy()
                    L_temp = dellist(L_temp, G1)
                    L_temp = dellist(L_temp, G2)
                    # print('G2', L_temp)
                    for G3 in combinations(L_temp, n_g3):
                        # print('G3', L_temp)
                        s1, s2, s3 = sum(G1), sum(G2), sum(G3)
                        syn = len(G1) + len(G2) + len(G3) - 3
                        ans.append(abs(s1 - A) + abs(s2 - B) +
                                   abs(s3 - C) + syn * 10)

# print(ans)
print(min(ans))
Buggy python submission (verdict: Time Limit Exceeded):
# from sys import stdin #入力の高速化(0.2秒ぐらい早くなる)
A, B, Q = list(map(int, input().split()))
# もし神社(寺)が1つしかなかった場合に両端に仮想の神社を建築して処理の一貫性を保つ。かりにこれが選ばれても最大のコストなので最終的に最適になることはない。
INF = 10 ** 18

# S = [-INF] + list(map(int, (stdin.readline() for _ in [0] * A))) + [INF]
# T = [-INF] + list(map(int, [stdin.readline() for _ in [0] * B])) + [INF]
S = [-INF] + [int(input()) for _ in range(A)]+[INF]
T = [-INF] + [int(input()) for _ in range(B)]+[INF]

from bisect import bisect_right
# from bisect import bisect_left as bisect_right #これでも通ったりする。
from itertools import product

for q in range(Q):  # 各問に答える
    x = int(input())  # 位置の指定
    s_idx, t_idx = bisect_right(S, x), bisect_right(T, x)
    ans = INF
    # 左右の神社と寺のの組み合わせ
    for s, t in product(S[s_idx - 1:s_idx + 1], T[t_idx - 1:t_idx + 1]):
        t_root = abs(t - x) + abs(s - t)  # 寺から最初に回るルート
        s_root = abs(s - x) + abs(s - t)
        ans = min(ans, t_root, s_root)
    # 最小をとって終わり
    print(ans)

'''
bisect_right

ソートされた順序を保ったまま x を a に挿入できる点を探し当てます。リストの中から検索する部分集合を指定するには、パラメータの lo と hi を使います。デフォルトでは、リスト全体が使われます。x がすでに a に含まれている場合、挿入点は既存のどのエントリーよりも後(右)になります。戻り値は、list.insert() の第一引数として使うのに適しています。a はすでにソートされているものとします。


In[3]: A
Out[3]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

In[4]: bisect.bisect_right(A, 2.5)
Out[4]: 3

In[5]: bisect.bisect_right(A, 3)
Out[5]: 4
'''


Fixed submission:
A, B, Q = list(map(int, input().split()))
# もし神社(寺)が1つしかなかった場合に両端に仮想の神社を建築して処理の一貫性を保つ。かりにこれが選ばれても最大のコストなので最終的に最適になることはない。
INF = 10 ** 18

S = [-INF] + [int(input()) for _ in range(A)]+[INF]
T = [-INF] + [int(input()) for _ in range(B)]+[INF]

from bisect import bisect_right
from itertools import product


for q in range(Q):  # 各問に答える
    x = int(input())  # 位置の指定
    s_idx, t_idx = bisect_right(S, x), bisect_right(T, x)
    ans = INF
    # 左右の神社と寺のの組み合わせ
    for s, t in product(S[s_idx - 1:s_idx + 1], T[t_idx - 1:t_idx + 1]):
        t_root = abs(t - x) + abs(s - t)  # 寺から最初に回るルート
        s_root = abs(s - x) + abs(s - t)
        ans = min(ans, t_root, s_root)
    # 最小をとって終わり
    print(ans)

'''
bisect_right

ソートされた順序を保ったまま x を a に挿入できる点を探し当てます。リストの中から検索する部分集合を指定するには、パラメータの lo と hi を使います。デフォルトでは、リスト全体が使われます。x がすでに a に含まれている場合、挿入点は既存のどのエントリーよりも後(右)になります。戻り値は、list.insert() の第一引数として使うのに適しています。a はすでにソートされているものとします。


In[3]: A
Out[3]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

In[4]: bisect.bisect_right(A, 2.5)
Out[4]: 3

In[5]: bisect.bisect_right(A, 3)
Out[5]: 4
'''
Buggy python submission (verdict: Runtime Error):
N = int(input())
idx_to_AB = {}
for i in range(N):
    idx_to_AB[i] = list(map(int, input().split()))

A_to_idx = {value[0]: key for key, value in idx_to_AB.items()}
B_to_idx = {value[1]: key for key, value in idx_to_AB.items()}

A = sorted(A_to_idx, reverse=True)
B = sorted(B_to_idx, reverse=True)

cntA, cntB = 0, 0
while (len(idx_to_AB)):
    # 先行

    if A[0] > B[0]:
        cntA += A[0]
        B.remove(idx_to_AB[A_to_idx[A[0]]][1])
        del idx_to_AB[A_to_idx[A[0]]]
        A = A[1:]

    else:
        cntA += idx_to_AB[B_to_idx[B[0]]][0]
        A.remove(idx_to_AB[B_to_idx[B[0]]][0])
        del idx_to_AB[B_to_idx[B[0]]]
        B = B[1:]
    # print(idx_to_AB)
    # print(A, B)

    if len(idx_to_AB) == 0:
        break
    # 後攻
    if A[0] < B[0]:
        cntB += B[0]
        A.remove(idx_to_AB[B_to_idx[B[0]]][0])
        del idx_to_AB[B_to_idx[B[0]]]
        B = B[1:]
    else:
        cntB += idx_to_AB[A_to_idx[A[0]]][1]
        B.remove(idx_to_AB[A_to_idx[A[0]]][1])
        del idx_to_AB[A_to_idx[A[0]]]
        A = A[1:]

print(cntA-cntB)


Fixed submission:
N = int(input())
# 仮に青木さん(B)が全て食べたとき、高橋(A)にとっては最悪な状況
# これを打破するためには、自分の得点と相手の得るはずだった得点の和を最大にするようなものについて食べれば良い
# 青木さんも同じことを考えるので、要は幸福度の和をソートして交互に食べていけば、互いに最善の行動を取ることとなる。
# 答えを出す際には、AがBから何点奪ったかだけを考えればよい。
# つまり、Aが最善で何点奪えるか　から　全てBさんが食べたとき　を引けばいい

sum_happiness = []
all_for_B = 0

for i in range(N):
    tmp1, tmp2 = list(map(int, input().split()))
    sum_happiness.append(tmp1 + tmp2)
    all_for_B += tmp2

sum_happiness.sort(reverse=True)


gain_A = 0
for i, h in enumerate(sum_happiness):
    if i % 2 == 0:
        gain_A += h
    # print(gain_A)


print(gain_A - all_for_B)
Buggy python submission (verdict: Runtime Error):
A=map(int,input().split())
A.sort()
print(A[0]*A[1]//2)



Fixed submission:
A=list(map(int,input().split()))
A.sort()
print(A[0]*A[1]//2)

Buggy python submission (verdict: Runtime Error):
A=map(int,input().split())
A.sort()
print(A[1]*A[2]//2)



Fixed submission:
A=list(map(int,input().split()))
A.sort()
print(A[0]*A[1]//2)
Buggy python submission (verdict: Runtime Error):
S = input()

keyword = 'keyence'
cnt = 0
for moji in S:
    if moji == keyword[0]:
        cnt += 1
        keyword = keyword[1:]

if cnt == 7:
    print('YES')
else:
    print('NO')


Fixed submission:
S = input()

keyword = 'keyence'
if (S[:7] == keyword) or (S[-7:] == keyword):
    print('YES')
    exit()

f, b = 0, 0
# forward
for i, (key, s) in enumerate(zip(keyword, S)):
    if key != s:
        f = i
        break
    else:
        # keyword = keyword[1:]
        pass
# print(keyword)
# backward
for i, (key, s) in enumerate(zip(keyword[::-1], S[::-1])):
    # print(key, s)
    if key != s:
        b = i
        break
    else:
        keyword = keyword[1:]

# print(f, b)
if f + b > 6:
    print('YES')
else:
    print("NO")
Buggy python submission (verdict: Time Limit Exceeded):
# DAGの最長経路...トポロジカルソートもどきか？
# 普通にDAGに沿ったdpをすればいいのでは?
# 再帰だと実装楽そうだけどどうしよう
# 問題は終了と最初がわからんこと
# いや最初は全部長さ0をセットすればいいだろ
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce

N, M = ints()
dag = defaultdict(lambda: [])
indeg = [0] * N
for _ in ra(M):
    x, y = mina(*ints())
    indeg[y] += 1
    dag[x].append(y)

q = deque()
for u, inn in enu(indeg):  # 多点DFS初期化
    if inn == 0:
        q.append(u)  # 別にlengthの情報をもたせちゃってもいいんだけどね

dp = [0] * N
while q:  # トポロジカル順序でdpテーブルを埋めていく
    u = q.popleft()
    for nx in dag[u]:
        dp[nx] = max(dp[nx], dp[u] + 1)
        # indeg[nx] -= 1
        # if indeg[nx] == 0:
        q.append(nx)
print(max(dp))


Fixed submission:
# DAGの最長経路...トポロジカルソートもどきか？
# 普通にDAGに沿ったdpをすればいいのでは?
# 再帰だと実装楽そうだけどどうしよう
# 問題は終了と最初がわからんこと
# いや最初は全部長さ0をセットすればいいだろ
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce

N, M = ints()
dag = defaultdict(lambda: [])
indeg = [0] * N
for _ in ra(M):
    x, y = mina(*ints())
    indeg[y] += 1
    dag[x].append(y)

q = deque()
for u, inn in enu(indeg):  # 多点DFS初期化
    if inn == 0:
        q.append(u)

dp = [0] * N
while q:  # トポロジカル順序でdpテーブルを埋めていく
    u = q.popleft()
    # dp[u] = max(dp[u], l)
    for nx in dag[u]:
        dp[nx] = max(dp[nx], dp[u] + 1)
        indeg[nx] -= 1
        if indeg[nx] == 0:
            q.append(nx)
print(max(dp))
Buggy python submission (verdict: Runtime Error):
# https://atcoder.jp/contests/dp/tasks/dp_l

'''
dp[i,j] ... dequeに[i,j]が残っているときに行動するプレイヤーのスコアの最大
dp[i,j] = max(a[i-1]-dp[i-1,j], a[j+1]-dp[i,j+1]) #これじゃgreedyと同じじゃん

dp[i,j] ... dequeに[i,j)が残っているときにその状態からスタートするプレイヤーが達成できるスコアの最大 (区間を伸ばしていく感じ)

初期値 dp[i,i]==0

dp[i,j]=max(a[i]-dp[i+1,j], a[j-1]-dp[i,j-1])
'''
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)


def a_int(): return int(readline())


def ints(): return np.fromstring(readline(), sep=' ', dtype=np.int64)


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import

N = a_int()
A = ints()


from numba import njit


@njit('(i8,i8[:])', cache=True)
def solve(N, A, dp):
    dp = np.zeros((N + 1, N + 1), dtype=np.int64)
    for i in range(N - 1, -1, -1):
        for j in range(i + 1, N + 1):
            dp[i, j] = max(A[i] - dp[i + 1, j], A[j - 1] - dp[i, j - 1])
    print(dp[0, N])
    # print(*dp, sep='\n')


solve(N, A)


Fixed submission:
# https://atcoder.jp/contests/dp/tasks/dp_l

'''
dp[i,j] ... dequeに[i,j]が残っているときに行動するプレイヤーのスコアの最大
dp[i,j] = max(a[i-1]-dp[i-1,j], a[j+1]-dp[i,j+1]) #これじゃgreedyと同じじゃん

dp[i,j] ... dequeに[i,j)が残っているときにその状態からスタートするプレイヤーが達成できるスコアの最大 (区間を伸ばしていく感じ)

初期値 dp[i,i]==0

dp[i,j]=max(a[i]-dp[i+1,j], a[j-1]-dp[i,j-1])
'''
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)


def a_int(): return int(readline())


def ints(): return np.fromstring(readline(), sep=' ', dtype=np.int64)


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import

N = a_int()
A = ints()

dp = full((N + 1, N + 1), -10**11)
dp[np.arange(N + 1), np.arange(N + 1)] = 0

from numba import njit


@njit('(i8,i8[:],i8[:,:])', cache=True)
def solve(N, A, dp):
    for i in range(N - 1, -1, -1):
        for j in range(i + 1, N + 1):
            dp[i, j] = max(A[i] - dp[i + 1, j], A[j - 1] - dp[i, j - 1])
    print(dp[0, N])
    # print(*dp, sep='\n')


solve(N, A, dp)
Buggy python submission (verdict: Runtime Error):
S=input()
ans=1000
for i in range(len(S)-3):
  ans=min(ans,abs(753-int(S[i]+S[i+1]+S[i+2]))
print(ans)


Fixed submission:
S=input()
ans=1000
for i in range(len(S)-2):
    ans=min(ans,abs(753-int(S[i:i+3])))

print(ans)

Buggy python submission (verdict: Runtime Error):
S=input()
ans=1000
for i in range(len(S)):
  if i+3>=len(S):
    break
  ans=min(ans,abs(753-int(S[i:i+3]))
print(ans)


Fixed submission:
S=input()
ans=1000
for i in range(len(S)-2):
    ans=min(ans,abs(753-int(S[i:i+3])))

print(ans)

Buggy python submission (verdict: Runtime Error):
S=input()
ans=1000
for i in range(len(S)-3):
  ans=min(ans,abs(753-int(S[i:i+3]))
print(ans)


Fixed submission:
S=input()
ans=1000
for i in range(len(S)-2):
    ans=min(ans,abs(753-int(S[i:i+3])))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# def to_2(num):
#     ret = []
#     while (num != 0):
#         if num % 2 == 1:
#             ret.append(True)
#         else:
#             ret.append(False)
#         num = num // 2
#     return np.array(ret)

# def()

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

# 全探索
from itertools import combinations
A_2 = [bin(a) for a in A]

kouho = [sum(A[idx:(idx2+1)]) for idx, idx2 in combinations(range(0, N), 2)]


ma = 0
for A_sub in combinations(kouho, K):
    bina = A_sub[0]
    # print(bina)
    for i in range(1, K):
        bina = bina & A_sub[i]
    if bina > ma:
        ma = bina

print(ma)

Fixed submission:
# https://atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_b
# 解説見てしまった
# N≤1000の性質をうまく使う必要はない。O(N^2)で全部書き出せばいい。完全に引っ掛け。
# 答えの仮定、bitごとに見る、上位桁からのgreedyらへんがキーワード

from itertools import combinations
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = [sum(A[s:t]) for s, t in combinations(range(N + 1), 2)]

l = max(B).bit_length()  # 何桁扱えば十分か？
x = 0  # 初期値
for i in range(l, -1, -1):  # 上位桁からgreedyに決定
    # 候補のうち i bit目=1がK個以上あれば答えに計上できる
    x_tmp = x + (1 << i)
    if sum((x_tmp & b) == x_tmp for b in B) >= K:  # 確定した桁+i桁を1としたときに答えになり得るか？
        x = x_tmp
print(x)
Buggy python submission (verdict: Runtime Error):
N,T=map(int,input().split())
ans=100000
for _ in range(N):
  c,t=map(int,input().split())
  if t<=T:
    ans=min(ans,c)
print('TLE' if ans=100000 else ans)

Fixed submission:
N,T=map(int,input().split())
ans=100000
for _ in range(N):
  c,t=map(int,input().split())
  if t<=T:
    ans=min(ans,c)
print('TLE' if ans==100000 else ans)
Buggy python submission (verdict: Runtime Error):
# https://atcoder.jp/contests/abc112/tasks/abc112_d

# 答えansの満たす条件
# ans<=M//Nである
# M%ans==0である


# 仮説:M//Nからansを--して、M%ans==0となるansが答え
# でももしN=2, M=10*9+7とかだったらTLEしそう →約数ならば

from math import sqrt

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

ans = M // N
if M % N == 0:
    print(ans)
    exit()

s = min(ans, sqrt(M) + 1)
for a in range(s, 0, -1):
    if M % a == 0:
        print(a)
        exit()


Fixed submission:
# https://atcoder.jp/contests/abc112/tasks/abc112_d

# 答えansの満たす条件
# ans<=M//Nである
# M%ans==0である


# 仮説:M//Nからansを--して、M%ans==0となるansが答え
# でももしN=2, M=10*9+7とかだったらTLE思想

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

ans = M // N
for a in range(ans, 0, -1):
    if M % a == 0:
        print(a)
        exit()
Buggy python submission (verdict: Runtime Error):
# https://atcoder.jp/contests/abc107/tasks/arc101_a

# 累積和を使って区間ごとの時間を求めて、更にスタートからの時間を足す
# 考える区間は0から左にK個〜右K個までK個ずつずらす

import sys
from bisect import bisect_left
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


N, K = read_ints()
X = read_ints()

zeroidx = bisect_left(X, 0)
if X[zeroidx] == 0:
    K -= 1


# すべて正の場合
if X[0] >= 0:
    print(X[K - 1])
    exit()
# 負の場合
if X[-1] <= 0:
    print(X[-K])
    exit()


l = max(zeroidx - K, 0)
# r_max = min(zeroidx + K, len(X) - 1)

ans = 10**16

for i in range(K):
    ll = l + i
    if ll + K - 1 >= len(X):
        break
    # print(X[ll:ll + K])
    ans = min(ans, 2 * abs(X[ll]) + abs(X[ll + K - 1]),
              abs(X[ll]) + 2 * abs(X[ll + K - 1]))


print(ans)


Fixed submission:
# https://atcoder.jp/contests/abc107/tasks/arc101_a

# 累積和を使って区間ごとの時間を求めて、更にスタートからの時間を足す
# 考える区間は0から左にK個〜右K個までK個ずつずらす

import sys
from bisect import bisect_left
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


N, K = read_ints()
X = read_ints()


# すべて正の場合
if X[0] >= 0:
    print(X[K - 1])
    exit()
# 負の場合
if X[-1] <= 0:
    print(abs(X[-K]))
    exit()


zeroidx = bisect_left(X, 0)
if X[zeroidx] == 0:
    K -= 1

l = max(zeroidx - K, 0)
# r_max = min(zeroidx + K, len(X) - 1)

ans = 10**16

for i in range(K):
    ll = l + i
    rr = ll + K - 1
    if rr >= len(X):
        break
    # print(X[ll:ll + K])
    ans = min(ans, 2 * abs(X[ll]) + abs(X[rr]),
              abs(X[ll]) + 2 * abs(X[rr]))


print(ans)
Buggy python submission (verdict: Runtime Error):
# https://atcoder.jp/contests/abc105/tasks/abc105_c
# -2進数
# 前に考えたときはわからなかったけど、数式イジイジしたら解けた


N = int(input())

if N == 0:
    print(0)
	exit()
ans = ''
while N != 0:
    if N & 1:  # 奇数ならbitが立つのは共通する性質
        ans += '1'
        N /= -2
        if N > 0:
            N += 1
        N = int(N)
    else:
        ans += '0'
        N //= -2


print(ans[::-1])


Fixed submission:
# https://atcoder.jp/contests/abc105/tasks/abc105_c
# -2進数
# 前に考えたときはわからなかったけど、数式イジイジしたら解けた


N = int(input())

if N == 0:
    print(0)
    exit()

ans = ''
while N != 0:
    if N & 1:  # 奇数ならbitが立つのは共通する性質
        ans += '1'
        N /= -2
        if N > 0:
            N += 1
        N = int(N)
    else:
        ans += '0'
        N //= -2


print(ans[::-1])
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from math import gcd

# https://atcoder.jp/contests/abc100/tasks/abc100_d
# 定式化 M個のidxの集合idsに対して、
# max(|sum_ids (x_i)| +|sum_ids (y_i)| + |sum_ids (z_i)|) という問題
# 各項について正負を仮定すると、どのケーキを取ればいいのか優先度が決まる(ソート)
# bit全探索とソートの合わせ技
N, M = read_ints()
XYZ = read_tuple(N)

ans = -1 * 10**13 - 100
for is_mina_x, is_mina_y, is_mina_z in product(range(2), repeat=3):
    is_mina_x = -1 if is_mina_x else 1
    is_mina_y = -1 if is_mina_y else 1
    is_mina_z = -1 if is_mina_z else 1

    XYZ.sort(key=lambda x: is_mina_x *
             x[0] + is_mina_y * x[1] + is_mina_z * x[2], reverse=True)
    x_sum = 0
    y_sum = 0
    z_sum = 0
    for x, y, z in XYZ[:M]:
        x_sum += x
        y_sum += y
        z_sum += z
    ans = max(ans, abs(x_sum) + abs(y_sum) + abs(z_sum))

print(ans)


Fixed submission:
# https://atcoder.jp/contests/abc100/tasks/abc100_d

# もし正の数だけだったら簡単→それぞれの合計値でソートすれば良い
# Nはたかだか1000→N^2でも間に合う

# 突っ込んだときに良くなるものを貪欲に選べばよいのでは？
# だめだ。-3 1 1 1 1とかのときに1が選ばれなくなる
# 正負の仮定を8パターン列挙しておいて、それぞれに貪欲にやる←行けそう

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


N, M = read_ints()
XYZ = read_tuple(N)


def iter_p_adic(p, length):
    '''
    連続して増加するp進数をリストとして返す。lengthはリストの長さ
    return
    ----------
    所望のp進数リストを次々返してくれるiterator
    '''
    from itertools import product
    tmp = [range(p)] * length
    return product(*tmp)


def sort_and_ret_score(p):
    a = [-1, 1]
    XYZ.sort(reverse=True, key=lambda x: (
        a[p[0]] * x[0] + a[p[1]] * x[1] + a[p[2]] * x[2]))  # すべて正だとして仮定した場合の最大値
    tmp = 0
    for x, y, z in XYZ[:M]:
        tmp += a[p[0]] * x + a[p[1]] * y + a[p[2]] * z
    return tmp


ans = 0
for p in iter_p_adic(2, 3):
    ans = max(ans, sort_and_ret_score(p))


print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc097/tasks/arc097_a
# まずは愚直に実装してみる

S = input()
K = int(input())
candi = []
for s in range(len(S)):
    for e in range(s + 1, len(S) + 1):
        candi.append(S[s:e])
candi = list(set(candi))
candi.sort()
print(candi[K - 1])


Fixed submission:
# https://atcoder.jp/contests/abc097/tasks/arc097_a


# 辞書順に置いては文字の先頭が重要。
# 一文字目が速いやつから注目していく。
# 一文字目が同じだったらさらにその次の文字を注目する。

# atcoderandatcodeer
# a      a  a       # 1種
# at     an at      # 1種 #tは以下のすべてよりも辞書順があと
#        and        # 1種
#        anda       # 1種
#        andat      #

S = input()
K = int(input())

# 一番速い文字を検索してからそこからK文字見るのが一番早そう。
# ただし、K文字ない場合は辻褄合わせが必要
# てか計算量的に、こんなことしなくてもK文字目まで全列挙すればよくね？

# mi = min(S)
candi = []
for s in range(len(S)):
    for add in range(1, K + 1):
        candi.append(S[s:s + add])

candi = list(set(candi))
candi.sort()
print(candi[K - 1])

Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc097/tasks/arc097_a
# まずは愚直に実装してみる

S = input()
K = int(input())
candi = []
for s in range(len(S)):
    for e in range(s + 1, len(S) + 1):
        candi.append(S[s:e])
candi = list(set(candi))
candi.sort()
print(candi[K - 1])


Fixed submission:
# https://atcoder.jp/contests/abc097/tasks/arc097_a


# 辞書順に置いては文字の先頭が重要。
# 一文字目が速いやつから注目していく。
# 一文字目が同じだったらさらにその次の文字を注目する。

# atcoderandatcodeer
# a      a  a       # 1種
# at     an at      # 1種 #tは以下のすべてよりも辞書順があと
#        and        # 1種
#        anda       # 1種
#        andat      #

S = input()
K = int(input())

# 一番速い文字を検索してからそこからK文字見るのが一番早そう。
# ただし、K文字ない場合は辻褄合わせが必要
# てか計算量的に、こんなことしなくてもK文字目まで全列挙すればよくね？

# mi = min(S)
candi = []
for s in range(len(S)):
    for add in range(1, K + 1):
        candi.append(S[s:s + add])

candi = list(set(candi))
candi.sort()
print(candi[K - 1])