Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)

N, Q = map(int, input().split())
tree = [[] for _ in range(N)]
ans = [0]*N
for _ in range(N-1):
    aa, bb = map(int, input().split())
    tree[aa-1].append(bb - 1)
    tree[bb-1].append(aa - 1)


for _ in range(Q):
    q, x = map(int, input().split())
    ans[q-1] += x

def DFS(x, pre):
    global ans
    for i in tree[x]:
        if i==pre:
            continue

        ans[i] += ans[x]
        DFS(i, x)

    return

DFS(0, -1)
for x in ans:
    print(x)



Fixed submission:
import sys
from collections import deque

sys.setrecursionlimit(10**9)

N, Q = map(int, input().split())
tree = [[] for _ in range(N)]
ans = [0]*N
queue = deque()

for _ in range(N-1):
    aa, bb = map(int, input().split())
    tree[aa-1].append(bb - 1)
    tree[bb-1].append(aa - 1)


for _ in range(Q):
    q, x = map(int, input().split())
    ans[q-1] += x

# def DFS(x, pre):
#     global ans
#     for i in tree[x]:
#         if i==pre:
#             continue
#
#         ans[i] += ans[x]
#         DFS(i, x)
#
#     return
#
# for _ in range(Q):
#     q, x = map(int, input().split())
#     ans[q-1] += x

def DFS(x, pre):
    global ans
    for i in tree[x]:
        if i==pre:
            continue

        ans[i] += ans[x]
        queue.append((i, x))

queue.append((0, -1))
while queue:
    DFS(*queue.pop())

for x in ans:
    print(x)

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

N, Q = map(int, input().split())
tree = [[] for _ in range(N)]
ans = [0]*N
for _ in range(N-1):
    aa, bb = map(int, input().split())
    tree[aa-1].append(bb - 1)
    tree[bb-1].append(aa - 1)


for _ in range(Q):
    q, x = map(int, input().split())
    ans[q-1] += x

def DFS(x, pre):
    global ans
    for i in tree[x]:
        if i==pre:
            continue

        ans[i] += ans[x]
        DFS(i, x)

    return

DFS(0, -1)
for x in ans:
    print(x)



Fixed submission:
import sys
from collections import deque

sys.setrecursionlimit(10**9)

N, Q = map(int, input().split())
tree = [[] for _ in range(N)]
ans = [0]*N
queue = deque()

for _ in range(N-1):
    aa, bb = map(int, input().split())
    tree[aa-1].append(bb - 1)
    tree[bb-1].append(aa - 1)


for _ in range(Q):
    q, x = map(int, input().split())
    ans[q-1] += x

# def DFS(x, pre):
#     global ans
#     for i in tree[x]:
#         if i==pre:
#             continue
#
#         ans[i] += ans[x]
#         DFS(i, x)
#
#     return
#
# for _ in range(Q):
#     q, x = map(int, input().split())
#     ans[q-1] += x

def DFS(x, pre):
    global ans
    for i in tree[x]:
        if i==pre:
            continue

        ans[i] += ans[x]
        queue.append((i, x))

queue.append((0, -1))
while queue:
    DFS(*queue.pop())

for x in ans:
    print(x)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque

s = input()
t = input()
n = len(s)
cnt = {}
s = s*2

for i, x in enumerate(s):
    if x not in cnt:
        cnt[x] = []
    cnt[x].append(i)

suffix = 0
idx = 0
ten = 0
for z in t:
    if z not in s:
        print(-1)
        sys.exit()

    idx = ([m for m in cnt[z][::-1] if m>=idx]).pop(-1) + 1

    if idx>=n:
        idx -= n
        ten += 1

suffix = idx + ten * n
print(suffix)

Fixed submission:
import sys
import bisect

ss = input()
t = input()
n = len(ss)
cnt = {}
s = ss*2

for i, x in enumerate(s):
    if x not in cnt:
        cnt[x] = []
    cnt[x].append(i)

