Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

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

def bfs(maze,visited,gx,gy):
    stack = deque([[0,0]])
    if maze[0][0] == '#':
        visited[0][0] = 1 
    else:
        visited[0][0] = 0 
    while stack:
        y,x = stack.pop()
        count = visited[y][x]
        
        for j,k in ([1,0],[0,1]):
            new_y,new_x = y+j,x+k
            if  new_x >= gx or  new_y >= gy:
                continue
            elif maze[new_y][new_x] == "#" and maze[y][x] == '.':
                visited[new_y][new_x] = min(count+1,visited[new_y][new_x])
                stack.appendleft([new_y, new_x])
            else:
                visited[new_y][new_x] = min(count,visited[new_y][new_x])
                stack.appendleft([new_y, new_x])
    return visited[gy-1][gx-1]

inf = float('inf')
visited = [[inf]*W for _ in range(H)]
print(bfs(maze,visited,W,H))


Fixed submission:
from collections import deque

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

def bfs(maze,visited,gx,gy):
    stack = deque([[0,0]])
    if maze[0][0] == '#':
        visited[0][0] = 1 
    else:
        visited[0][0] = 0 
    while stack:
        y,x = stack.pop()
        count = visited[y][x]
        
        for j,k in ([1,0],[0,1]):
            new_y,new_x = y+j,x+k
            if  new_x >= gx or  new_y >= gy:
                continue
            elif maze[new_y][new_x] == "#" and maze[y][x] == '.' and visited[new_y][new_x] > count+1:
                visited[new_y][new_x] = count+1
                stack.appendleft([new_y, new_x])
            elif maze[new_y][new_x] == "#" and maze[y][x] == '.' and visited[new_y][new_x] <= count+1:
                continue
            elif visited[new_y][new_x] > count:
                visited[new_y][new_x] = count
                stack.appendleft([new_y, new_x])
    return visited[gy-1][gx-1]

inf = float('inf')
visited = [[inf]*W for _ in range(H)]
print(bfs(maze,visited,W,H))
Buggy python submission (verdict: Runtime Error):
from collections import deque
N = int(input())
alpha = ['a','b','c','d','e','f','g','h','i','j']
ans = []

stack = deque(['a'])

while stack:
    print(stack)
    if len(stack[-1]) == N:
        break
    s = stack.pop()
    s_list = list(s)
    index = alpha.index(s_list[-1])
    print(index)
    for i in range(index+2):
        stack.appendleft(s+alpha[i])
    

stack.reverse()
for j in range(len(stack)):
    print(stack[j])



Fixed submission:
from collections import deque
N = int(input())
alpha = ['a','b','c','d','e','f','g','h','i','j']
ans = []

stack = deque(['a'])

while stack:
    if len(stack[-1]) == N:
        break
    s = stack.pop()
    s_list = sorted(list(s))
    index = alpha.index(s_list[-1])
    for i in range(index+2):
        stack.appendleft(s+alpha[i])
    

stack.reverse()
for j in range(len(stack)):
    print(stack[j])
Buggy python submission (verdict: Time Limit Exceeded):
S = list(input())
Q = int(input())
L = []
count = 0
for i in range(Q):
    l = list(input().split())
    if len(l) == 1:
        count +=1
    else:
        l[1] = int(l[1])
        if count%2 == 1:
            if l[1] == 1:
                l[1] = 2
            else:
                l[1] = 1
        if l[1] == 1:
            S.insert(0,l[2])
        else:
            S.append(l[2])

if count%2 == 0:
    print(''.join(S))
else:
    S.reverse()
    print(''.join(S))



Fixed submission:
from collections import deque
S = deque(input())
Q = int(input())
count = 0
for i in range(Q):
    l = list(input().split())
    if len(l) == 1:
        count +=1
    else:
        l[1] = int(l[1])
        if count%2 == 1:
            if l[1] == 1:
                l[1] = 2
            else:
                l[1] = 1
        if l[1] == 1:
            S.appendleft(l[2])
        else:
            S.append(l[2])

if count%2 == 0:
    print(''.join(list(S)))
else:
    S.reverse()
    print(''.join(list(S)))

