Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
# input = sys.stdin.readline
inf = 10 ** 18

N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]

ans = inf
for i in range(N - 1):
    xi, yi = xy[i]
    for j in range(i + 1, N):
        xj, yj = xy[j]
        #
        p = xj - xi
        q = yj - yi
        terms = set([])
        for n, (xn, yn) in enumerate(xy):
            mp = q * xn -  p * yn
            mod = xn % p if p > 0 else yn % q
            terms.add((mp, mod))
        # print("#", p, q, terms)
        ans_tmp = len(terms)
        #
        if ans > ans_tmp: ans = ans_tmp

print(ans)


Fixed submission:
import sys
# input = sys.stdin.readline
inf = 10 ** 18

N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]

x = [xi for xi, yi in xy]
y = [yi for xi, yi in xy]

ans = inf
for i in range(N - 1):
    xi, yi = xy[i]
    for j in range(i + 1, N):
        xj, yj = xy[j]
        #
        p = xj - xi
        q = yj - yi
        #
        ans_tmp = 0
        for n, (xn, yn) in enumerate(xy):
            xm = xn - p
            ym = yn - q
            # print("##", (xm, ym))
            if [xm, ym] not in xy: ans_tmp += 1
        #
        # print("#", xy, ans_tmp)
        if ans > ans_tmp: ans = ans_tmp

if N == 1:
    print(1)
else:
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]


tab_h = [[0] * W for _ in range(H)]
tab_v = [[0] * W for _ in range(H)]

for i in range(H):
    memo = [0] * W
    tmp = 0
    for j in range(W):
        if S[i][j] == '.':
            tmp += 1
        else:
            tmp = 0
        memo[j] = tmp
    tmp = 0
    for j in range(W):
        if tmp == 0 and memo[W - 1 - j] > 0:
            tmp = memo[W - 1 - j]
        elif memo[W - 1 - j] == 0:
            tmp = 0
        tab_h[i][W - 1 - j] = tmp

for j in range(W):
    memo = [0] * H
    tmp = 0
    for i in range(H):
        if S[i][j] == '.':
            tmp += 1
        else:
            tmp = 0
        memo[i] = tmp
    tmp = 0
    for i in range(H):
        if tmp == 0 and memo[H - 1 - i] > 0:
            tmp = memo[H - 1 - i]
        elif memo[H - 1 - i] == 0:
            tmp = 0
        tab_v[H - 1 - i][j] = tmp

# for i in range(H): print("#", tab_h[i])
# for i in range(H): print("#", tab_v[i])

ans = 1
for i in range(H):
    for j in range(W):
        ans_tmp = tab_h[i][j] + tab_v[i][j] - 1
        if ans < ans_tmp:
            ans = ans_tmp

print(ans)

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


tab_h = [[0] * W for _ in range(H)]
tab_v = [[0] * W for _ in range(H)]

for i in range(H):
    memo = [0] * W
    tmp = 0
    for j in range(W):
        if S[i][j] == '.':
            tmp += 1
        else:
            tmp = 0
        memo[j] = tmp
    tmp = 0
    for j in range(W):
        if tmp == 0 and memo[W - 1 - j] > 0:
            tmp = memo[W - 1 - j]
        elif memo[W - 1 - j] == 0:
            tmp = 0
        tab_h[i][W - 1 - j] = tmp

for j in range(W):
    memo = [0] * H
    tmp = 0
    for i in range(H):
        if S[i][j] == '.':
            tmp += 1
        else:
            tmp = 0
        memo[i] = tmp
    tmp = 0
    for i in range(H):
        if tmp == 0 and memo[H - 1 - i] > 0:
            tmp = memo[H - 1 - i]
        elif memo[H - 1 - i] == 0:
            tmp = 0
        tab_v[H - 1 - i][j] = tmp

# for i in range(H): print("#", tab_h[i])
# for i in range(H): print("#", tab_v[i])

ans = 1
for i in range(H):
    for j in range(W):
        ans_tmp = tab_h[i][j] + tab_v[i][j] - 1
        if ans < ans_tmp:
            ans = ans_tmp

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = list(input())
N = len(s)

