Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
Q = int(input())
q = [list(input().split()) for _ in range(Q)]
r = 0


for i in range(Q):
    if q[i][0] == "1":
        r += 1
    else:
        if (q[i][1] == "1" and r%2==0)or (q[i][1] == "2" and r%2==1 ):
            S = q[i][2] + S
        else:
            S = S + q[i][2]

if r%2==1:
    S = S[::-1]
print(S)


Fixed submission:
from collections import deque

S = deque(list(input()))
Q = int(input())
q = [list(input().split()) for _ in range(Q)]
r = 0


for i in range(Q):
    if q[i][0] == "1":
        r += 1
    else:
        if (q[i][1] == "1" and r%2==0)or (q[i][1] == "2" and r%2==1 ):
            S.appendleft(q[i][2])
        else:
            S.append(q[i][2])

S = "".join(S)
if r%2==1:
    S = S[::-1]
print(S)

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

for _ in range(Q):
    q = list(input().split())
    if q[0] == "1":
        S = S[::-1]
    else:
        if q[1] == "1":
            S = q[2] + S
        else:
            S = S + q[2]

print(S)

Fixed submission:
from collections import deque

S = deque(list(input()))
Q = int(input())
q = [list(input().split()) for _ in range(Q)]
r = 0


for i in range(Q):
    if q[i][0] == "1":
        r += 1
    else:
        if (q[i][1] == "1" and r%2==0)or (q[i][1] == "2" and r%2==1 ):
            S.appendleft(q[i][2])
        else:
            S.append(q[i][2])

S = "".join(S)
if r%2==1:
    S = S[::-1]
print(S)
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
l = [0]*n

for _ in range(m):
    a, s = map(int, input().split())
    s = str(s)
    if (l[a-1] and l[a-1] != s) or (a==1 and s=="0"):
        l = -1
        break
    else:
        l[a-1] = s

if l == -1:
    print(l)
else:
    print("".join(l))

Fixed submission:
n, m = map(int, input().split())
l = [0]*n

for _ in range(m):
    a, s = map(int, input().split())
    s = str(s)
    if n == 1 and (a==1 and s=="0"):
        l[0] = s
    elif (l[a-1] and l[a-1] != s) or (a==1 and s=="0"):
        l = [-1]
        break
    else:
        l[a-1] = s

num = "".join(map(str, l))

if num[0] == "0" and n != 1:
    print("1" + num[1:])
else:
    print(num)
Buggy python submission (verdict: Time Limit Exceeded):
n, a, b = map(int, input().split())
mod = 10**9+7
sum = (2**n-1)%mod

def comb(m):
    x = 1
    y = 1
    for i in range(m):
        x = x*(n-i)%mod #コンビネーションの分子
        y = y*(i+1)%mod #コンビネーションの分母
    return (x * pow(y, mod-2, mod) % mod)

print((sum-comb(a)-comb(b))%mod)


Fixed submission:
n, a, b = map(int, input().split())
mod = 10**9+7
sum = pow(2, n, mod) - 1 #(2**n-1)%modと同じ

def comb(m):
    x = 1
    y = 1
    for i in range(m):
        x = x*(n-i)%mod #コンビネーションの分子
        y = y*(i+1)%mod #コンビネーションの分母
    return (x * pow(y, mod-2, mod) % mod)

print((sum-comb(a)-comb(b))%mod)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
p = list(map(int, input().split()))
l = []

for i in range(n-k+1):
    num = 0
    for j in range(k):
        num += p[i+j]
    l.append(num)

print((max(l)+k)/2)


Fixed submission:
n, k = map(int, input().split())
p = list(map(int, input().split()))
l = []

num = 0
for j in range(k):
    num += p[j]
l.append(num)

for i in range(n-k):
    l.append(l[i]-p[i]+p[i+k])

print((max(l)+k)/2)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)
#print(L)
ans = 0

for i in range(N-2):
    for j in range(i+1, N-1):
        left = j
        right = N
        target = L[i]-L[j]
        while right-left > 1:
            mid = (right + left)//2
            #print(mid)

            if L[mid] > target:
                left = mid
            else:
                right = mid

        ans += left-j

print(ans)

Fixed submission:
from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)
#print(L)
ans = 0

"""
これだとTLEしてしまう
for i in range(N-2):
    for j in range(i+1, N-1):
        left = j
        right = N
        target = L[i]-L[j]
        while right-left > 1:
            mid = (right + left)//2
            #print(mid)

            if L[mid] > target:
                left = mid
            else:
                right = mid

        ans += left-j
        """