idx = 0
ten = 0
#print(cnt)
for z in t:
    if z not in ss:
        print(-1)
        sys.exit()

    idx = cnt[z][bisect.bisect_left(cnt[z], idx)] + 1

    if idx>=n:
        idx -= n
        ten += 1

    #print(idx, z, ten)

suffix = idx + ten * n

print(suffix)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque

s = input()
t = input()
n = len(s)
cnt = {}
s = s*2

for i, x in enumerate(s):
    if x not in cnt:
        cnt[x] = []
    cnt[x].append(i)

for y in t:
    if y not in s:
        print(-1)
        sys.exit()

suffix = 0
idx = 0
ten = 0
for z in t:
    idx = ([m for m in cnt[z][::-1] if m>=idx]).pop(-1) + 1

    if idx>=n:
        idx -= n
        ten += 1

suffix = idx + ten * n
print(suffix)

Fixed submission:
import sys
import bisect

ss = input()
t = input()
n = len(ss)
cnt = {}
s = ss*2

for i, x in enumerate(s):
    if x not in cnt:
        cnt[x] = []
    cnt[x].append(i)

idx = 0
ten = 0
#print(cnt)
for z in t:
    if z not in ss:
        print(-1)
        sys.exit()

    idx = cnt[z][bisect.bisect_left(cnt[z], idx)] + 1

    if idx>=n:
        idx -= n
        ten += 1

    #print(idx, z, ten)

suffix = idx + ten * n

print(suffix)

Buggy python submission (verdict: Time Limit Exceeded):
import sys

s = input()
t = input()
n = len(s)
cnt = {}
s = s*2

for i, x in enumerate(s):
    if x not in cnt:
        cnt[x] = []
    cnt[x].append(i)

for y in t:
    if y not in s:
        print(-1)
        sys.exit()

suffix = 0
idx = 0
ten = 0
for z in t:
    idx = min([m for m in cnt[z] if m>=idx]) + 1

    if idx>=n:
        idx -= n
        ten += 1

suffix = idx + ten * n
print(suffix)

Fixed submission:
import sys
import bisect

ss = input()
t = input()
n = len(ss)
cnt = {}
s = ss*2

for i, x in enumerate(s):
    if x not in cnt:
        cnt[x] = []
    cnt[x].append(i)

idx = 0
ten = 0
#print(cnt)
for z in t:
    if z not in ss:
        print(-1)
        sys.exit()

    idx = cnt[z][bisect.bisect_left(cnt[z], idx)] + 1

    if idx>=n:
        idx -= n
        ten += 1

    #print(idx, z, ten)

suffix = idx + ten * n

print(suffix)
Buggy python submission (verdict: Time Limit Exceeded):
Q = int(input())
MAX = 10**5

def findAllOfPrime(N):
    prime = [True] * (N + 1)
    prime[0] = False
    prime[1] = False

    x = 2
    while x**2 <= N:
        if prime[x]:
            j = 2
            while x * j <= N:
                prime[x * j] = False
                j += 1
        x += 1

    return prime

prime = findAllOfPrime(MAX)