s_tmp = list(s)
ans = 0
for i in range(N - 2):
    if s_tmp[i] == 'A' and s_tmp[i + 1] == 'B' and s_tmp[i + 2] == 'C':
        for i_back in range(i):
            if s_tmp[i - 1 - i_back] == 'A':
                continue
            else:
                break
        else:
            i_back = i
        #
        for j in range(i - i_back, i + 3):
            if j == i - i_back:
                s_tmp[j] = 'B'
            elif j == i - i_back + 1:
                s_tmp[j] = 'C'
            else:
                s_tmp[j] = 'A'
        #
        ans += (i_back + 1)

print(ans)


Fixed submission:
s = input()

s = s.replace('BC', 'X')
# print("#", s)

seqs = []
seq = ''
for si in s:
    if si in ('A', 'X'):
        seq += si
    else:
        seqs.append(seq)
        seq = ''
else:
    if len(seq) > 0:
        seqs.append(seq)
        seq = ''
        
ans = 0
for seq in seqs:
    Ni = len(seq)
    cnttab = [None] * Ni
    cnt = seq.count('X')
    for i, ci in enumerate(seq):
        if ci == 'X':
            cnt -= 1
        cnttab[i] = cnt
    # print("##", seq, cnttab)
    #
    for i, ci in enumerate(seq):
        if ci == 'A':
            ans += cnttab[i]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]

pool = []

for Ai in A:
    pool.append(Ai)

for Bi, Ci in BC:
    for _ in range(Bi):
        pool.append(Ci)

pool.sort(key=lambda x: -x)

print(sum(pool[:N]))

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


table = {}
for Ai in A:
    table[str(Ai)] = 0
for Bi, Ci in BC:
    table[str(Ci)] = 0
    
for Ai in A:
    table[str(Ai)] += 1

for Bi, Ci in BC:
    table[str(Ci)] += Bi

table2 = [(int(key), value) for key, value in table.items()]
table2.sort(key=lambda x: -x[0])

ans = ans_cnt = 0
for key, value in table2:
    # print("#", key, value, ans_cnt, ans)
    if ans_cnt + value >= N:
        ans += key * (N - ans_cnt)
        break
    else:
        ans_cnt += value
        ans += key * value

print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
# input = sys.stdin.readline
inf = 10 ** 18

N, M = map(int, input().split())
XYZ = [list(map(int, input().split())) for _ in range(M)]

grp = [0] * N
moushiokuri = []
idx = 1
for i, (Xi, Yi, Zi) in enumerate(XYZ):
    if grp[Xi - 1] == grp[Yi - 1] == 0:
        grp[Xi - 1] = grp[Yi - 1] = idx
        idx += 1
    elif grp[Xi - 1] == 0:
        grp[Xi - 1] = grp[Yi - i]
    elif grp[Yi - 1] == 0:
        grp[Yi - 1] = grp[Xi - 1]
    else:
        moushiokuri.append((grp[Xi - 1], grp[Yi - 1]))

for src, dst in moushiokuri:
    for i, grpi in enumerate(grp):
        if grpi == src:
            grp[i] = dst

# print("#", grp)

ans = len(set(grp))
if 0 in grp:
    ans -= 1
    ans += grp.count(0)

print(ans)

Fixed submission:
import sys
# input = sys.stdin.readline
inf = 10 ** 18

N, M = map(int, input().split())
XYZ = [list(map(int, input().split())) for _ in range(M)]

# https://qiita.com/maron8676/items/6010128f4ef5c268f719
class UFnode(object):
    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.rank_ = 1

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()
        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                unite_root.parent_ = root
                root.rank_ = max(root.rank_, unite_root.rank_ + 1)
            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)

nodes = [UFnode(i) for i in range(N)]

for i, (Xi, Yi, Zi) in enumerate(XYZ):
    nodes[Xi - 1].unite(nodes[Yi - 1])

print(len(set([nodes[i].find() for i in range(N)])))
Buggy python submission (verdict: Runtime Error):
import sys
# input = sys.stdin.readline
inf = 10 ** 18

M, K = map(int, input().split())

tmp = 0
notK = []
for i in range(1 << M):
    if i == K: continue
    tmp ^= i
    notK.append(i)