L.sort()
for i in range(N):
    for j in range(i+1, N):
        target = L[i]+L[j]
        left = bisect_left(L, target) #二分探索の関数
        ans += max(0, left-j-1)


print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from math import gcd

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

m = gcd(A, B)
#print(m)

num = m+1
ans = 1

for i in range(2,num):
    if m%i:
        continue
    ans += 1
    while not m%i:
        m = m/i

print(ans)

Fixed submission:
from math import gcd

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

m = gcd(A, B)
#print(m)

num = int(m**0.5) #mに対する素因数分解は、int(√m)の場合を調べればよい
ans = 1

for i in range(2,num+1):
    if m%i:
        continue
    ans += 1
    while not m%i:
        m /= i

if m>1:
    ans+=1 #m+1が素因数の場合がある

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

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

A = list(map(int, input().split()))
A.sort()
#print(A)

for _ in range(M):
    a = int(A.pop()/2)
    bisect.insort_left(A, a)

print(sum(A))

Fixed submission:
import heapq #今回は優先度キューを使う

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

A = list(map(lambda x:-int(x), input().split())) #優先度付きキューは最小値しか出せないので、×-1して最大値を最小値にしている
#A.sort() 今回は間に合わない
heapq.heapify(A) #優先度付きキューに変換
#print(A)

for _ in range(M):
    a = heapq.heappop(A) #最小値取得
    a = -a // 2 #負のまま計算すると切り捨てが違うところで起こる
    heapq.heappush(A,-a) #優先度付きキューに挿入

print(-sum(A))

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

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

A = list(map(int, input().split()))
A.sort()
#print(A)

for _ in range(M):
    a = A.pop()/2
    bisect.insort_left(A, a)

print(sum(list(map(int, A))))

Fixed submission:
import heapq #今回は優先度キューを使う

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

A = list(map(lambda x:-int(x), input().split())) #優先度付きキューは最小値しか出せないので、×-1して最大値を最小値にしている
#A.sort() 今回は間に合わない
heapq.heapify(A) #優先度付きキューに変換
#print(A)

for _ in range(M):
    a = heapq.heappop(A) #最小値取得
    a = -a // 2 #負のまま計算すると切り捨てが違うところで起こる
    heapq.heappush(A,-a) #優先度付きキューに挿入

print(-sum(A))
Buggy python submission (verdict: Runtime Error):
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

A, B = MAP()


print(int(A*B))

Fixed submission:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

L = input().split()
A = int(L[0])
B = int(L[1].replace(".", ""))


print(int(A*B)//100)
Buggy python submission (verdict: Runtime Error):
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
import math

N = INT()
A = LIST()


if (N == 0 and A[0] != 1) or (N > 0 and A[0] != 0):
    print(-1)
    exit()


node_min, node_max = [0]*(N+1), [0]*(N+1)
node_min[-1] = A[-1]
node_max[-1] = A[-1]
for i in reversed(range(N)):
    node_min[i] = max(math.ceil(node_min[i+1]/2) + A[i]
    node_max[i] = node_max[i+1] + A[i]


if node_min[0] > 1:
    print(-1)
    exit()

ans = 1
node = 1
for i in range(1, N+1):
    node = min(node_max[i], 2*node)
    ans += node
    node = node - A[i]


print(ans)







Fixed submission:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
import math

N = INT()
A = LIST()


if (N == 0 and A[0] != 1) or (N > 0 and A[0] != 0):
    print(-1)
    exit()


node_min, node_max = [0]*(N+1), [0]*(N+1)
node_min[-1] = A[-1]
node_max[-1] = A[-1]
for i in reversed(range(N)):
    node_min[i] = math.ceil(node_min[i+1]/2) + A[i]
    node_max[i] = node_max[i+1] + A[i]


if node_min[0] > 1:
    print(-1)
    exit()

ans = 1
node = 1
for i in range(1, N+1):
    node = min(node_max[i], 2*node)
    ans += node
    node = node - A[i]


print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))


N = INT()
A = LIST()

init_nodes = [0]*(N+1)
stems = [0]*(N+1)
init_nodes[0] = 1
stems[0] = 1


def solve():
    if N > 0:
        if A[0] > 0: return -1
    else:
        if A[0] == 1: return 1
        else: return -1

    if A[-1] == 0: return -1


    for i in range(N+1):
        if A[i] > 2**i:
            return -1


    for i in range(1, N+1):
        init_nodes[i] = 2 * stems[i-1]
        stems[i] = init_nodes[i] - A[i]
        if stems[i] < 0: return -1

    ans = sum(init_nodes)

    dif = init_nodes[-1] - A[-1]
    ans -= dif
    for i in reversed(range(N+1)):
        if init_nodes[i] - dif < 0: return -1
        dif = (dif-(init_nodes[i] - dif))//2
        if dif <= 0: break
        ans -= dif
    return ans