Buggy python submission (verdict: Time Limit Exceeded):
S = list(input())
Q = int(input())
L = []
for i in range(Q):
    l = list(input().split())
    if len(l) == 1:
        S.reverse()
    else:
        l[1] = int(l[1])
        if l[1] == 1:
            S.insert(0,l[2])
        else:
            S.append(l[2])
        
print(''.join(S))



Fixed submission:
from collections import deque
S = deque(input())
Q = int(input())
count = 0
for i in range(Q):
    l = list(input().split())
    if len(l) == 1:
        count +=1
    else:
        l[1] = int(l[1])
        if count%2 == 1:
            if l[1] == 1:
                l[1] = 2
            else:
                l[1] = 1
        if l[1] == 1:
            S.appendleft(l[2])
        else:
            S.append(l[2])

if count%2 == 0:
    print(''.join(list(S)))
else:
    S.reverse()
    print(''.join(list(S)))
Buggy python submission (verdict: Runtime Error):
N,K = list(map(int, input().split()))
p = list(map(int, input().split()))
max_l = 0
Max_l = p[0:K]

for i in range(N-K+1):
    m = sum(p[i:i+K])
    if m > max_l:
        max_l = m
        Max_l = p[i:i+K]


print((sum(L)+K)//2)

Fixed submission:
N,K = list(map(int, input().split()))
p = list(map(int, input().split()))
max_l = 0
Max_l = p[0:K]
S = [0]
s=0
for j in range(N):
    s += p[j]
    S.append(s)

for i in range(N-K+1):
    m = S[K+i]-S[i]
    if m > max_l:
        max_l = m



print((max_l+K)/2)
Buggy python submission (verdict: Runtime Error):
H,N = list(map(int, input().split()))
A = []
B = []
for _ in range(N):
    a,b = list(map(int, input().split()))
    A.append(a)
    B.append(b)

dp = [float('inf') for i in range(H+max(A))]
dp[0] = 0

for i in range(H+max(A)):
    m = []
    for j in range(N):
        if i-A[j] >= 0:
            m.append(dp[i-A[j]]+B[j])
    m.append(dp[i])
    dp[i] = min(m)

print(min(dp[H:]))




Fixed submission:
H,A = list(map(int, input().split()))
i = 0
while(True):
    i += 1
    if A * i >= H:
        break

print(i)
Buggy python submission (verdict: Runtime Error):
N = int(input())
count = 0

c = [[0 for i in range(10)]for j in range(10)]

for i in range(1,N+1):
    str_i = str(i)
    c[int(str_i[0])][int(str_i[-1])] += 1

for j in range(10):
    for k in range(10):
        count += c[j][k] * c[k][j]

print(count)




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

if M >= N:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Runtime Error):
N = int(input())
S,T = list(input())
S = list(S)
T = list(T)
ans = ''

for i in range(N):
    ans += S[i]+T[i]

print(ans)


Fixed submission:
A = int(input())
B = int(input())

print(6-A-B)
Buggy python submission (verdict: Runtime Error):
N = int(input())
S,T = list(input())
ans = ''

for i in range(N):
    ans += S[i]+T[i]

print(ans)


Fixed submission:
N = int(input())
S,T = input().split()
ans = ''

for i in range(N):
    ans += S[i]+T[i]

print(ans)
Buggy python submission (verdict: Runtime Error):
import math
A,B = list(map(int, input().split()))