if K == 0:
    ans = []
    for i in range((1 << M)):
        ans.append(i)
    for i in range((1 << M)):
        ans.append((1 << M) - 1 - i)
    #
    for i, ansi in enumerate(ans):
        if i > 0: print(' ', end='')
        print(ansi, end='')
    print()
elif tmp != K:
    print(-1)
else:
    ans = []
    ans.append(notK[0])
    ans.append(K)
    ans.append(notK[0])
    for i in range(1, (1 << M)):
        ans.append(notK[i])
        ans.append(K)
    for i in range(1, (1 << M)):
        ans.append(notK[(1 << M) - i])
    #
    for i, ansi in enumerate(ans):
        if i > 0: print(' ', end='')
        print(ansi, end='')
    print()

Fixed submission:
import sys
# input = sys.stdin.readline
inf = 10 ** 18

M, K = map(int, input().split())

tmp = 0
notK = []
for i in range(1 << M):
    if i == K: continue
    tmp ^= i
    notK.append(i)
if K == 0:
    ans = []
    for i in range((1 << M)):
        ans.append(i)
    for i in range((1 << M)):
        ans.append((1 << M) - 1 - i)
    #
    for i, ansi in enumerate(ans):
        if i > 0: print(' ', end='')
        print(ansi, end='')
    print()
elif tmp != K:
    print(-1)
else:
    ans = []
    ans.append(notK[0])
    ans.append(K)
    ans.append(notK[0])
    for i in range(1, (1 << M) - 1):
        ans.append(notK[i])
    ans.append(K)
    for i in range(1, (1 << M) - 1):
        ans.append(notK[(1 << M) - 1 - i])
    #
    for i, ansi in enumerate(ans):
        if i > 0: print(' ', end='')
        print(ansi, end='')
    print()
Buggy python submission (verdict: Time Limit Exceeded):
# encoding: utf-8
import sys
# input = sys.stdin.readline
inf = 10 ** 18

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

from collections import deque

field = [[None] * W for _ in range(H)]
q = deque([])
cnt = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            field[i][j] = 0
            q.append((i, j, 0))
            cnt += 1

tblr = ((-1, 0), (1, 0), (0, -1), (0, 1))
while cnt < H * W:
    y, x, d = q.popleft()
    for dy, dx in tblr:
        if y + dy < 0: continue
        if x + dx < 0: continue
        if y + dy >= H: continue
        if x + dx >= W: continue
        if field[y + dy][x + dx] != None: continue
        #
        field[y + dy][x + dx] = d + 1
        q.append((y + dy, x + dx, d + 1))
        cnt += 1

print(max([max(field[i]) for i in range(H)]))


Fixed submission:
# encoding: utf-8
import sys
# input = sys.stdin.readline
inf = 10 ** 18

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

from collections import deque

field = [[None] * W for _ in range(H)]
q = deque([])
cnt = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            field[i][j] = 0
            q.append((i, j, 0))
            cnt += 1

tblr = ((-1, 0), (1, 0), (0, -1), (0, 1))
while cnt < H * W:
    y, x, d = q.popleft()
    for dy, dx in tblr:
        if y + dy < 0: continue
        if x + dx < 0: continue
        if y + dy >= H: continue
        if x + dx >= W: continue
        if field[y + dy][x + dx] != None: continue
        #
        field[y + dy][x + dx] = d + 1
        q.append((y + dy, x + dx, d + 1))
        cnt += 1

print(max([max(field[i]) for i in range(H)]))
Buggy python submission (verdict: Time Limit Exceeded):
# encoding: utf-8
import sys
from collections import deque
input = sys.stdin.readline

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

q = deque([(b, [])])
while len(q) > 0:
    b, seq = q.pop()
    if len(b) == 0: break
    for i, bi in enumerate(b):
        if i + 1 == bi:
            if i == 0: q.append((b[i + 1:], seq + [i + 1]))
            elif i == len(b) - 1: q.append((b[:i], seq + [i + 1]))
            else: q.append((b[:i] + b[i + 1:], seq + [i + 1]))
else:
    seq = [-1]

for i in seq[::-1]: print(i)

Fixed submission:
# encoding: utf-8
import sys
from collections import deque
input = sys.stdin.readline

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