print(solve())







Fixed submission:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
import math

N = INT()
A = LIST()


if (N == 0 and A[0] != 1) or (N > 0 and A[0] != 0):
    print(-1)
    exit()


node_min, node_max = [0]*(N+1), [0]*(N+1)
node_min[-1] = A[-1]
node_max[-1] = A[-1]
for i in reversed(range(N)):
    node_min[i] = math.ceil(node_min[i+1]/2) + A[i]
    node_max[i] = node_max[i+1] + A[i]


if node_min[0] > 1:
    print(-1)
    exit()

ans = 1
node = 1
for i in range(1, N+1):
    node = min(node_max[i], 2*node)
    ans += node
    node = node - A[i]


print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N, M = MAP()
H = LIST()
AB = []
for _ in range(M):
    a, b = MAP()
    AB.append((a-1,b-1))
    AB.append((b-1,a-1))

ans = 0
for i in range(N):
    flag = True
    j = 0
    while flag or j < len(AB):
        a, b = AB[j][0], AB[j][1]
        if a == i and H[a] <= H[b]:
            flag = False
            break

        j += 1
        if j == len(AB):
            break

    if flag:
        ans += 1

print(ans)

 

Fixed submission:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N, M = MAP()
H = LIST()
lights = [0] * N
for _ in range(M):
    a, b = MAP()
    a -= 1; b -= 1
    if lights[a] == 0:
        if H[a] <= H[b]:
            lights[a] += 1
    if lights[b] == 0:
        if H[b] <= H[a]:
            lights[b] += 1

print(lights.count(0))

# ans = 0
# for i in range(N):
#     flag = True
#     j = 0
#     while flag or j < len(AB):
#         a, b = AB[j][0], AB[j][1]
#         if a == i and H[a] <= H[b]:
#             flag = False
#             break

#         j += 1
#         if j == len(AB):
#             break

#     if flag:
#         ans += 1
# import deque





# print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

S = input()
n = len(S)
integer = int(S)

