Harryxun/stf_run huggingface dataset:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

S = input()
Xans,Yans = inpl()

Xmove = []
Ymove = []

flag = True
tmp = 0
for s in S+'T':
	if s == 'F':
		tmp += 1
	else:
		if flag:
			Xmove.append(tmp)
		else:
			Ymove.append(tmp)
		tmp = 0
		flag = not flag

if len(Xmove) == 0:
	if Xans != 0:
		print('No')
		sys.exit()
else:
	Xsum = sum(Xmove)
	if (Xsum+Xans)%2 == 1:
		print('No')
		sys.exit()
	else:
		Xpos = (Xsum+Xans)//2
		dp = [0]*(Xpos+1)
		dp[0] = 1
		for x in Xmove:
			for i in range(Xpos,x-1,-1):
				dp[i] = dp[i-x]
			if dp[-1] == 1:
				break
		else:
			print('No')
			sys.exit()


if len(Ymove) == 0:
	if Yans != 0:
		print('No')
		sys.exit()
else:
	Ysum = sum(Ymove)
	if (Ysum+Yans)%2 == 1:
		print('No')
		sys.exit()
	else:
		Ypos = (Ysum+Yans)//2
		dp = [0]*(Ypos+1)
		dp[0] = 1
		for y in Ymove:
			for i in range(Ypos,y-1,-1):
				dp[i] = dp[i-y]

			if dp[-1] == 1:
				break
		else:
			print('No')
			sys.exit()

print('Yes')


### FIXED CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

S = input()
Xans,Yans = inpl()

Xmove = []
Ymove = []

First = True
flag = True
tmp = 0
for s in S+'T':
	if s == 'F':
		tmp += 1
	else:
		if First:
			Xans -= tmp
			First = False
		else:
			if flag:
				Xmove.append(tmp)
			else:
				Ymove.append(tmp)
		tmp = 0
		flag = not flag


Xsum = sum(Xmove)
if (Xsum+Xans)%2 == 1:
	print('No')
	sys.exit()
elif abs(Xans) > Xsum:
	print('No')
	sys.exit()
elif len(Xmove) == 0:
	if Xans != 0:
		print('No')
		sys.exit()
else:
	Xpos = (Xsum+Xans)//2
	dp = [0]*(Xpos+1)
	dp[0] = 1
	for x in Xmove:
		for i in range(Xpos,x-1,-1):
			dp[i] = dp[i-x]
		if dp[-1] == 1:
			break
	else:
		print('No')
		sys.exit()

Ysum = sum(Ymove)
if (Ysum+Yans)%2 == 1:
	print('No')
	sys.exit()
elif abs(Yans) > Ysum:
	print('No')
	sys.exit()
elif len(Ymove) == 0:
	if Yans != 0:
		print('No')
		sys.exit()
else:
	Ypos = (Ysum+Yans)//2
	dp = [0]*(Ypos+1)
	dp[0] = 1
	for y in Ymove:
		for i in range(Ypos,y-1,-1):
			dp[i] = dp[i-y]
		if dp[-1] == 1:
			break
	else:
		print('No')
		sys.exit()

print('Yes')
a = int(input())
b = int(input())
if (2 % a * b == 0) print("Even")
if (2 % a * b != 0) print("0dd")
    

### FIXED CODE ###

a, b = map(int, input().split())
if a * b % 2 == 0:print("Even")
if a * b % 2 != 0:print("Odd")
N, T = map(int, input().split())
cost = 2_000_000
TLE_flg = True
for _ in range(N):
    c, t = map(int, input().split())
    if t <= T:
        cost = min(cost, c)
        TLE_flg = False
print('TLE' if TLE_flg else cost)


### FIXED CODE ###

N, T = map(int, input().split())
c_t = [list(map(int, input().split())) for _ in range(N)]
cost = 2000000
TLE_flg = True
for i in range(N):
    if c_t[i][1] <= T:
        cost = min(cost, c_t[i][0])
        TLE_flg = False