for i, bi in enumerate(b):
    if i + 1 < bi:
        q = deque([])
        break
else:
    q = deque([(b, [])])
    
while len(q) > 0:
    b_tmp, seq = q.pop()
    if len(b_tmp) == 0: break
    for i, bi in enumerate(b_tmp):
        if i + 1 < bi: break
        elif i + 1 == bi:
            if i == 0: q.append((b_tmp[i + 1:], seq + [i + 1]))
            elif i == len(b_tmp) - 1: q.append((b_tmp[:i], seq + [i + 1]))
            else: q.append((b_tmp[:i] + b_tmp[i + 1:], seq + [i + 1]))
else:
    seq = [-1]

for i in seq[::-1]: print(i)
Buggy python submission (verdict: Time Limit Exceeded):
# encoding: utf-8
N, K = map(int, input().split())
h = list(map(int, input().split()))

def mysub(a, b): return a - b if a > b else b - a

import heapq

pq = []
d = [0] * N
prev = [None] * N

heapq.heappush(pq, (0, 0))
for i in range(1, N): d[i] = 10 ** 9 + 7

while len(pq) > 0:
    Qu, u = heapq.heappop(pq)
    if Qu > d[u]: continue
    for i in range(1, min(K + 1, N - u)):
        v = u + i
        cost = mysub(h[u], h[v])
        if Qu + cost < d[v]:
            d[v] = Qu + cost
            heapq.heappush(pq, (Qu + cost, v))
            prev[v] = u

print(d[-1])

Fixed submission:
# encoding: utf-8
N, K = map(int, input().split())
h = list(map(int, input().split()))
 
def mysub(a, b): return a - b if a > b else b - a
 
import heapq
 
pq = []
d = [0] * N
prev = [None] * N
 
heapq.heappush(pq, (0, 0))
for i in range(1, N): d[i] = 10 ** 9 + 7
 
while len(pq) > 0:
    Qu, u = heapq.heappop(pq)
    if Qu > d[u]: continue
    for i in range(1, min(K + 1, N - u)):
        v = u + i
        cost = mysub(h[u], h[v])
        if Qu + cost < d[v]:
            d[v] = Qu + cost
            heapq.heappush(pq, (Qu + cost, v))
            prev[v] = u
 
print(d[-1])

Buggy python submission (verdict: Time Limit Exceeded):
# encoding: utf-8
N, K = map(int, input().split())
h = list(map(int, input().split()))

def mysub(a, b): return a - b if a > b else b - a

import heapq

pq = []
d = [0] * N
prev = [None] * N

heapq.heappush(pq, (0, 0))
for i in range(1, N): d[i] = 10 ** 9 + 7

while len(pq) > 0:
    Qu, u = heapq.heappop(pq)
    for i in range(1, min(K + 1, N - u)):
        v = u + i
        cost = mysub(h[u], h[v])
        if d[u] + cost < d[v]:
            d[v] = d[u] + cost
            heapq.heappush(pq, (d[v], v))
            prev[v] = u

print(d[-1])

Fixed submission:
# encoding: utf-8
N, K = map(int, input().split())
h = list(map(int, input().split()))
 
def mysub(a, b): return a - b if a > b else b - a
 
import heapq
 
pq = []
d = [0] * N
prev = [None] * N
 
heapq.heappush(pq, (0, 0))
for i in range(1, N): d[i] = 10 ** 9 + 7
 
while len(pq) > 0:
    Qu, u = heapq.heappop(pq)
    if Qu > d[u]: continue
    for i in range(1, min(K + 1, N - u)):
        v = u + i
        cost = mysub(h[u], h[v])
        if Qu + cost < d[v]:
            d[v] = Qu + cost
            heapq.heappush(pq, (Qu + cost, v))
            prev[v] = u
 
print(d[-1])
Buggy python submission (verdict: Runtime Error):
# encoding: utf-8
import math
N, P = map(int, input().split())

ans = 1
P_tmp = P
for p in range(2, int(math.sqrt(P)) + 1):
    if P_tmp % (p ** N) == 0:
        for i_p in range(1, P):
            if P_tmp % (p ** (N * (i_p + 1))) > 0: break
        P_tmp = P_tmp // (p ** (N * i_p))
        ans = ans * (p ** i_p)
    if P_tmp < ((p + 1) ** N): break

