Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N,Q = map(int,input().split(" "))
s=list(input())
ju = []
for i in range(Q):
    ju.append(input().split(" "))

mem = [0] * N
def isdead(xp):
    if mem[xp] == 1:
        return True
    elif mem[xp] == 2:
        return False
    oxp = xp
    for i in range(Q):
        com = ju[i]
        if s[xp] == com[0]:
            if com[1] == "L":
                xp -= 1
            else:
                xp += 1
        if xp < 0 or xp > N-1:
            mem[oxp] = 1
            return True
    mem[oxp] = 2
    return False

def mid(x1,x2):
    return int((x1+x2)/2)

p1 = 0
p3 = N-1
p2 = int((p1+p3) / 2)
ap = -1
#left
while p1 != p2:
    if isdead(p2):
        p2,p3 = int((p1+p2)/2),p2
    else:
        ap = p2
        break
#right
if ap == -1:
    while p2 != p3:
        if isdead(p2):
            p2,p1 = int((p2+p3)/2),p2
        else:
            ap = p2
            break
if ap == -1:
    print(0)
    exit()

#left
p1 = 0
p3 = ap
p2 = mid(p1,p3)
while p3 - p1 != 1:
    if isdead(p2):
        p1,p2 = p2,mid(p2,p3)
    else:
        p2,p3 = mid(p1,p2),p2
if isdead(p1):
    p = p3
else:
    p = p1
#right
p1 = ap
p3 = N-1
p2 = mid(p1,p3)
while p3 - p1 != 1:
    if isdead(p2):
        p2,p3 = mid(p1,p2),p2
    else:
        p1,p2 = p2,mid(p2,p3)
if isdead(p3):
    q = p1
else:
    q = p3


if p > q:
    print(0)
else:
    print(q-p+1)


### FIXED CODE ###

input = raw_input

N,Q = map(int,input().split(" "))
s=list(input())
ju = []
for i in range(Q):
    ju.append(input().split(" "))

def isdeadleft(xp):
    oxp = xp
    for i in range(Q):
        com = ju[i]
        if s[xp] == com[0]:
            if com[1] == "L":
                xp -= 1
            else:
                xp += 1
        if xp < 0:
            return True
        if xp > N-1:
            xp = N-1
    return False

def isdeadright(xp):
    oxp = xp
    for i in range(Q):
        com = ju[i]
        if s[xp] == com[0]:
            if com[1] == "L":
                xp -= 1
            else:
                xp += 1
        if xp < 0:
            xp = 0
        if xp > N-1:
            return True
    return False

def mid(x1,x2):
    return int((x1+x2)/2)

if isdeadleft(N-1) or isdeadright(0):
    print(0)
    exit()

#left
p1 = 0
p3 = N-1
p2 = mid(p1,p3)
while p3 - p1 != 1:
    if isdeadleft(p2):
        p1,p2 = p2,mid(p2,p3)
    else:
        p2,p3 = mid(p1,p2),p2
if isdeadleft(p1):
    p = p3
else:
    p = p1
#right
p1 = 0
p3 = N-1
p2 = mid(p1,p3)
while p3 - p1 != 1:
    if isdeadright(p2):
        p2,p3 = mid(p1,p2),p2
    else:
        p1,p2 = p2,mid(p2,p3)
if isdeadright(p3):
    q = p1
else:
    q = p3

if p > q:
    print(0)
else:
    print(q-p+1)
### BUGGY CODE ###

from collections import Counter

N = int(input())
words = [Counter(input()) for _ in range(N)]
ans = 0
def get_unique_list(seq):
    seen = []
    return [seq.count(x) for x in seq if x not in seen and not seen.append(x) and seq.count(x) != 1]

# counters_counts = [words.count(x) for x in get_unique_list(words) if words.count(x) > 1]

for count in get_unique_list(words):
    ans += int((count * (count-1)) / 2)
print(ans)

### FIXED CODE ###

from collections import Counter

class hashabledict(dict):
    def __hash__(self):
        return hash(tuple(sorted(self.items())))

N = int(input())
words = [hashabledict(dict(Counter(input()))) for _ in range(N)]
ans = 0
counter_hash = {}
for counter in words:
    if counter not in counter_hash.keys():
        counter_hash[counter] = 1
    else:
        counter_hash[counter] += 1
 
for count in counter_hash.values():
    ans += int((count * (count-1)) / 2)
print(ans)
### BUGGY CODE ###