print('TLE' if TLE_flg else cost)
import math
import collections
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    n = int(input())
    maxv = n*(n-1)//2
    a = [list(map(lambda x:x-1, list(map(int, input().split()))))for i in range(n)]


    # 試合を頂点とする(ex 1-2,2-4 : i < j)
    v = 0  # 頂点数
    # 頂点にIDをふる
    Id = [[-1 for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            if i < j:
                Id[i][j] = v
                Id[j][i] = v
                v += 1

    # 頂点間の辺を貼る
    e = [[] for i in range(maxv)]
    for i in range(n):
        # a[i][j]にIDを代入する Id[1][3]=1 => a[1][3] = a[3][1] = 1
        for j in range(n - 1):
            a[i][j] = Id[i][a[i][j]]

        # 辺をはる
        for j in range(n - 2):
            e[a[i][j]].append(a[i][j+1])


    calculated = [False for i in range(maxv)]
    dp = [-1 for i in range(maxv)]
    def dfs(v):
        if dp[v] != -1:
            if not calculated[v]:
                return -1
            return dp[v]
        dp[v] = 1
        for u in e[v]:
            ret = dfs(u)
            if ret == -1:
                return -1
            dp[v] = max(dp[v], ret + 1)
        calculated[v] = True　#帰りがけ
        return dp[v]
    

    #トポロジカルソート
    ans = 0
    for i in range(v):
        ret = dfs(i)
        if ret == -1:  # サイクル検知
            print(-1)
            exit()
        ans = max(ans, ret)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
import collections
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    n = int(input())
    maxv = n*(n-1)//2
    a = [list(map(int, input().split())) for i in range(n)]
    for i in range(n):
        for j in range(n-1):
            a[i][j] -= 1
    v = 0
    Id = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            if i < j:
                Id[i][j] = v
                v += 1

    def toId(i, j):
        if i > j:
            i, j = j, i
        return Id[i][j]

    to = [[] for i in range(maxv)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] = toId(i, a[i][j])
        for j in range(n - 2):
            to[a[i][j+1]].append(a[i][j])

    visited = [False for i in range(maxv)]
    calculated = [False for i in range(maxv)]
    dp = [0 for i in range(maxv)]

    def dfs(v):
        if visited[v]:
            if not calculated[v]:
                return -1
            return dp[v]
        visited[v] = True
        dp[v] = 1
        for u in to[v]:
            ret = dfs(u)
            if ret == -1:
                return -1
            dp[v] = max(dp[v], ret + 1)
        calculated[v] = True
        return dp[v]

    ans = 0
    for i in range(v):
        ret = dfs(i)
        if ret == -1:  # detected cycle
            print(-1)
            exit()
        ans = max(ans, ret)
    print(ans)


if __name__ == '__main__':
    main()
n = int(input())
l = list(map(int,input().split()))
a = 10**9
ans = 0
for i in range(n):

    if l[i] <= a:
        ans += 1
         a = l[i]
print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
a = 10**9
ans = 0
for i in range(n):
    if p[i]<=a:
        ans+= 1
        a = p[i]
print(ans)
n = int(input())
a=list(map(int, input().split()))
count = 0
success = True
while True:
    for i, ele in enumerate(a):
        if ele % 2 == 0:
            a[i] = ele / 2
        else:
            success = False
    if not success:
        break
    count += 1
print(count)

### FIXED CODE ###

a = input()
print(int(a[0])+int(a[1])+int(a[2]))
n,m=map(int,input().split())
a=list(map(int,input().split()))
import fractions
lmc=a[0]
for i in range(1,n):
    lmc=lmc*a[i]//fractions.gcd(lmc,a[i])
    if lmc>m:
        print("0")
        exit()
if i in range(n):
   if (lmc//a[i])%2==0:
      print("0")
      exit()
if (m%lmc)<lmc//2:
    print((m//lmc))
else:
    print((m//lmc)+1)

### FIXED CODE ###

n,k=map(int,input().split())
g=500*n
if g>=k:
    print("Yes")
else:
    print("No")
s = input()
print(''.join([s[i] if i%2 == 1 for i in range(len(s))]))

### FIXED CODE ###

s = input()
print(''.join([s[i] for i in range(len(s)) if i%2 == 0]))
a,b=[int(i) for i in input().split()]

h = 0
i = 0
while h < a and i < 1000:
    i += 1
    h += i

if i > 999
    print(h-b)
else:
    print(h-a)

### FIXED CODE ###

a,b=[int(i) for i in input().split()]

d = b - a

h = 0
for i in range(1,d):
    h += i

print(h-a)
from collections import deque

n = int(input())
list = [list(map(int,input().split())) for i in range(n)]

p = deque()

for i in list:
  p.append([i[0] - i[1],i[0] + i[1]])
  
p = sorted(p,key = lambda x: x[1])

ex = []
ex.append(p.pop(left))




for i in range(len(p)):
  if(ex[-1][1] <= p[0][0]):
    ex.append(p.pop(left))
  else:
    p.pop(left)

print(len(ex))

### FIXED CODE ###

from collections import deque

n = int(input())
list = [list(map(int,input().split())) for i in range(n)]

p = deque()

for i in list:
  p.append([i[0] - i[1],i[0] + i[1]])
  
p = sorted(p,key = lambda x: x[1])

ex = []
ex.append(p.pop(0))




for i in range(len(p)):
  if(ex[-1][1] <= p[0][0]):
    ex.append(p.pop(0))
  else:
    p.pop(0)

print(len(ex))
n=int(input())
a=[int(input()) for i in range(n)]
cost=abs(a[n-1])
a.append(0)
a.insert(0,0)
for i in range(n):
    tmp=abs(a[i]-a[i+1])
    cost+=tmp
for i in range(n):
    ans=cost+abs(a[i]-a[i+2])-abs(a[i+1]-a[i])-abs(a[i+1]-a[i+2])
    print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
cost=abs(a[n-1])
a.append(0)
a.insert(0,0)
for i in range(n):
    tmp=abs(a[i]-a[i+1])
    cost+=tmp
for i in range(n):
    ans=cost+abs(a[i]-a[i+2])-abs(a[i+1]-a[i])-abs(a[i+1]-a[i+2])
    print(ans)
a = input()
print(a[2])
if a[2] == a[3] && a[4] == a[5]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a = input()
if a[2] == a[3] and a[4] == a[5]:
    print("Yes")
else:
    print("No")
N,Q=map(int,input().split())
S=input()
t=[0]*N
for i in range(N-1):
    t[i+1]=t[i]+(1 if S[i:i+2]=='AC' else 0)
for i in range(Q):
    l,r=map(int,input().split())
    print(t[r-1]-t[l-1])

### FIXED CODE ###

b=input()
if b=='A':
    print('T')
elif b=='T':
    print('A')
elif b=='C':
    print('G')
else:
    print('C')
import sys
sys.setrecursionlimit(1000000000)
Books,Cost,X=None,None,None
DP={}

def getUnderstanding(prev,curr):
    global Books
    L=[]
    for i in range(len(prev)):
        L.append(prev[i]+Books[curr][i])
    return L
def isUnderstandingReached(prev):
    global X
    for u in prev:
        if u<X:
            return False
    return True

def F(curr,prev):
    global Books,Cost,X,DP
    if (curr,tuple(prev)) in DP:
        return DP[(curr,prev)]
    if isUnderstandingReached(prev):
        return 0
    if curr==len(Books):
        return float('inf')
    DP[(curr,tuple(prev))]=min(Cost[curr]+F(curr+1,getUnderstanding(prev,curr)),F(curr+1,prev))
    return DP[(curr,tuple(prev))]

N,M,X=map(int,input().strip().split())
Books=[]
Cost=[]
for i in range(N):
    L=list(map(int,input().strip().split()))
    Books.append(L[1:])
    Cost.append(L[0])
print(F(0,[0]*len(Books[0])))

### FIXED CODE ###

Books,Cost,X=None,None,None
DP={}

def getUnderstanding(prev,curr):
    global Books
    L=[]
    for i in range(len(prev)):
        L.append(prev[i]+Books[curr][i])
    return L
def isUnderstandingReached(prev):
    global X
    for u in prev:
        if u<X:
            return False
    return True

def F(curr,prev):
    global Books,Cost,X,DP
    #if (curr,tuple(prev)) in DP:
    #    return DP[(curr,prev)]
    if isUnderstandingReached(prev):
        return 0
    if curr==len(Books):
        return float('inf')
    DP[(curr,tuple(prev))]=min(Cost[curr]+F(curr+1,getUnderstanding(prev,curr)),F(curr+1,prev))
    return DP[(curr,tuple(prev))]

N,M,X=map(int,input().strip().split())
Books=[]
Cost=[]
for i in range(N):
    L=list(map(int,input().strip().split()))
    Books.append(L[1:])
    Cost.append(L[0])
res=F(0,[0]*len(Books[0]))
if res==float('inf'):
    print(-1)
else:
    print(res)
def calcH(x, cx, y, cy, h):
    return abs(x-cx)+abs(y-cy)+h
n = int(input())
xyh = [list(map(int, input().split())) for i in range(n)]
Hmax = 10**9
for i in range(101):
    for j in range(101):
        k = 0
        flag = True
        for x, y, h in xyh:
            H_ = calcH(x, i, y, j, h)
            if h == 0:
                flag = False
            if k > 0:
                if H_ != H and flag:
                    flag = False
                    break
                elif H_ != H:
                    H = H_
                    flag = True
                else:
                    flag = True
                    continue
            else:
                H = H_
                flag = True
            k += 1
        if flag == False or H > Hmax:
            continue
        else:
            Cx = i
            Cy = j
            Ch = H
            break
print(Cx, Cy, Ch)

### FIXED CODE ###

def calcCh(cx, cy, x, y, h):
    return abs(x-cx)+abs(y-cy)+h
def calcH(cx, cy, ch, x, y, h):
    return max(ch - calcCh(cx, cy, x, y, 0), 0)
n = int(input())
xyh = [list(map(int, input().split())) for i in range(n)]
xyh = sorted(xyh, key = lambda x: x[2])[::-1]
lst = [[x, y] for x in range(101) for y in range(101)]
for Cx, Cy in lst:
    Ch = calcCh(Cx, Cy, *xyh[0])
    if all(xyh[i][2] == calcH(Cx, Cy, Ch, *xyh[i]) for i in range(n)):
        break
print(Cx, Cy, Ch)
n,m = map(int,raw_input().strip().split(' '))
graph = [[] for i in range(n)]
for i in range(m):
    s,t = map(int,raw_input().strip().split(' '))
    graph[s].append(t)
    graph[t].append(s)
 
color = {}
c = 0
for i in range(n):
    if not i in color:
        que = [i]
        color[i] = c
        if len(que) > 0:
         for j in range (m):
            u = que[0]
            for v in graph[u]:
                if not v in color:
                    color[v] = c
                    que.append(v)
            del que[0]
        c += 1

### FIXED CODE ###

n,m = map(int,raw_input().strip().split(' '))
graph = [[] for i in range(n)]
for i in range(m):
    s,t = map(int,raw_input().strip().split(' '))
    graph[s].append(t)
    graph[t].append(s)
color = {}
c = 0
for i in range(n):
    if not i in color:
        que = [i]
        color[i] = c
        while len(que) > 0:
            u = que[0]
            for v in graph[u]:
                if not v in color:
                    color[v] = c
                    que.append(v)
            del que[0]
        c += 1
q = int(raw_input())
for i in range(q):
   s,t = map(int,raw_input().strip().split(' '))
   if color[s] == color[t]:
     print 'yes'
   else:
     print 'no'
A,P = int(input())
N = 3*A+P
print(N//2)

### FIXED CODE ###

A,P = map(int,input().split())
N = 3*A+P
print(N//2)
n = int(input())
h = list(map(int, input().split()))
l = []
cnt = 0
for i in reversed(range(1, n)):
  if h[i]<=h[i-1]:
    cnt += 1
  else:
    l.append(cnt)
    cnt = 0
ans = max(l)
print(ans)

### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
l = []
cnt = 0
ans = 0
for i in reversed(range(1, n)):
  if h[i]<=h[i-1]:
    cnt += 1
  else:
    l.append(cnt)
    cnt = 0
  if i==1:
    l.append(cnt)

if len(l)!=0: ans = max(l)
print(ans)
a = []
i = 0
while true:
  n = input()
  if n == 0:
    break
  a.append(n)
  print('Case {0}: {1}'.format(i,n))

### FIXED CODE ###

i = 1
while True:
  n = input()
  if n == "0":
    break
  print("Case {0}: {1}".format(i,n))
  i += 1
if int(input())%2 == 1 and int(input())%2 == 1:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a, b = map(int, input().split())
if a%2 == 1 and b%2 == 1:
  print("Yes")
else:
  print("No")
def main():
  A,B = input.split()
  A = int(A)
  B = round(float(B)*100)
 
  res = (A*B)//100
  print(res)
 
main()

### FIXED CODE ###

A,B = input().split()
A = int(A)
B = round(float(B)*100)

res = (A*B)//100
print(res)
n = int(input())
card = []

for i in range(n):
    x,y,h = [int(i) for i in input().split()]
    card.append([x,y,h])


 
def check(cx,cy):
    needH = -1
    for i in range(n):
        x,y,h = card[i]

        if h>0:
            global H = abs(x-cx)+abs(y-cy)+h
            if needH == -1:
                needH = H
            else:
                if needH != H:
                    return False
    
    for i in range(n):
        x,y,h = card[i]

        if h==0:
            dist = abs(x-cx)+abs(y-cy)
            if H > dist:
                return False
    else:
        return True

    
for i in range(101):
    for j in range(101):
        if check(i,j):

            print("{} {} {}".format(i,j,H))


### FIXED CODE ###

n = int(input())
card = []

for i in range(n):
    x,y,h = [int(i) for i in input().split()]
    card.append([x,y,h])


 
def check(cx,cy):
    needH = -1
    for i in range(n):
        x,y,h = card[i]

        if h>0:
            global H
            H = abs(x-cx)+abs(y-cy)+h
            if needH == -1:
                needH = H
            else:
                if needH != H:
                    return False
    
    for i in range(n):
        x,y,h = card[i]

        if h==0:
            dist = abs(x-cx)+abs(y-cy)
            if H > dist:
                return False
    else:
        return True

    
for i in range(101):
    for j in range(101):
        if check(i,j):

            print("{} {} {}".format(i,j,H))
x=map(raw_input().split())

for i in reversed(range(len(x)):
print x[i]

### FIXED CODE ###

n = int(raw_input())
a = map(int,raw_input().split())
a.reverse()
for i in a:
    print i,
s = input()
a = 0
for char in s:
	if char != 'x':
    	a++
print(700+a*100)

### FIXED CODE ###

s = input()
a = 0
for i in range(3):
	if s[i:i+1] != 'x':
		a += 100
print(700 + a)
from bisect import bisect_right


def main():
    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    for i in range(1, n):
        a[i] += a[i - 1]
    for i in range(1, m):
        b[i] += b[i - 1]
    answer = 0
    if a[-1] + b[-1] <= k:
        print(n + m)
    else:
        for i in range(n):
            l = bisect_right(b, k - a[i])
            if l == 0 or (l == m and b[l] + a[i] != k):
                continue
            answer = max(answer, i + 1 + l)
        print(answer)


if __name__ == '__main__':
    main()



### FIXED CODE ###

from bisect import bisect_right


def main():
    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    answer = 0
    is_changed = False
    if a[0] <= k or b[0] <= k:
        answer = 1
    elif a[0] + b[0] <= k:
        answer = 2
    for i in range(1, n):
        a[i] += a[i - 1]
        if k < a[i] and not is_changed:
            answer = i
            is_changed = True
    if a[-1] <= k:
        answer = n
    is_changed = False
    for i in range(1, m):
        b[i] += b[i - 1]
        if k < b[i] and not is_changed:
            answer = max(answer, i)
            is_changed = True
    if b[-1] <= k:
        answer = max(answer, m)
    if a[-1] + b[-1] <= k:
        answer = n + m
    elif all(k < x for x in [a[0], b[0], a[0] + b[0]]):
        answer = 0
    else:
        for i in range(n):
            l = bisect_right(b, k - a[i])
            if l == 0 or (l == m and b[l - 1] + a[i] > k):
                continue
            answer = max(answer, i + 1 + l)
    print(answer)


if __name__ == '__main__':
    main()
r1,c1,r2,c2=map(int,input().split())

#O(10**12) orz

from scipy.misc import comb
mod=10**9+7
tret=0
for i in range(r1,r2+1):
    for j in range(c1,c2+1):
        # print(i,j)
        tret+=comb(i+j,i,exact=True)
        tret%=mod
        
print(tret)
        

### FIXED CODE ###

r1,c1,r2,c2=map(int,input().split())

mod = 10**9+7
MAX_N = 3*10**6

fact = [1]
fact_inv = [0]*(MAX_N+4)
for i in range(MAX_N+3):
    fact.append(fact[-1]*(i+1)%mod)

fact_inv[-1] = pow(fact[-1],mod-2,mod)
for i in range(MAX_N+2,-1,-1):
    fact_inv[i] = fact_inv[i+1]*(i+1)%mod

def comb(n,k,mod):
    if n<k:return 0
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod

ans=0
ans+=comb(c1+r1,r1,mod)
ans%=mod
ans-=comb(c1+r2+1,r2+1,mod)
ans%=mod
ans-=comb(c2+r1+1,r1,mod)
ans%=mod
ans+=comb(c2+r2+2,r2+1,mod)
ans%=mod

print(ans)
N,K =map(int,input().split())
count=0
for a in range(K,N+2):
  count+=0.5*(N-a+1)*(N-a+2)-0.5*a*(a-1)+1
print(count%(10**9+7))
  


### FIXED CODE ###

import math
a=int(input())
print(2* math.pi *a)
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, q = LI()
ans = (n-2) * (n-2)
min_x_list = [-n]
min_x_idx = [0]
min_y_list = [-n]
min_y_idx = [0]
idx = 1
for _ in range(q):
    a, b = LI()
    min_x = -min_x_list[-1]
    min_y = -min_y_list[-1]
    if a == 1:
        if min_x > b:
            min_x_list.append(-b)
            min_x_idx.append(idx)
            idx += 1
            ans -= min_y - 2
        else:
            r = br(min_x_list, -b)
            i = min_x_idx[r]
            r = br(min_y_idx, i)
            ans -= -min_y_list[r-1] - 2

    elif a == 2:
        if min_y > b:
            min_y_list.append(-b)
            min_y_idx.append(idx)
            idx += 1
            ans -= min_x - 2
        else:
            r = br(min_y_list, -b)
            i = min_y_idx[r]
            r = br(min_y_idx, i)
            ans -= -min_x_list[r-1] - 2
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, q = LI()
ans = (n-2) * (n-2)
min_x_list = [-n]
min_x_idx = [0]
min_y_list = [-n]
min_y_idx = [0]
idx = 1
for _ in range(q):
    a, b = LI()
    min_x = -min_x_list[-1]
    min_y = -min_y_list[-1]
    if a == 1:
        if min_x > b:
            min_x_list.append(-b)
            min_x_idx.append(idx)
            idx += 1
            ans -= min_y - 2
        else:
            r = br(min_x_list, -b)
            i = min_x_idx[r]
            r = br(min_y_idx, i)
            ans -= -min_y_list[r-1] - 2

    elif a == 2:
        if min_y > b:
            min_y_list.append(-b)
            min_y_idx.append(idx)
            idx += 1
            ans -= min_x - 2
        else:
            r = br(min_y_list, -b)
            i = min_y_idx[r]
            r = br(min_x_idx, i)
            ans -= -min_x_list[r-1] - 2
print(ans)