print(ans)

Fixed submission:
# encoding: utf-8
N = int(input())
a = [int(input()) for i in range(N)]

ans = 2
for ai in a:
    if ai % 2:
        ans = 1
        break

if ans == 2: print('second')
else: print('first')
Buggy python submission (verdict: Time Limit Exceeded):
# encoding: utf-8
import math

N = int(input())
A = [int(input()) for i in range(N)]

A_up = sorted(A)
A_down = list(A_up[::-1])

rslt = []
idx_up = 0
idx_down = 0
for i in range(N):
    if i % 4 == 0:
        rslt = [A_up[idx_up]] + rslt
        idx_up += 1
    elif i % 4 == 1:
        rslt = rslt + [A_down[idx_down]]
        idx_down += 1
    elif i % 4 == 2:
        rslt = rslt + [A_up[idx_up]]
        idx_up += 1
    else:
        rslt = [A_down[idx_down]] + rslt
        idx_down += 1

# exception (N == 3, may be related with perfect graph ?)
if N == 3:
    if A_up[1] - A_up[0] > A_up[2] - A_up[1]:
        rslt = [A_up[1], A_up[0], A_up[2]]
    else:
        rslt = [A_up[1], A_up[2], A_up[0]]
        
ans = 0
prev = rslt[0]
for val in rslt[1:]:
    ans += (val - prev) if (val - prev) > 0 else (prev - val)
    prev = val

# print(rslt)
print(ans)

Fixed submission:
# encoding: utf-8
import math, sys

N = int(input())
A = [int(input()) for i in range(N)]

A_up = sorted(A)
A_down = list(A_up[::-1])

# magic-hand-like order
# 1 2 3
# |X X  4 <- this node is taken last
# 7 6 5