ans = 0
for i in range(n-3):
    for j in range(i+4, n+1):
        num = (integer//10**(n-j) - integer//10**(n-i)*10**(j-i))
        if num % 2019 == 0:
            # print((integer//10**j - integer//10**i))
            ans += 1

print(ans)

Fixed submission:
S = input()

res = [0] * 2019
res[0] = 1

d = 1
a = 0

for c in reversed(S):
    a += int(c) * d
    a %= 2019
    res[a] += 1
    d *= 10
    d %= 2019

ans = 0
for r in res:
    ans += r*(r-1) // 2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

S = input()
n = len(S)

ans = 0
for i in range(n-3):
    for j in range(i+4, n+1):
        if int(S[i:j]) % 2019 == 0:
            # print(S[i:j])
            ans += 1

print(ans)

Fixed submission:
S = input()

res = [0] * 2019
res[0] = 1

d = 1
a = 0

for c in reversed(S):
    a += int(c) * d
    a %= 2019
    res[a] += 1
    d *= 10
    d %= 2019

ans = 0
for r in res:
    ans += r*(r-1) // 2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

S = input()
n = len(S)

ans = 0
for i in range(n-3):
    for j in range(i+4, n+1):
        if int(S[i:j]) % 2019 == 0:
            # print(S[i:j])
            ans += 1

print(ans)

Fixed submission:
S = input()

res = [0] * 2019
res[0] = 1

d = 1
a = 0

for c in reversed(S):
    a += int(c) * d
    a %= 2019
    res[a] += 1
    d *= 10
    d %= 2019

ans = 0
for r in res:
    ans += r*(r-1) // 2
print(ans)
Buggy python submission (verdict: Runtime Error):

N = int(input())

alphabet = "abcdefghijklmnopqrstuvwxyz"

curr_str = []

def print_str(curr_str):
    string = ""
    for i in curr_str:
        string += alphabet[i]
    print(string)


def dfs(index, curr_str, curr_char):
    if curr_char > index:
        return None
    if curr_char > max(curr_str) + 1:
        return None

    if index == N-1:
        print_str(curr_str + [curr_char])
        return None

    for i in range(N):
        dfs(index+1, curr_str+[curr_char], i)

for i in range(N):
    dfs(1, [0], i)

Fixed submission:
# https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_d

N = int(input())

alphabet = "abcdefghijklmnopqrstuvwxyz"

curr_str = []

def print_str(curr_str):
    string = ""
    for i in curr_str:
        string += alphabet[i]
    print(string)


def dfs(index, curr_str, curr_char):
    if curr_char > index:
        return None
    if curr_char > max(curr_str) + 1:
        return None

    if index == N-1:
        print_str(curr_str + [curr_char])
        return None

    for i in range(N):
        dfs(index+1, curr_str+[curr_char], i)


if N == 1:
    print("a")
else:    
    for i in range(N):
        dfs(1, [0], i)

Buggy python submission (verdict: Time Limit Exceeded):
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N = INT()

import itertools
import collections

alphabet = 'abcdefghijklmnopqrstuvwxyz'

a_set = set()
for w in itertools.product(range(N), repeat=N):
    # print(w, end=", ")
    seen = {}

    i = 0
    for l in w:
        if l not in seen.keys():
            seen[l] = i
            i += 1

    # print(seen, end="")

    ans = [0] * N

    for i in range(len(ans)):
        ans[i] = seen[w[i]]

    if tuple(ans) not in a_set:
        print("".join([alphabet[i] for i in ans]))
        a_set.add(tuple(ans))






Fixed submission:
# https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_d

N = int(input())

alphabet = "abcdefghijklmnopqrstuvwxyz"

curr_str = []

def print_str(curr_str):
    string = ""
    for i in curr_str:
        string += alphabet[i]
    print(string)


def dfs(index, curr_str, curr_char):
    if curr_char > index:
        return None
    if curr_char > max(curr_str) + 1:
        return None

    if index == N-1:
        print_str(curr_str + [curr_char])
        return None

    for i in range(N):
        dfs(index+1, curr_str+[curr_char], i)


if N == 1:
    print("a")
else:    
    for i in range(N):
        dfs(1, [0], i)
Buggy python submission (verdict: Runtime Error):
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N, A, B = MAP()

# blues = 0
# while N > 0:
#     if N - A < 0:
#         A = N
#     N -= A
#     blues += A

#     N -= B

# print(blues)

S = []

while len(S) <= N:
    S += "b" * A
    S += "r" * B

print(S[:N].count("b"))

Fixed submission:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N, A, B = MAP()



sets = N // (A+B) 
remain = N % (A+B)

blues = sets * A + min(remain, A)
print(blues)

Buggy python submission (verdict: Time Limit Exceeded):
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N, A, B = MAP()

blues = 0
while N > 0:
    if N - A < 0:
        A = N
    N -= A
    blues += A

    N -= B

print(blues)


Fixed submission:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N, A, B = MAP()



sets = N // (A+B) 
remain = N % (A+B)

blues = sets * A + min(remain, A)
print(blues)
Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
A, B = [], []
for _ in range(N):
    ai, bi = map(int, input().split())
    A.append(ai)
    B.append(bi)

inf = 10**23

d = [inf] * (H+1)
d[0] = 0
for i in range(1, H+1):
    for abi in range(N):
        if A[abi] >= i:
            d[i] = min(d[i], B[abi])
        else:
            d[i] = min(d[i], d[i-A[abi]] + B[abi])


print(d[H])




Fixed submission:


H, N = map(int, input().split())
A, B = [], []
for _ in range(N):
    ai, bi = map(int, input().split())
    A.append(ai)
    B.append(bi)

inf = 10**23

d = [inf] * (H+1)
d[0] = 0
for i in range(1, H+1):
    for abi in range(N):
        if A[abi] >= i:
            d[i] = min(d[i], B[abi])
        else:
            d[i] = min(d[i], d[i-A[abi]] + B[abi])


print(d[H])
Buggy python submission (verdict: Runtime Error):
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N = INT()
P = LIST()
Q = LIST()

import itertools

for i, l in enumerate(itertools.permutations(range(1, N+1), N)):
    if list(l) == P:
        a = i+1
    elif list(l) == Q:
        b = i+1

print(abs(a-b))

Fixed submission:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N = INT()
P = LIST()
Q = LIST()

import itertools

for i, l in enumerate(itertools.permutations(range(1, N+1), N)):
    if list(l) == P:
        a = i+1
    if list(l) == Q:
        b = i+1

print(abs(a-b))

Buggy python submission (verdict: Runtime Error):
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N = INT()
P = LIST()
Q = LIST()

import itertools

for i, l in enumerate(itertools.permutations(range(1, N+1), N)):
    if list(l) == P:
        a = i+1
    elif list(l) == Q:
        b = i+1

print(abs(a-b))

Fixed submission:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N = INT()
P = LIST()
Q = LIST()

import itertools

for i, l in enumerate(itertools.permutations(range(1, N+1), N)):
    if list(l) == P:
        a = i+1
    if list(l) == Q:
        b = i+1

print(abs(a-b))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
ans = set()

for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            ans.add(S[i]+S[j]+S[k])
print(len(ans))

Fixed submission:
N = int(input())
S = input()
ans = 0

for i in range(0, 1000):
    i = str(i).zfill(3)
    idx = 0
    for j in range(3):
        if i[j] in S[idx:]:
            idx += S[idx:].index(i[j])+1
            continue
        else:
            break
    else:
        ans += 1

    


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

ans = N-1

def get_steps(a, b):
    return (a-1) + (b-1)


for i in range(1, N//2+1):
    if N % i == 0:
        d = N // i
        ans = min(ans, get_steps(i, d))

print(ans)

Fixed submission:
N = int(input())

ans = N-1

def get_steps(a, b):
    return (a-1) + (b-1)


for i in range(1, int(N**0.5)+1):
    if N % i == 0:
        d = N // i
        ans = min(ans, get_steps(i, d))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L = [int(i) for i in input().split()]


ans = 0
for a in range(N-2):
    for b in range(a+1, N-1):
        for c in range(b+1, N):
            # print(L[a], L[b], L[c])
            if L[a] < L[b]+L[c] and L[b] < L[a]+L[c] and L[c] < L[a]+L[b]:
                ans += 1

print(ans)

Fixed submission:
N = int(input())
L = [int(i) for i in input().split()]

import bisect
L.sort()
ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        idx = bisect.bisect_left(L, L[i]+L[j])
        ans += (idx-(j+1))

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L = [int(i) for i in input().split()]


from itertools import combinations

ans = 0
for a, b, c in combinations(L,3):
    # print(a, b, c)
    if a<b+c and b<a+c and c<a+b:
        ans += 1
        # print(a, b, c)

print(ans)

Fixed submission:
N = int(input())
L = [int(i) for i in input().split()]

import bisect
L.sort()
ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        idx = bisect.bisect_left(L, L[i]+L[j])
        ans += (idx-(j+1))

print(ans)
Buggy python submission (verdict: Runtime Error):
# https://atcoder.jp/contests/abc138/tasks/abc138_d

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N, Q = MAP()
ab = []
for _ in range(N-1):
    a, b = MAP()
    ab.append((a, b))

ans = [None] + [0]*N

check = set()
def dfs(root, x):
    global ans, check
    for i in range(N-1):
        if ab[i][0] == root:
            if root not in check:
                ans[root] += x
                check.add(root)
            ans[ab[i][1]] += x
            check.add(ab[i][1])
            dfs(ab[i][1], x)
        if ab[i][1] == root:
            if root not in check:
                ans[root] += x
                check.add(root)


for _ in range(Q):
    p, x = MAP()
    dfs(p, x)
    check = set()

print(" ".join([str(i) for i in ans[1:]]))
    



Fixed submission:
# https://atcoder.jp/contests/abc138/tasks/abc138_d
#　木探索

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

from collections import deque

N, Q = MAP()
counter = [0]*N
tree = [[] for _ in range(N)]
parent = [-1]*N
for _ in range(N-1):
    a, b = MAP()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

for _ in range(Q):
    p, x = MAP()
    counter[p-1] += x

q = deque()
q.append(0)

while q:
    index = q.pop()
    pindex = parent[index]
    for i in tree[index]:
        if i == pindex:
            continue
        counter[i] += counter[index]
        parent[i] = index
        q.append(i)

print(*counter)
Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc134/tasks/abc134_e

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N = INT()
A = []

for _ in range(N):
    A.append(INT())

DP = [0] * N
DP[0] = 1
inc_dic = {0: 0}
color = 0
for i in range(1, N):
    if A[i-1] < A[i]:
        DP[i] = DP[i-1]
        inc_dic[color] = i
        continue
    else:
        for j in inc_dic.keys():
            if A[inc_dic[j]] < A[i]:
                DP[i] = DP[i-1]
                inc_dic[j] = i
                color = j
                break
        else:
            DP[i] = DP[i-1] + 1
            color = max(inc_dic.keys()) + 1
            inc_dic[color] = i

print(DP[-1])



Fixed submission:
# https://atcoder.jp/contests/abc134/tasks/abc134_e

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
from collections import deque
from bisect import bisect_left

N = INT()
A = []

for _ in range(N):
    A.append(INT())

t = deque([A[0]])
for a in A[1:]:
    i = bisect_left(t, a) - 1
    if i == -1:
        t.appendleft(a)
    else:
        t[i] = a

print(len(t))