K,S=map(int,input().split())
ans=0
for i in range(K+1):
    for j in range(K+1):
        for l in range(K+1):
            if i+j+l==S:
                ans+=1
print(ans)

### FIXED CODE ###

K,S=map(int,input().split())
ans=0
for i in range(K+1):
    for j in range(K+1):
        if 0<=S-i-j<=K:
          ans+=1
print(ans)
### BUGGY CODE ###

S = input()
n = len(S)
mod = 10**9+7
dp = [[0 for _ in range(13)] for _ in range(n+1)]
dp[0][0] = 1
mul = 1
for i in range(n):
    x = S[-(i+1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i+1][(k*mul+j)%13] += dp[i][j]
                dp[i+1][(k*mul+j)%13] %= mod
    else:
        k = int(x)
        for j in range(13):
            dp[i+1][(k*10**i+j)%13] += dp[i][j]
            dp[i+1][(k*10**i+j)%13] %= mod
    mul = mul*10%13
print (dp[n][5])

### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

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

### FIXED CODE ###

from collections import deque
S = list(input())
S = deque(S)
Q = int(input())
c = 0
for _ in range(Q):
    q = list(input().split())
    if int(q[0]) == 1:
        if c == 0:
            c = 1
        else:
            c = 0
    else:
        if c == 0:
            if int(q[1]) == 1:
                S.appendleft(q[2])
            else:
                S.append(q[2])
        else:
            if int(q[1]) == 2:
                S.appendleft(q[2])
            else:
                S.append(q[2])
S = list(S)
if c == 0:
    print("".join(S))
else:
    S = S[::-1]
    print("".join(S))
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]
for i in range(n):
    s[i] = sorted(s[i])
count = 0
l = [s[0]]
for i in range(1,n):
    exis = False
    for j in range(len(l)):
        if s[i] == l[j]:
            count += 1
    l.append(s[i])
print(count)

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]
for i in range(n):
    s[i] = sorted(s[i])
s.sort()
result = 0
count = 1
for i in range(n-1):
    if s[i] == s[i+1]:
        count += 1
    else:
        result += (count*(count-1))//2
        count = 1
result += count*(count-1)//2
print(result)
### BUGGY CODE ###

import sys
import queue
input = sys.stdin.readline

def main():
    N, M, P = map(int, input().split())
    g = [[] for _ in range(N+1)]
    g2 = [[] for _ in range(N+1)]
    data = [list(map(int, input().split())) for _ in range(M)]
    for a, b, _ in data:
        g2[b].append(a)
        g[a].append(b)

    visit = [False]*(N+1)
    visit2 = [False]*(N+1)

    q = queue.Queue()
    q.put(1)
    visit[1] = True
    while (not q.empty()):
        now = q.get()
        for next in g[now]:
            if not visit[next]:
                visit[next] = True
                q.put(next)

    q = queue.Queue()
    q.put(N)
    visit2[N] = True
    while (not q.empty()):
        now = q.get()
        for next in g2[now]:
            if not visit2[next]:
                visit2[next] = True
                q.put(next)

    for i in range(1, N+1):
        visit[i] = visit[i] and visit2[i]


    INF = 1000000001
    d = [(-1)*INF for i in range(N+1)]
    d[1] = 0

    for i in range(N):
        d_N = [d[i] for i in range(1, N+1) if visit[i]]
        for j in range(M):
            a = data[j][0]
            b = data[j][1]
            c = data[j][2]
            d[b] = max(d[b], d[a]+c-P)
        if i == N-1:
            if d_N != [d[i] for i in range(1, N+1) if visit[i]]:
                ans = -1

            else:
                ans = d[N]

    if ans == -1:
        print(-1)
    else:
        print(max(0, ans))

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import queue
input = sys.stdin.readline