print(A*B//math.gcd(A,B))


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

print(A*B//fractions.gcd(A,B))

Buggy python submission (verdict: Runtime Error):
import math
A,B = list(map(int, input().split()))

print(A*B//math.gcd(A,B))


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

print(A*B//fractions.gcd(A,B))
Buggy python submission (verdict: Runtime Error):
A1,A2,A3 = list(map(int, input().split()))

if A1+A2+A3 => 22:
    print('bust')
else:
    print('win')

Fixed submission:
A1,A2,A3 = list(map(int, input().split()))

if A1+A2+A3 >= 22:
    print('bust')
else:
    print('win')
Buggy python submission (verdict: Runtime Error):
import math
A,B,X = list(map(int, input().split()))

def nedan(n):
    return A*n + B*int(math.log10(n)+1)

if nedan(1000000000) <= X:
    print(1000000000)
else:
    min = 0
    max = 1000000000
    while(True):
        if nedan((max+min)//2) <= X:
            min = (max+min)//2
        else:
            max = (max+min)//2
        
        if abs(max-min)<=1:
            break

if nedan(max) <= X:
    print(max)
else:
    print(min)



Fixed submission:
S = input()
L = ['SUN','MON','TUE','WED','THU','FRI','SAT']

print(7-L.index(S))
Buggy python submission (verdict: Time Limit Exceeded):
N,M = list(map(int, input().split()))
A = list(map(int, input().split()))

for _ in range(M):

    max_A = max(A)
    ind = A.index(max_A)
    A[ind] = max_A//2

print(sum(A))

Fixed submission:
import heapq
N,M = list(map(int, input().split()))
A = list(map(int, input().split()))
A = list(map(lambda x: x*(-1), A))

heapq.heapify(A)


for _ in range(M):
    a = heapq.heappop(A)
    a = -(-a//2)
    heapq.heappush(A,a)

print(-1*sum(A))

Buggy python submission (verdict: Time Limit Exceeded):
N,M = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort(reverse=True)

for _ in range(M):
    A[0] = A[0]//2
    A.sort(reverse=True)

print(sum(A))

Fixed submission:
import heapq
N,M = list(map(int, input().split()))
A = list(map(int, input().split()))
A = list(map(lambda x: x*(-1), A))

heapq.heapify(A)


for _ in range(M):
    a = heapq.heappop(A)
    a = -(-a//2)
    heapq.heappush(A,a)

print(-1*sum(A))
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
n = int(input())
a = list(map(int, input().split()))
a.sort()
parent = [a[-1]]
rest = a[:-1]

for _ in range(n):
    next_parent = []
    next_rest = []
    for i in parent[::-1]:
        while(rest):
            x = rest.pop()
            if x < i:
                next_parent.append(x)
                break
            else:
                next_rest.append(x)
                continue
    parent += next_parent
    parent.sort()
    next_rest.reverse()
    rest += next_rest

if len(parent) == 2**n:
    print("Yes")
else:
    print("No") 


Fixed submission:
a = int(input())
print(a*a*a)

Buggy python submission (verdict: Runtime Error):
a = input()
print(a*a*a)

Fixed submission:
a = int(input())
print(a*a*a)

Buggy python submission (verdict: Runtime Error):
a = input()
print(a*a*a)

Fixed submission:
a = int(input())
print(a*a*a)

Buggy python submission (verdict: Runtime Error):
a = input()
print(a**3)

Fixed submission:
a = int(input())
print(a*a*a)
Buggy python submission (verdict: Runtime Error):
n = int(input())
A = int(input().split())
B = int(input().split())
C = int(input().split())
S = 0
before = 100

for i in range(n):
    S += B[A[i]]
    if A[i] == before + 1:
        S += C[before]
    before = A[i]

print(S)
    


Fixed submission:
# -*- coding: utf-8 -*-
n = int(input())
A = list(map(int,(input().split())))
B = list(map(int,(input().split())))
C = list(map(int,(input().split())))
S = 0
before = 100

for i in range(n):
    S += B[A[i]-1]
    if A[i]-1 == before + 1:
        S += C[before]
    before = A[i]-1

print(S)
Buggy python submission (verdict: Runtime Error):
n = int(input())
B = list(map(int,(input().split())))

list_A = [0]*n

list_A[0] = B[0]
list_A[i-1] = B[i-2]
for i in range(1:n-2):
    list_A[i] = max(B[i],B[i+1])

print(sum(list_A))




Fixed submission:
n = int(input())
B = list(map(int,(input().split())))

list_A = [0]*n

list_A[0] = B[0]
list_A[n-1] = B[n-2]
for i in range(1,n-1):
    list_A[i] = min(B[i-1],B[i])

print(sum(list_A))
Buggy python submission (verdict: Runtime Error):
N = int(input())
P = list(map(int, input().split()))
 
left_bigger  = [0] + [i for i in range(N+1)]
right_bigger = [i+1 for i in range(N+1)] + [N+1]
 
E = [(v, i+1) for i, v in enumerate(P)]
E.sort()

ans = 0
for v,i in E:
    l0=left_bigger[i]
    l1=left_bigger[l0]
    r0=right_bigger[i]
    r1=right_bigger[r0]
    print(left_bigger)
    ans += ((r1-r0)*(i-l0) + (r0-i)*(l0-l1))*v
    left_bigger[r0]=l0
    right_bigger[l0]=r0
print(ans)




Fixed submission:
N = int(input())
P = list(map(int, input().split()))
 
left_bigger  = [0] + [i for i in range(N+1)]
right_bigger = [i+1 for i in range(N+1)] + [N+1]
 
E = [(v, i+1) for i, v in enumerate(P)]
E.sort()

ans = 0
for v,i in E:
    l0=left_bigger[i]
    l1=left_bigger[l0]
    r0=right_bigger[i]
    r1=right_bigger[r0]
    ans += ((r1-r0)*(i-l0) + (r0-i)*(l0-l1))*v
    left_bigger[r0]=l0
    right_bigger[l0]=r0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = list(map(int,(input().split())))
S = 0
max_1 = 0
max_2 = 0

for i in range(1,len(P)):
    max_1 = max(P[i-1],P[i])
    max_2 = min(P[i-1],P[i])
    S += max_2
    for j in range(i-1):
        n = i-j-2
        if P[n] > max_1:
            max_2 = max_1
            max_1 = P[n]
        elif P[n] > max_2:
            max_2 = P[n]
        S += max_2

print(S)

Fixed submission:
N = int(input())
P = list(map(int, input().split()))
 
left_bigger  = [0] + [i for i in range(N+1)]
right_bigger = [i+1 for i in range(N+1)] + [N+1]
 
E = [(v, i+1) for i, v in enumerate(P)]
E.sort()

ans = 0
for v,i in E:
    l0=left_bigger[i]
    l1=left_bigger[l0]
    r0=right_bigger[i]
    r1=right_bigger[r0]
    ans += ((r1-r0)*(i-l0) + (r0-i)*(l0-l1))*v
    left_bigger[r0]=l0
    right_bigger[l0]=r0
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = []
count = 0
for _ in range(N):
    s = list(input())
    s.sort()
    S.append(''.join(s))

for i in range(N):
    for j in range(i+1,N):
        if S[i] == S[j]:
            count += 1

print(count)

Fixed submission:
import math
N = int(input())
S = []
ans = 0
count = 1
for _ in range(N):
    s = list(input())
    s.sort()
    S.append(''.join(s))
S.sort()
S.append('a')

for i in range(N):
    if S[i] == S[i+1]:
        count += 1
    else:
        if count > 2:
            ans += math.factorial(count)//(math.factorial(count-2)*math.factorial(2))
        elif count == 2:
            ans += 1
        count =1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = []
count = 0
for _ in range(N):
    s = list(input())
    s.sort()
    S.append(s)

for i in range(N):
    for j in range(i+1,N):
        if S[i] == S[j]:
            count += 1

print(count)


Fixed submission:
import math
N = int(input())
S = []
ans = 0
count = 1
for _ in range(N):
    s = list(input())
    s.sort()
    S.append(''.join(s))
S.sort()
S.append('a')

for i in range(N):
    if S[i] == S[i+1]:
        count += 1
    else:
        if count > 2:
            ans += math.factorial(count)//(math.factorial(count-2)*math.factorial(2))
        elif count == 2:
            ans += 1
        count =1

print(ans)
Buggy python submission (verdict: Runtime Error):
N,L = list(map(int, input().split()))
l = []
l_abs = []
for i in range(N):
    l.append(L+i)
    l_abs.append(abs(L+i))


print(sum(l)-l[l.index(min(l_abs))])


Fixed submission:
N,L = list(map(int, input().split()))
l = []
l_abs = []
for i in range(N):
    l.append(L+i)
    l_abs.append(abs(L+i))


print(sum(l)-l[l_abs.index(min(l_abs))])

Buggy python submission (verdict: Runtime Error):
N,L = list(map(int, input().split()))
l = []
l_abs = []
for i in range(N):
    l.append(L+i)
    l_abs.append(abs(L+i))


print(sum(l)-l[l.index(min(l_abs))])


Fixed submission:
N,L = list(map(int, input().split()))
l = []
l_abs = []
for i in range(N):
    l.append(L+i)
    l_abs.append(abs(L+i))


print(sum(l)-l[l_abs.index(min(l_abs))])
Buggy python submission (verdict: Time Limit Exceeded):
N,Q = list(map(int, input().split()))
S = list(input())
l = []
r = []
for _ in range(Q):
    L,R = list(map(int, input().split()))
    l.append(L)
    r.append(R)
flag = False
ac = [0]*N

for j in range(N):
        if S[j] == 'A':
            flag = True
            continue
        if S[j] == 'C' and flag:
            ac[j] += 1
        flag = False


for i in range(Q):
    print(sum(ac[l[i]:r[i]]))


Fixed submission:
N,Q = list(map(int, input().split()))
S = list(input())
l = []
r = []
for _ in range(Q):
    L,R = list(map(int, input().split()))
    l.append(L)
    r.append(R)
flag = False
ac = [0]*N
count = 0

for j in range(N):
        if S[j] == 'A':
            flag = True
            ac[j] = count
            continue
        if S[j] == 'C' and flag:
            count += 1
        ac[j] = count
        flag = False


for i in range(Q):
    print(ac[r[i]-1]-ac[l[i]-1])

Buggy python submission (verdict: Time Limit Exceeded):
N,Q = list(map(int, input().split()))
S = list(input())
l = []
r = []
for _ in range(Q):
    L,R = list(map(int, input().split()))
    l.append(L)
    r.append(R)
flag = False


for i in range(Q):
    count = 0
    for j in range(l[i]-1,r[i]):
        if S[j] == 'A':
            flag = True
            continue
        if S[j] == 'C' and flag:
            count += 1
        flag = False
    print(count)


Fixed submission:
N,Q = list(map(int, input().split()))
S = list(input())
l = []
r = []
for _ in range(Q):
    L,R = list(map(int, input().split()))
    l.append(L)
    r.append(R)
flag = False
ac = [0]*N
count = 0

for j in range(N):
        if S[j] == 'A':
            flag = True
            ac[j] = count
            continue
        if S[j] == 'C' and flag:
            count += 1
        ac[j] = count
        flag = False


for i in range(Q):
    print(ac[r[i]-1]-ac[l[i]-1])
Buggy python submission (verdict: Time Limit Exceeded):

N,M = list(map(int, input().split()))
P = []
Y = []
for _ in range(M):
    p,y = list(map(int, input().split()))
    P.append(p)
    Y.append(y)
ans = [[0]*1 for _ in range(N+1)]
data = [[p,y,i] for p,y,i in zip(P,Y,range(1,M+1))]

data.sort(key=lambda x: x[1])

for i in range(M):
    ans[data[i][0]].append(data[i][2])

for j in range(1,M+1):
    a = P[j-1]
    b = ans[a].index(j)
    print(str(a*(10**6)+b).zfill(12))






Fixed submission:

N,M = list(map(int, input().split()))
P = []
Y = []
for _ in range(M):
    p,y = list(map(int, input().split()))
    P.append(p)
    Y.append(y)
count = [0]*(N+1)
ans = [0]*(M+1)
data = [[p,y,i] for p,y,i in zip(P,Y,range(1,M+1))]

data.sort(key=lambda x: x[1])

for i in range(M):
    count[data[i][0]] += 1
    ans[data[i][2]] = count[data[i][0]]


for j in range(1,M+1):
    a = P[j-1]
    b = ans[j]
    print(str(a*(10**6)+b).zfill(12))

Buggy python submission (verdict: Time Limit Exceeded):

N,M = list(map(int, input().split()))
P = []
Y = []
for _ in range(M):
    p,y = list(map(int, input().split()))
    P.append(p)
    Y.append(y)
ans = [[0]*1 for _ in range(N+1)]
data = [[p,y,i] for p,y,i in zip(P,Y,range(1,M+1))]

data.sort(key=lambda x: x[1])

for i in range(M):
    ans[data[i][0]].append(data[i][2])

for j in range(1,M+1):
    a = P[j-1]
    b = ans[a].index(j)
    print(str(a*(10**6)+b).zfill(12))






Fixed submission:

N,M = list(map(int, input().split()))
P = []
Y = []
for _ in range(M):
    p,y = list(map(int, input().split()))
    P.append(p)
    Y.append(y)
count = [0]*(N+1)
ans = [0]*(M+1)
data = [[p,y,i] for p,y,i in zip(P,Y,range(1,M+1))]

data.sort(key=lambda x: x[1])

for i in range(M):
    count[data[i][0]] += 1
    ans[data[i][2]] = count[data[i][0]]


for j in range(1,M+1):
    a = P[j-1]
    b = ans[j]
    print(str(a*(10**6)+b).zfill(12))
Buggy python submission (verdict: Time Limit Exceeded):
N,M = list(map(int, input().split()))

ans_max = M//N
ans = 0

for i in range(N,M+1):
    if M % i == 0:
        ans = int(M/i)
        break

print(ans)

Fixed submission:
N,M = list(map(int, input().split()))
divi = []

for i in range(1,int(M**0.5)+1):
    if M % i == 0:
        if i >= N:
            divi.append(i)
        if i != M//i:
            if M//i >= N:
                divi.append(M//i)

print(M//min(divi))

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

ans_max = M//N
ans = 0

for i in range(ans_max):
    if M % (ans_max-i) == 0:
        ans = ans_max-i
        break

print(ans)

Fixed submission:
N,M = list(map(int, input().split()))
divi = []

for i in range(1,int(M**0.5)+1):
    if M % i == 0:
        if i >= N:
            divi.append(i)
        if i != M//i:
            if M//i >= N:
                divi.append(M//i)

print(M//min(divi))
Buggy python submission (verdict: Runtime Error):
a,b = list(map(int, input().split()))

if (a*b)%2 == 0:
    print(Even)

else:
    print(Odd)

Fixed submission:
a,b = list(map(int, input().split()))

if (a*b)%2 == 0:
    print("Even")

else:
    print("Odd")
Buggy python submission (verdict: Runtime Error):
n = int(input())
s = 0

if int(n/100) == 1:
    s += 1
if n%100 => 10:
    s += 1
if n%10 == 1:
    s += 1

print(s)

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

if int(n/100) == 1:
    s += 1
if n%100 >= 10:
    s += 1
if n%10 == 1:
    s += 1

print(s)

Buggy python submission (verdict: Runtime Error):
n = int(input())
s = 0

if int(n/100) == 1:
    s ++
if n%100 => 10:
    s ++
if n%10 == 1:
    s ++

print(s)

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

if int(n/100) == 1:
    s += 1
if n%100 >= 10:
    s += 1
if n%10 == 1:
    s += 1

print(s)
Buggy python submission (verdict: Time Limit Exceeded):
class SegTree:
    X_unit = 1 << 30
    X_f = min

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)
      
N, Q=map(int,input().split())
S1=SegTree(N)
S2=SegTree(N)

S1.build([N]*N)
S2.build([N]*N)
ans=(N-2)**2

for i in range(Q):
  j, x=map(int,input().split())
  if j==1:
    l=S2.fold(x-1,N)
    ans-=l-2
    S1.set_val(l-1,min(x,S1.X[l-1+N]))
  if j==2:
    l=S1.fold(x-1,N)
    ans-=l-2
    S2.set_val(l-1,min(x,S2.X[l-1+N]))
    
print(ans)

Fixed submission:
class SegTree:
    X_unit = 1 << 30
    X_f = min

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)
      
N, Q=map(int,input().split())
S1=SegTree(N)
S2=SegTree(N)

S1.build([N]*N)
S2.build([N]*N)
ans=(N-2)**2

for i in range(Q):
  j, x=map(int,input().split())
  if j==1:
    l=S2.fold(x-1,N)
    ans-=l-2
    S1.set_val(l-1,min(x,S1.X[l-1+N]))
  if j==2:
    l=S1.fold(x-1,N)
    ans-=l-2
    S2.set_val(l-1,min(x,S2.X[l-1+N]))
    
print(ans)