for _ in range(Q):
    cnt = 0
    l, r = map(int, input().split())

    for x in range(l, r + 1):
        if prime[x] and prime[(x + 1) // 2]:
            cnt += 1

    print(cnt)




Fixed submission:
Q = int(input())
MAX = 10**5

def findAllOfPrime(N):
    prime = [True] * (N + 1)
    prime[0] = False
    prime[1] = False

    x = 2
    while x**2 <= N:
        if prime[x]:
            j = 2
            while x * j <= N:
                prime[x * j] = False
                j += 1
        x += 1

    return prime

prime = findAllOfPrime(MAX)
primeSum = [0] * (MAX + 1)
for x in range(1, MAX + 1):
    primeSum[x] = primeSum[x - 1]
    if prime[x] and prime[(x + 1) // 2]:
        primeSum[x] += 1
        

for _ in range(Q):
    cnt = 0
    l, r = map(int, input().split())

    print(primeSum[r] - primeSum[l - 1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys

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

dif = []
for idx, v in enumerate(A_list, 1):
    dif.append(v - idx)
b = 0
dif_num = sum(map(abs, (map(lambda x: x + b, dif))))
b = 1
dif_num_plus = sum(map(abs, (map(lambda x: x + b, dif))))
b = -1
dif_num_minus = sum(map(abs, (map(lambda x: x + b, dif))))
if dif_num <= dif_num_plus and dif_num < dif_num_minus:
    print(dif_num)
    sys.exit()

p_f = True
if dif_num_plus < dif_num_minus:
    p_f = True
    b = 1
else:
    p_f = False
    b = -1

dif_num = min(dif_num, dif_num_plus, dif_num_minus)

while True:
    if p_f:
        b += 1
    else:
        b -= 1
    l = list((map(lambda x: x + b, dif)))
    dif_num2 = sum(map(abs, (map(lambda x: x + b, dif))))
    if dif_num2 < dif_num:
        dif_num = dif_num2
    else:
        break
print(dif_num)


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

dif = []
for idx, v in enumerate(A_list, 1):
    dif.append(v - idx)

dif.sort()
if len(dif) % 2 == 1:
    b = dif[len(dif) // 2]
    print(sum(map(abs, (map(lambda x: x - b, dif)))))
else:
    b1 = dif[len(dif) // 2 - 1]
    b2 = dif[len(dif) // 2]
    print(min(sum(map(abs, (map(lambda x: x - b1, dif)))),
              sum(map(abs, (map(lambda x: x - b2, dif))))))
Buggy python submission (verdict: Time Limit Exceeded):
def judge():
    four = []
    even = []
    odd = []
    for a in a_list:
        if a % 2 == 1:
            odd.append(a * 3)
        else:
            if a % 4 == 0:
                four.append(a)
            else:
                even.append(a)
    if len(four) > 0:
        odd.append(four.pop() // 2)
        four = [i * 3 for i in four]
        odd.extend(four)
        even = [i * 3 for i in even]
        odd.extend(even)
    else:
        if even:
            odd.append(even.pop() // 2)
            even = [i * 3 for i in even]
            odd.extend(even)
        else:
            return False
    global a_list
    a_list = odd
    return True


N = int(input())
a_list = list(map(int, input().split()))
cnt = 0
while True:
    if judge():
        cnt += 1
    else:
        break
print(cnt)


Fixed submission:
N = int(input())
a_list = list(map(int, input().split()))
cnt = 0
for a in a_list:
    if a % 2 == 0:
        while a % 2 == 0:
            a /= 2
            cnt += 1
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
K = int(input())

s_set = set()
for i in range(len(s) + 1):
    for j in range(i + 1, len(s) + 1):
        s_set.add(s[i:j])
s_list = list(s_set)
s_list.sort()
print(s_list[K - 1])


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

s_set = set()
for i in range(len(s)):
    for j in range(i + 1, i + K + 1):
        if j > len(s) + 1:
            break
        s_set.add(s[i:j])
s_list = list(s_set)
s_list.sort()
print(s_list[K - 1])
Buggy python submission (verdict: Time Limit Exceeded):
# UnionFindで参考にしたページ
# http://www.geocities.jp/m_hiroi/light/pyalgo61.html


# 集合の代表を求める
def find(x):
    while link[x] >= 0:
        x = link[x]
    return x


# 併合
def union(x, y):
    s1 = find(x)
    s2 = find(y)
    if s1 != s2:
        if link[s1] >= link[s2]:
            # 小さいほうが個数が多い
            link[s1] += link[s2]
            link[s2] = s1
        else:
            link[s2] += link[s1]
            link[s1] = s2
        return True
    return False


N, M = map(int, input().split())
p = list(map(int, input().split()))
link = [-1 for _ in range(N + 1)]

for _ in range(M):
    x, y = map(int, input().split())
    union(x, y)

cnt = 0
for i in range(1, N + 1):
    a = find(i)
    b = find(p[i - 1])
    if a == b:
        cnt += 1
print(cnt)


Fixed submission:
# UnionFindで参考にしたページ
# http://www.geocities.jp/m_hiroi/light/pyalgo61.html


# 集合の代表を求める
def find(x):
    if link[x] < 0:
        return x
    else:
        # 経路の圧縮
        link[x] = find(link[x])
        return link[x]


# 併合
def union(x, y):
    s1 = find(x)
    s2 = find(y)
    if s1 != s2:
        if link[s1] >= link[s2]:
            # 小さいほうが個数が多い
            link[s1] += link[s2]
            link[s2] = s1
        else:
            link[s2] += link[s1]
            link[s1] = s2
        return True
    return False


N, M = map(int, input().split())
p = list(map(int, input().split()))
link = [-1 for _ in range(N + 1)]

for _ in range(M):
    x, y = map(int, input().split())
    union(x, y)

cnt = 0
for i in range(1, N + 1):
    if find(i) == find(p[i - 1]):
        cnt += 1
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
num_list = list(map(int, input().split()))
cumulative_sum_list = [0]
c_s = 0
for i in num_list:
    c_s += i
    cumulative_sum_list.append(c_s)
cumulative_sum_list.sort()
cumulative_sum_set = set(cumulative_sum_list)
s = 0
for i in cumulative_sum_set:
    c = cumulative_sum_list.count(i)
    s += c * (c - 1) // 2
print(s)


Fixed submission:
from itertools import accumulate
from collections import Counter

N = int(input())
num_list = list(map(int, input().split()))
cumulative_sum_list = list(accumulate(num_list))
cumulative_sum_list.append(0)

c = Counter(cumulative_sum_list)
s = 0
for i in c.values():
    s += i * (i - 1) // 2
print(s)

Buggy python submission (verdict: Runtime Error):
N = int(input())
num_list = list(map(int, input().split()))
cumulative_sum_list = [0]
c_s = 0
for i in num_list:
    c_s += i
    cumulative_sum_list.append(c_s)
cumulative_sum_list.sort()
cumulative_sum_set = set(cumulative_sum_list)
cumulative_dif = [0, 0]
for idx, i in enumerate(range(1, 2 * (10 ** 5)), 2):
    cumulative_dif.append(cumulative_dif[idx - 1] + i)
s = 0
for i in cumulative_sum_set:
    s += cumulative_dif[cumulative_sum_list.count(i)]
print(s)


Fixed submission:
from itertools import accumulate
from collections import Counter

N = int(input())
num_list = list(map(int, input().split()))
cumulative_sum_list = list(accumulate(num_list))
cumulative_sum_list.append(0)

c = Counter(cumulative_sum_list)
s = 0
for i in c.values():
    s += i * (i - 1) // 2
print(s)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

cnt = 0
S_list = [input() for _ in range(N)]


def count_symmetry(S_symmetry):
    for i in range(N):
        for j in range(N):
            if S_symmetry[i][j] != S_symmetry[j][i]:
                return False
    return True


for k in range(N):
    S_symmetry = S_list[k:] + S_list[:k]
    if count_symmetry(S_symmetry):
        cnt += 1

print(cnt * N)


Fixed submission:
N = int(input())
S_list = [input() for _ in range(N)]
cnt = 0


def count_symmetry(S_symmetry):
    for i in range(N):
        for j in range(i + 1, N):
            if S_symmetry[i][j] != S_symmetry[j][i]:
                return False
    return True


for k in range(N):
    S_symmetry = S_list[k:] + S_list[:k]
    if count_symmetry(S_symmetry):
        cnt += 1

print(cnt * N)

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

cnt = 0
S_list = [list(input()) for _ in range(N)]
S_symmetry = [['' for _ in range(N)] for _ in range(N)]


def count_symmetry():
    for i in range(N):
        for j in range(N):
            if S_symmetry[i][j] != S_symmetry[j][i]:
                return False
    return True


for k in range(N):
    for i in range(N):
        for j in range(N):
            S_symmetry[i][(j + k) % N] = S_list[i][j]
    if count_symmetry():
        cnt += 1

print(cnt * N)


Fixed submission:
N = int(input())
S_list = [input() for _ in range(N)]
cnt = 0


def count_symmetry(S_symmetry):
    for i in range(N):
        for j in range(i + 1, N):
            if S_symmetry[i][j] != S_symmetry[j][i]:
                return False
    return True


for k in range(N):
    S_symmetry = S_list[k:] + S_list[:k]
    if count_symmetry(S_symmetry):
        cnt += 1

print(cnt * N)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
X_list = list(map(int, input().split()))
idx_value = []

for idx, v in enumerate(X_list, 1):
    idx_value.append((idx, v,))

i_list = [i for i in range(1, N + 1)]
idx_value_copy = idx_value.copy()
idx_value_copy.sort(key=lambda x: x[1])
li_list = []
for t in idx_value:
    for idx, t_c in enumerate(idx_value_copy, 1):
        if t_c[0] == t[0] and t_c[1] == t[1]:
            li_list.append(idx)
            break

median_idx = int(N / 2)
median_left = idx_value_copy[median_idx - 1][1]
median_right = idx_value_copy[median_idx][1]
for i in li_list:
    if i <= median_idx:
        print(median_right)
    else:
        print(median_left)


Fixed submission:
N = int(input())
X_list = list(map(int, input().split()))
X_list_copy = X_list.copy()
X_list_copy.sort()

median_idx = int(N / 2)
left_num = X_list_copy[median_idx - 1]
right_num = X_list_copy[median_idx]

for x in X_list:
    if x < right_num:
        print(right_num)
    else:
        print(left_num)

Buggy python submission (verdict: Time Limit Exceeded):
import statistics

N = int(input())
#N = 200000
X_list = list(map(int, input().split()))
#X_list = [i for i in range(N)]

median_idx = int(len(X_list) / 2) - 1

for idx, v in enumerate(X_list):
    X_copy = X_list.copy()
    X_copy.pop(idx)
    # median_idx = int((len(X_copy) + 1) / 2) - 1
    # print(median_idx)
    # X_copy.sort()
    print(int(statistics.median(X_copy)))


Fixed submission:
N = int(input())
X_list = list(map(int, input().split()))
X_list_copy = X_list.copy()
X_list_copy.sort()

median_idx = int(N / 2)
left_num = X_list_copy[median_idx - 1]
right_num = X_list_copy[median_idx]

for x in X_list:
    if x < right_num:
        print(right_num)
    else:
        print(left_num)

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

median_idx = int(len(X_list) / 2) - 1

for idx, v in enumerate(X_list):
    X_copy = X_list.copy()
    X_copy.pop(idx)
    #median_idx = int((len(X_copy) + 1) / 2) - 1
    #print(median_idx)
    X_copy.sort()
    print(X_copy[median_idx])


Fixed submission:
N = int(input())
X_list = list(map(int, input().split()))
X_list_copy = X_list.copy()
X_list_copy.sort()

median_idx = int(N / 2)
left_num = X_list_copy[median_idx - 1]
right_num = X_list_copy[median_idx]

for x in X_list:
    if x < right_num:
        print(right_num)
    else:
        print(left_num)
Buggy python submission (verdict: Time Limit Exceeded):
A, B, K = map(int, input().split())

l = [i for i in range(A, B + 1)]
small = l[:K]
big = l[-K:]
small.extend(big)
small = list(set(small))
small.sort()
for i in small:
    print(i)

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

ans = set()
for i in range(0, K):
    if A + i <= B:
        ans.add(A + i)
    if B - i >= A:
        ans.add(B - i)
ans = list(ans)
ans.sort()
for i in ans:
    print(i)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A_list = [0]
A_list.extend(list(map(int, input().split())))
A_list.append(0)
previous_val = 0
dif = []
for i in A_list[1:]:
    dif.append(previous_val - i)
    previous_val = i

for idx, val in enumerate(dif):
    if idx < len(dif)-1:
        tmp1 = dif[idx]
        tmp2 = dif[idx + 1]
        dif[idx] = 0
        dif[idx + 1] = 0
        print(sum(map(abs, dif)) + abs(tmp1 + tmp2))
        dif[idx] = tmp1
        dif[idx + 1] = tmp2


Fixed submission:
N = int(input())
A_list = [0]
A_list.extend(list(map(int, input().split())))
A_list.append(0)
previous_val = 0
S = 0
for i in A_list[1:]:
    S += abs(previous_val - i)
    previous_val = i

for idx, val in enumerate(A_list):
    if idx == 0 or idx == (len(A_list) - 1):
        continue
    else:
        new_dif = abs(A_list[idx - 1] - A_list[idx + 1])
        old_dif = abs(A_list[idx - 1] - A_list[idx]) + abs(A_list[idx] - A_list[idx + 1])
        print(S + new_dif - old_dif)
Buggy python submission (verdict: Runtime Error):
from collections import deque

H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]
dot_cnt = 0
for g in grid:
    dot_cnt += g.count('.')
sy = 0
sx = 0
gy = H - 1
gx = W - 1

deq = deque()
deq.append((0, 0))
grid[0][0] = 0

y_list = [-1, 1, 0, 0]
x_list = [0, 0, -1, 1]

while deq:
    y, x = deq.popleft()
    if y == gy and x == gx:
        break
    for i in range(len(y_list)):
        dy = y + y_list[i]
        dx = x + x_list[i]
        if dy < 0 or H <= dy or dx < 0 or W <= dx:
            continue
        if grid[dy][dx] == '.':
            deq.append((dy, dx))
            grid[dy][dx] = grid[y][x] + 1
print(dot_cnt - (grid[gy][gx] + 1))


Fixed submission:
from collections import deque

H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]
dot_cnt = 0
for g in grid:
    dot_cnt += g.count('.')
sy = 0
sx = 0
gy = H - 1
gx = W - 1

deq = deque()
deq.append((0, 0))
grid[0][0] = 0

y_list = [-1, 1, 0, 0]
x_list = [0, 0, -1, 1]

while deq:
    y, x = deq.popleft()
    if y == gy and x == gx:
        break
    for i in range(len(y_list)):
        dy = y + y_list[i]
        dx = x + x_list[i]
        if dy < 0 or H <= dy or dx < 0 or W <= dx:
            continue
        if grid[dy][dx] == '.':
            deq.append((dy, dx))
            grid[dy][dx] = grid[y][x] + 1
if grid[gy][gx] == '.':
    print(-1)
else:
    print(dot_cnt - (grid[gy][gx] + 1))
Buggy python submission (verdict: Time Limit Exceeded):
N, C = map(int, input().split())
program = []
program_list = [0 for _ in range((((10 ** 5) * 2) + 10))]
for _ in range(C + 1):
    program.append(program_list.copy())
sm = program_list.copy()

s_list = []
t_list = []
c_list = []
for _ in range(N):
    s, t, c = map(int, input().split())
    s_list.append(s)
    t_list.append(t)
    c_list.append(c)

for i in range(1, C + 1):
    for j in range(len(s_list)):
        if i == c_list[j]:
            program[i][(s_list[j] * 2) - 1] += 1
            program[i][(t_list[j] * 2)] -= 1
    for j in range(1, len(program_list)):
        program[i][j] += program[i][j - 1]
    for j in range(0, len(program_list)):
        if program[i][j] > 0:
            sm[j] += 1
print(max(sm))


Fixed submission:
N, C = map(int, input().split())
program = []
program_list = [False for _ in range((((10 ** 5) * 2) + 10))]
for _ in range(C + 1):
    program.append(program_list.copy())

for _ in range(N):
    s, t, c = map(int, input().split())
    s2 = (t * 2) - ((s * 2) - 1)
    program[c][(s * 2) - 1:t * 2] = [True] * s2

max_c = 0
for i in range(len(program_list)):
    c = 0
    for j in range(1, C + 1):
        if program[j][i]:
            c += 1
        if c > max_c:
            max_c = c
print(max_c)

Buggy python submission (verdict: Time Limit Exceeded):
N, C = map(int, input().split())
program = []
program_list = [False for _ in range((((10 ** 5) * 2) + 10))]
for _ in range(C + 1):
    program.append(program_list.copy())

for _ in range(N):
    s, t, c = map(int, input().split())
    s -= 0.5
    s *= 2
    s = int(s)
    t *= 2
    for i in range(s, t):
        program[c][i] = True

max_c = 0
for i in range(len(program_list)):
    c = 0
    for j in range(1, C + 1):
        if program[j][i]:
            c += 1
    if c > max_c:
        max_c = c
print(max_c)


Fixed submission:
N, C = map(int, input().split())
program = []
program_list = [False for _ in range((((10 ** 5) * 2) + 10))]
for _ in range(C + 1):
    program.append(program_list.copy())

for _ in range(N):
    s, t, c = map(int, input().split())
    s2 = (t * 2) - ((s * 2) - 1)
    program[c][(s * 2) - 1:t * 2] = [True] * s2

max_c = 0
for i in range(len(program_list)):
    c = 0
    for j in range(1, C + 1):
        if program[j][i]:
            c += 1
        if c > max_c:
            max_c = c
print(max_c)
Buggy python submission (verdict: Runtime Error):
import fractions


def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


N = int(input())
t1 = int(input())
t2 = int(input())
t = lcm(t1, t2)
for _ in range(2, N):
    t = lcm(t, int(input()))
print(t)


Fixed submission:
import fractions


def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


N = int(input())
if N == 1:
    print(input())
else:
    t1 = int(input())
    t2 = int(input())
    t = lcm(t1, t2)
    for _ in range(2, N):
        t = lcm(t, int(input()))
    print(t)
Buggy python submission (verdict: Runtime Error):
N = int(input())
adj_list = [[] for _ in range(N)]
depth = [float('inf')] * 100010


def dfs(v, p, d):
    depth[v] = d
    for adj in adj_list[v]:
        if adj[0] == p:
            continue
        dfs(adj[0], v, d + adj[1])


for _ in range(N - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    adj_list[a].append((b, c))
    adj_list[b].append((a, c))

Q, K = map(int, input().split())
dfs(K - 1, -1, 0)

for _ in range(Q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    print(depth[x] + depth[y])


Fixed submission:
import heapq


def dijkstra(K):
    c_l = [float('inf')] * N
    c_l[K] = 0
    hq = [(0, K)]
    while hq:
        u = heapq.heappop(hq)[1]
        for nv, c in adj_list[u]:
            if c_l[nv] > c_l[u] + c:
                c_l[nv] = c_l[u] + c
                heapq.heappush(hq, (c_l[u] + c, nv))
    return c_l


N = int(input())
adj_list = [[] for _ in range(N)]

for _ in range(N - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    adj_list[a].append((b, c))
    adj_list[b].append((a, c))

Q, K = map(int, input().split())
c_l = dijkstra(K - 1)

for _ in range(Q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    print(c_l[x] + c_l[y])