ans = 0
for i in range(N // 2):
    if i == 0:
        ans += (A_down[0] - A_up[0])
    else:
        ans += (A_down[i - 1] - A_up[i])
        ans += (A_down[i] - A_up[i - 1])

if N % 2:
    ans += max((A_down[N // 2 - 1] - A_down[N // 2], A_up[N // 2] - A_up[N // 2 - 1]))

print(ans)
Buggy python submission (verdict: Runtime Error):
# encoding: utf-8
N = int(input())
xyh = [list(map(int, input().split())) for i in range(N)]

ans = None
for cx in range(101):
    for cy in range(101):
        H_tmp = 0
        for xi, yi, hi in xyh:
            dx = xi - cx if xi >= cx else cx - xi
            dy = yi - cy if yi >= cy else cy - yi
            if H_tmp == 0 or H_tmp == hi + dx + dy: H_tmp = hi + dx + dy
            else: break
        else:
            ans = (cx, cy, H_tmp)
        if ans != None: break
    if ans != None: break

print(ans[0], ans[1], ans[2])


Fixed submission:
# encoding: utf-8
N = int(input())
xyh = [list(map(int, input().split())) for i in range(N)]

ans = None
for cx in range(101):
    for cy in range(101):
        H_tmp = -1
        # print("#", cx, cy)
        for xi, yi, hi in sorted(xyh, key=lambda x: -x[2]):
            # print("##", (xi, yi, hi), H_tmp)
            dx = (xi - cx) if xi >= cx else (cx - xi)
            dy = (yi - cy) if yi >= cy else (cy - yi)
            if H_tmp == -1: H_tmp = hi + dx + dy
            elif hi == 0:
                if dx + dy < H_tmp: break
                else: continue
            elif H_tmp == hi + dx + dy: H_tmp = hi + dx + dy
            else: break
        else:
            ans = (cx, cy, H_tmp)
        if ans != None: break
    if ans != None: break

print(ans[0], ans[1], ans[2])
Buggy python submission (verdict: Runtime Error):
# encoding: utf-8
# N = int(input())
# S = input()
# N, M = map(int, input().split())
# A = list(map(int, input().split()))

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

tab = [[None] * (x + 1) for i in range(N)]

def recsearch(i, x_tmp):
    # print("#", i, x_tmp)
    if i == N:
        if x_tmp > 0: return -1
        else: return 0
    elif tab[i][x_tmp] != None: ret = tab[i][x_tmp] # read
    elif x_tmp == 0: ret = 0
    elif x_tmp < A[i]: ret = recsearch(i + 1, x_tmp)
    else: ret = max((recsearch(i + 1, x_tmp - A[i]) + 1, recsearch(i + 1, x_tmp)))
    if tab[i][x_tmp] == None: tab[i][x_tmp] = ret # write
    return ret

print(max(0, recsearch(0, x)))

Fixed submission:
# encoding: utf-8
# N = int(input())
# S = input()
# N, M = map(int, input().split())
# A = list(map(int, input().split()))

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

x_tmp = x
for i, Ai in enumerate(sorted(A)):
    x_tmp -= Ai
    if x_tmp == 0:
        ans = i + 1
        break
    elif x_tmp < 0:
        ans = i
        break
    else: continue
else: ans = i

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# encoding: utf-8
N, X = map(int, input().split())
dx = list(map(lambda x: x - X, map(int, input().split())))

dx_nearest = 10**9
for dxi in dx:
    if (2 *(dxi > 0) - 1) * dxi < dx_nearest: dx_nearest = (2 *(dxi > 0) - 1) * dxi

for D in range(dx_nearest + 1)[::-1]:
    for dxi in dx:
        if dxi % D > 0: break
        else: continue
    else:
        print(D)
        break
else: print("oops")

Fixed submission:
# encoding: utf-8
import math

N, X = map(int, input().split())
x = sorted(list(map(int, input().split())) + [X])

def gcf2(a, b):
    if b == 0: return a
    else: return gcf2(b, (a % b))

# Greatest common factor
# print(x)
GCF = x[1] - x[0]
x_min = x[0]
for i, xi in enumerate(x):
    if i == 0: continue
    GCF = gcf2(GCF, (xi - x_min))

print(GCF)
Buggy python submission (verdict: Runtime Error):
# encoding: utf-8
L = int(input())

for base in range(2, 60):
    # encode
    for l_max in range(L):
        if base ** l_max > L: break
    bits = [None] * l_max
    L_temp = L
    for l in range(l_max):
        bits[l] = L_temp % base
        L_temp = L_temp // base
    # calculate N and M
    N = 2
    M = 0
    for l, bit in enumerate(bits):
        N += max((0, (bit > 0) * (l - 1)))
        M += (bit > 0) * max((1, base * l))
    if 2 < N <= 20 and 2 <= M <= 60: break
    else: continue
else:
    print("oops")
    
print(N, M)

offset = 0
idx = 2
for l, bit in enumerate(bits):
    if bit == 0: continue
    elif l == 0:
        print(1, N, 0)
        offset += 1
        continue
    # if l > 0
    nodes = [1] + [idx + i for i in range(l - 1)]
    # w/o offset
    for i in range(base * (l - 1)):
        edge = i % base
        if i % base == 0:
            cnct = i // base
            print(nodes[cnct], nodes[cnct + 1], 0)
        else:
            print(nodes[cnct], nodes[cnct + 1], edge * (base ** cnct))
    # w/ offset
    cnct += 1
    for i in range(base):
        if i == 0:
            print(nodes[-1], N, offset)
        else:
            print(nodes[-1], N, offset + i * (base ** cnct))
    # update offset and idx
    offset += max((1, base * l))
    idx += l
    # print

Fixed submission:
# encoding: utf-8
L = int(input())

# length
for l_max in range(1, 21):
    if 2 ** l_max > L: break

# encode L - 2 ** (l_max - 1)
bits_sub = [None] * l_max
L_temp = L - 2 ** (l_max - 1)
for l in range(l_max):
    bits_sub[l] = L_temp % 2
    L_temp = L_temp // 2

# result
N = l_max
M = 2 * (l_max - 1) + sum(bits_sub)
print(N, M) # oh...

# main path
for i in range(l_max - 1):
    for j in range(2):
        print(i + 1, i + 2, j * (2 ** i))

# sub path
maxlen = 2 ** (l_max - 1)
for i, bit in enumerate(bits_sub):
    if bit == 0: continue
    for j in range(bit):
        print(i + 1, l_max, maxlen)
        maxlen += 2 ** i