def main():
    N, M, P = map(int, input().split())
    g = [[] for _ in range(N+1)]
    g2 = [[] for _ in range(N+1)]
    data = [list(map(int, input().split())) for _ in range(M)]
    for a, b, _ in data:
        g2[b].append(a)
        g[a].append(b)

    visit = [False]*(N+1)
    visit2 = [False]*(N+1)

    q = queue.Queue()
    q.put(1)
    visit[1] = True
    while (not q.empty()):
        now = q.get()
        for next in g[now]:
            if not visit[next]:
                visit[next] = True
                q.put(next)

    q = queue.Queue()
    q.put(N)
    visit2[N] = True
    while (not q.empty()):
        now = q.get()
        for next in g2[now]:
            if not visit2[next]:
                visit2[next] = True
                q.put(next)

    for i in range(1, N+1):
        visit[i] = visit[i] and visit2[i]


    INF = 1000000001
    d = [(-1)*INF for i in range(N+1)]
    d[1] = 0

    for i in range(N):
        d_N = [d[i] for i in range(1, N+1) if visit[i]]
        for j in range(M):
            a = data[j][0]
            b = data[j][1]
            c = data[j][2]
            d[b] = max(d[b], d[a]+c-P)
        if i == N-1:
            if d_N != [d[i] for i in range(1, N+1) if visit[i]]:
                ans = -1

            else:
                ans = d[N]

    if ans == -1:
        print(-1)
    else:
        print(max(0, ans))

if __name__ == "__main__":
    main()
### BUGGY CODE ###

def main():
  A, B, K = map(int, input().split())
  
  for _ in range(K):
    if A >= 1:
      A -= 1
      continue
    elif B >= 1:
      B-= 1
      continue
  
  print(A, B)
  
  
  
main()

### FIXED CODE ###

def main():
  A, B, K = map(int, input().split())
  
  if K <= A:
    print(A - K, B)
  elif K > A and B >= K - A:
    print(0, B - (K - A))
  elif K > A and B < (K - A):
    print(0, 0)
  
  
  
main()
### BUGGY CODE ###

R,G,B,N = map(int,input().split())

rmax = N//R
gmax = N//G
bmax = N//B

cnt = 0

for i in range(rmax+1):
    for j in range(gmax+1):
        if R*i + G*j > N:
            continue
        if ((N-R*i-G*j)%B == 0) and ((N-R*i-G*j)//B <= bmax):
            cnt += 1
print(cnt)

### FIXED CODE ###

R,G,B,N = map(int,input().split())
A = [R,G,B]
A.sort()
R = A[2]
G = A[1]
B = A[0]
rmax = N//R
gmax = N//G
bmax = N//B

cnt = 0

if R == 1:
    print((N+1)*(N+2)//2)
    exit()

for i in range(rmax+1):
    for j in range(gmax+1):
        if R*i + G*j > N:
            continue
        if ((N-R*i-G*j)%B == 0) and ((N-R*i-G*j)//B <= bmax):
            cnt += 1
print(cnt)
### BUGGY CODE ###

N, Q = map(int, input().split())
T = [[0, [], []] for _ in range(N+1)] #counter, parents, children
E = sorted([list(map(int, input().split())) for _ in range(N-1)], key=lambda x:x[0])
for e in E:
  p, c = e
  T[c][1] += T[p][1]
  T[c][1].append(p)
  for q in T[c][1]:
    T[q][2].append(c)
for _ in range(Q):
  p, x = map(int, input().split())
  T[p][0] += x
  for c in T[p][2]:
    T[c][0] += x
ans_s = ""
for t in T[1:]:
  ans_s += "%d "%t[0]
print(ans_s)



### FIXED CODE ###

import sys
sys.setrecursionlimit(3*(10**5))


N, Q = map(int, input().split())
T = [[0, []] for _ in range(N+1)] #counter, nearest-children
E = [list(map(int, input().split())) for _ in range(N-1)]
PX = [list(map(int, input().split())) for _ in range(Q)]
for e in E:
  T[e[0]][1].append(e[1])
for px in PX:
  T[px[0]][0] += px[1]
for t in T:
  for c in t[1]:
    T[c][0] += t[0]
ans_s = ""
for t in T[1:]:
  ans_s += "%d "%t[0]
print(ans_s)
### BUGGY CODE ###

a,b,x=map(int,input().split())
c=0
for i in range(a,b+1):
     if i%x==0:
          c+=1
print(c)

### FIXED CODE ###

a,b,x=map(int,(input().split()))
print(b//x-(a-1)//x)
#0 100000000000000000 1
### BUGGY CODE ###

def resolve():
    A, B, N = map(int, input().split())

    ans = 0
    for i in range(min(N, B - 1), 0, -1):
        tmp = (A * i // B)
        ans = max(tmp, ans)

    print(ans)


resolve()

### FIXED CODE ###

def resolve():
    A, B, N = map(int, input().split())
    print(A * min(N, B - 1) // B)


resolve()
### BUGGY CODE ###

s = input()
dp = [[0 for i in range(13)] for i in range(len(s))]
if s[-1] != "?":
    dp[0][int(s[-1]) % 13] += 1
else:
    for k in range(10):
        dp[0][k % 13] += 1

for i in range(1,len(s)):
    for r in range(13):
        if s[-(i+1)] == "?":
            for k in range(10): 
                dp[i][(k * (10**i) + r) % 13] += dp[i-1][r] % (10**9+7)
                
        else:
            dp[i][(int(s[-(i+1)]) * (10**i) + r) % 13] += dp[i-1][r] % (10**9+7)
            
print(dp[len(s)-1][5]%(10**9+7))


### FIXED CODE ###

s = input()
dp = [[0 for i in range(13)]]
if s[-1] != "?":
    dp[0][int(s[-1]) % 13] += 1
else:
    for k in range(10):
        dp[0][k % 13] += 1
        
d = [1]   
for i in range(1,len(s)):
    dp.append([0]*13)
    d.append(d[i-1]*10 % 13)
    for r in range(13):
        if s[-(i+1)] == "?":
            for k in range(10): 
                dp[i][(k * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)
                
        else:
            dp[i][(int(s[-(i+1)]) * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)

print(dp[len(s)-1][5]%(10**9+7))
### BUGGY CODE ###

import math
m = list(map(int, input().split()))[0]
a = list(map(int, input().split()))


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
  
b = [False for i in range(m)]
c = [False for i in range(m)]

for i in range(m):
    ii = m - i
    if(a[ii-1] != b[ii-1]):
        k = make_divisors(ii)
        for j in k:
            b[j-1] = not b[j-1]
        c[ii-1] = True
    #print("b",b)
    #print("c",c)
    #print()

ans = ""
count = 0
for i in range(m):
    if(c[i] == True):
        ans+= str(i+1) + " "
        count +=1
        
print(count)
print(ans)

### FIXED CODE ###

import math

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

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

for ii in range(n):
    #print(ans)
    i = n-ii
    if(a[i-1]!=ans[i-1]):
        d = make_divisors(i)
        ball.append(i)
        for k in d:
            ans[k-1] = 1-ans[k-1]
print(len(ball))
print(' '.join(map(str,ball)))
### BUGGY CODE ###

n = int(input())
a = input().split()
aa = [int(a[i]) for i in range(n)]
b = 1
for i in range(n):
  b = b * aa[i]
c = 0
cnt = 0
while c < 1:
  if b % 2 == 0:
    b = b // 2
    cnt = cnt + 1
  else:
    c = 1
print(cnt)

### FIXED CODE ###

n = int(input())
a = input().split()
aa = [int(a[i]) for i in range(n)]
b = 1
for i in range(n):
  s = list(str(aa[i]))
  ss = int(s[-1])
  if ss == 0 or ss == 2 or ss == 4 or ss == 6 or ss == 8:
  	b = b * aa[i]

c = 0
cnt = 0
while c < 1:
  if b % 2 == 0:
    b = b // 2
    cnt = cnt + 1
  else:
    c = 1
print(cnt)
### BUGGY CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
ca = Counter(a)

ans = 0
for i in ca.keys():
  cnt = sum([v for k, v in ca.items() if i-1 <= k <= i+1])
  if ans < cnt:
    ans = cnt
print(ans)


### FIXED CODE ###

input()
C = [0] * 100002
for i in map(int, input().split()):
  C[i - 1] += 1
  C[i] += 1
  C[i + 1] += 1
print(max(C))
### BUGGY CODE ###

# bin/env/pypy3
import sys
import collections
n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))
c = collections.Counter(a)
#print(n,a,c)
memo_e = {}
for e in a:
    if not e in memo_e:
        c[e] -= 1
        memo_e[e] = sum(v*(v-1)//2 for v in c.values() if v > 1)
        c[e] += 1
    print(memo_e[e])


### FIXED CODE ###

# bin/env/pypy3
import sys
import collections
n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))
c = collections.Counter(a)
#print(n,a,c)
memo_e = {}
s = sum(v*(v-1)//2 for v in c.values() if v > 1)
for e in a:
    if not e in memo_e:
        #c[e] -= 1
        if 1 < c[e]:
            memo_e[e] = s - (c[e]*(c[e]-1)//2 - (c[e]-1)*(c[e]-2)//2)
        else:
            memo_e[e] = s
    print(memo_e[e])
### BUGGY CODE ###

n, m = [int(i) for i in input().split(" ")]
s = [int(input()) for _ in range(m)]

divider = 10**9 + 7
ans = [0]*(n + 1)
ans[0] = 1
ans[1] = 1

if 1 in s:
    ans[1] = 0
        
for i in range(2, n+1):
    
    if i in s:
        continue
    else:
        ans[i] = ans[i-1] + ans[i-2]
    
   
print(ans[n] % divider)

### FIXED CODE ###

n, m = [int(i) for i in input().split(" ")]

l = list(range(1, n+1))
divider = 10**9 + 7
ans = [0]*(n + 1)
broken = [False]*(n+1)
ans[0] = 1
ans[1] = 1

for i in range(m):
    a = int(input())
    broken[a] = True
    if a == 1:
        ans[1] = 0
    
for i in range(2,n+1):
    if broken[i] == False:
        ans[i] = ans[i-1] + ans[i-2]
    
   
print(ans[n] % divider)
### BUGGY CODE ###

N,K=map(int,input().split())
ans=0

A=list(map(int,input().split()))
for j in range(N):
    A[j] %= K
ans += A.count(1)

B=[]
for j in range(N-1):
    B.append((A[j]+A[j+1])%K)
ans += B.count(2)

for i in range(2,min(K+1,N)):
    C=[]
    for j in range(N-i):
        C.append((B[j]+B[j+1]-A[j+1])%K)
    ans += C.count(i+1)
    A = B
    B = C
    
print(ans)
    


### FIXED CODE ###

import numpy
N,K=map(int,input().split())

if K==1:
    print(0)
    exit(0)

A=list(map(int,input().split()))
S=[0]+list(numpy.cumsum(A)) #累積和
S2=[(S[i]-i)%K for i in range(N+1)]

d = {}
ans = 0
for j in range(1,N+1):
    if j>K-1:
        if S2[j-K] in d:
            d[S2[j-K]] -= 1
        
    if S2[j-1] in d:
        d[S2[j-1]] += 1
    else:
        d[S2[j-1]] = 1
        
    if S2[j] in d:
        ans += d[S2[j]]
print(ans)
### BUGGY CODE ###

import sys
# 整数の入力
N,M=list(map(int, input().split()))
p=[]
q=0
count=0
for i in range(0,M):
  p.append(list(map(int, input().split())))
for i in range(0,M):
  q+=p[i][0]-p[i][1]
if q%2==1:
  print("NO")
else:
  for j in range(0,M):
    for i in range(0,M):
      if p[i][0]==j or p[i][1]==j:
        count+=1
    if count%2==1:
      print("NO")
      sys.exit()
  else: 
    print("YES")

### FIXED CODE ###

import sys
# 整数の入力
N,M=list(map(int, input().split()))
p=[]
for i in range(0,N):
  p.append(0)
for i in range(0,M):
  count=list(map(int, input().split()))
  p[count[0]-1]+=1
  p[count[1]-1]+=1
for i in range(0,M):
  if p[i]%2==1:
    print("NO")
    sys.exit()
print("YES")
### BUGGY CODE ###

def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


k = int(input())
s = input()
l = len(s)
MOD = 10 ** 9 + 7

facts, finvs = prepare(k + l, MOD)

ans = 0
for i in range(k + 1):
    r = k - i
    pat = facts[l + r - 1] * finvs[l - 1] * finvs[r] % MOD
    ans = (ans + pat * pow(25, r, MOD) * pow(26, i, MOD)) % MOD
print(ans)


### FIXED CODE ###

def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


k = int(input())
s = input()
l = len(s)
MOD = 10 ** 9 + 7

facts, finvs = prepare(k + l, MOD)

ans = 0
for i in range(k + 1):
    r = k - i
    pat = facts[l + r - 1] * finvs[l - 1] * finvs[r] % MOD
    ans = (ans + pat * pow(25, r, MOD) * pow(26, i, MOD)) % MOD
print(ans)
### BUGGY CODE ###

n = int(input())
table = [[] for _ in range(n+1)]
for i in range(1, n+1):
  a = list(map(int, input().split()))
  table[i] = a
cursor = [0]*(n+1)
is_matched = set()
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n):
    if cursor[i] < n-1 and i not in is_matched:
      j = table[i][cursor[i]]
      if i < j and j not in is_matched and table[j][cursor[j]] == i :
        match += 1
        cursor[i] += 1
        is_matched.add(i)
        cursor[j] += 1
        is_matched.add(j)
  if now_match == match:
    print(-1)
    exit()
  d += 1
  is_matched.clear()
print(d)

### FIXED CODE ###

n = int(input())
table = [[] for _ in range(n+1)]
for i in range(1, n+1):
  a = list(map(int, input().split()))
  table[i] = a
cursor = [0]*(n+1)
is_matched = set()
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n):
    if cursor[i] < n-1 and i not in is_matched:
      j = table[i][cursor[i]]
      if i < j and j not in is_matched and table[j][cursor[j]] == i :
        match += 1
        cursor[i] += 1
        is_matched.add(i)
        cursor[j] += 1
        is_matched.add(j)
  if now_match == match:
    print(-1)
    exit()
  if d > 30000:
    print(499500)
    exit()  
  d += 1
  is_matched.clear()
print(d)
### BUGGY CODE ###

n, m = map(int, input().split())
d1 = {}
for _ in range(n):
  a, b = map(int, input().split())
  if a in d1:
    d1[a].append(b)
  else:
    d1[a] = [b]
result = 0
d2 = {}
maxb = -1
for i in range(1, m + 1):
  if i in d1:
    for j in d1[i]:
      if j not in d2:
        d2[j] = 0
      d2[j] += 1
      if j > maxb:
        maxb = j
  else:
    if len(d2) == 0:
      continue
  result += maxb
  if d2[maxb] == 1:
    del d2[maxb]
    if len(d2) == 0:
      maxb = 0
    else:
      maxb = max(d2.keys())
  else:
    d2[maxb] -= 1
print(result)

### FIXED CODE ###

from heapq import heappush, heappop
n, m = map(int, input().split())
jobs = {}
for _ in range(n):
  a, b = map(int, input().split())
  if a > m:
    continue
  if a in jobs:
    jobs[a].append(b)
  else:
    jobs[a] = [b]
result = 0
candidates = []
for a in range(1, m + 1):
  if a in jobs:
    for b in jobs[a]:
      heappush(candidates, -b)
  else:
    if len(candidates) == 0:
      continue
  result += -heappop(candidates)
print(result)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))

dp = [[0]*(n+1) for i in range(n+1)]

for d in range(1, n+1):
    for i in range(n+1-d):
        j = i+d
        if (n-d)%2 == 0:
            dp[i][j] = max(dp[i+1][j]+A[i], dp[i][j-1]+A[j-1])
        else:
            dp[i][j] = min(dp[i+1][j]-A[i], dp[i][j-1]-A[j-1])
print(dp[0][n])

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))

dp = [[0]*(n+1) for i in range(n+1)]

for d in range(1, n+1):
    for i in range(n+1-d):
        j = i+d
        if (n-d)%2 == 0:
            dp[i][j] = max(dp[i+1][j]+A[i], dp[i][j-1]+A[j-1])
        else:
            dp[i][j] = min(dp[i+1][j]-A[i], dp[i][j-1]-A[j-1])
print(dp[0][n])
### BUGGY CODE ###

import numpy as np
from scipy.optimize import fmin

n,k=map(int,input().split())
XYC=[list(map(int,input().split())) for i in range(n)]
def f(xy):
    x,y=xy
    times=[c*((X-x)**2+(Y-y)**2)**0.5 for X,Y,c in XYC]
    times.sort()
    return times[k-1]
ansx=[fmin(f,(x,y),disp=False,ftol=10**(-6)) for x,y,c in XYC]
ansy=list(map(lambda x:f(x),ansx))
print(min(ansy))


### FIXED CODE ###

import numpy as np
from scipy.optimize import fmin

n,k=map(int,input().split())
XYC=[list(map(int,input().split())) for i in range(n)]
X,Y,C=[],[],[]
for x,y,c in XYC:
    X.append(x)
    Y.append(y)
    C.append(c)
X=np.array(X,dtype=np.float)
Y=np.array(Y,dtype=np.float)
C=np.array(C,dtype=np.float)
def f(xy):
    x,y=xy
    times=(X-x)*(X-x)+(Y-y)*(Y-y)
    times=C*np.sqrt(times)
    times=np.sort(times)
    return times[k-1]
deff=0.5
ansx=[fmin(f,(x,y),disp=False,ftol=10**(-7),initial_simplex=[(x+deff,y),(x-deff,y+deff),(x-deff,y-deff)]) for x,y,c in XYC]
ansy=list(map(lambda x:f(x),ansx))
print(min(ansy))
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(1,n):
    ans+=i
print(ans)

### FIXED CODE ###

n = int(input())
print(n*(n+1)//2 - n)