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

def dw_heap(A,i,length):
    largest = i
    while True:
        l = i*2
        r = l + 1
        if l < length and A[l] > A[largest]: largest = l
        if r < length and A[r] > A[largest]: largest = r
        if largest == i: return
        A[i], A[largest] = A[largest], A[i] 
        i = largest


def up_heap(A,i):
    p = i//2
    while A[i] > A[p]:
        A[i], A[p] = A[p], A[i] 
        i = p
        p = i//2


if __name__=='__main__':
    hp = [None]*(2*10**6)
    hp[0] = 2*10**9 + 1
    i = 1
    j = -1 
    while True:
        op = input() 
        if   op[0] != 'i': break
        hp[i] = int(op[7:])
        i += 1
    if op[2] != 'd':
        for k in range(i//2,0,-1): dw_heap(hp,k,i)
    while True:
        if   op[2] == 'd': break
        if   op[0] == 'i':
            hp[i] = int(op[7:])
            up_heap(hp,i)
            i += 1
        else:# extract
            hp[j] = hp[1]
            hp[1],hp[i-1] = hp[i-1],hp[1]
            dw_heap(hp,1,i-1)
            i -= 1
            j -= 1
        op = input() 
    print(*hp[:j:-1],sep='\n')

### FIXED CODE ###

from sys import stdin

def dw_heap(A,i):
    largest = i
    while True:
        l = i*2
        r = l + 1
        if A[l] > A[largest]: largest = l
        if A[r] > A[largest]: largest = r
        if largest == i: return
        A[i], A[largest] = A[largest], A[i] 
        i = largest

def up_heap(A,i):
    p = i//2
    while A[i] > A[p]:
        A[i], A[p] = A[p], A[i] 
        i = p
        p = i//2

if __name__=='__main__':
    hp = [-1]*(4000000)
    hp[0] = 2000000001
    i = 1
    j = -1 
    for op in stdin:
        if op[0] == 'i':# insert
            hp[i] = int(op[7:])
            up_heap(hp,i)
            i += 1
        elif op[1] == 'x':# extract
            hp[j],hp[1],hp[i-1] = hp[1],hp[i-1],-1
            dw_heap(hp,1)
            i -= 1
            j -= 1
        else:# end
            break
    print(*hp[:j:-1],sep='\n')
### BUGGY CODE ###

S=input()
Q=int(input())

for i 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 CODE ###

S=input()
Q=int(input())
p=0
u=0
l=""
r=""
for i in range(Q):
    q=list(input().split())
    if q[0]=="1":
        u+=1
    else:
        if q[1]=="1" and u%2==0 or q[1]=="2" and u%2==1:
            l=l+q[2]
        else:
            r=r+q[2]
if u%2==0:
    l=l[::-1]
    S=l+S+r
else:
    S=S[::-1]
    r=r[::-1]
    S=r+S+l
print(S)
### BUGGY CODE ###

n = int(input())
s = input()

length = n//2

for ans in reversed(range(1, length+1)):
    for left in range(n - 2 * ans + 1):
        for right in range(left + ans, n - ans + 1):
            if s[left:left+ans] == s[right:right+ans]:
                print(ans)
                exit()

print(0)




### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
s = tuple(map(lambda x: ord(x) - ord("a") + 1, input()))
base = 1007
mod = 2**61 - 1

length = n//2
b = [1] * (length + 1)
shash = [0] * (length+1)
for i in range(1, length + 1):
    b[i] = b[i-1] * base % mod
    shash[i] = (shash[i - 1] * base + s[i - 1]) % mod

for ans in reversed(range(1, length+1)):
    # calc hash
    hash_ = 0
    check = {}
    #y = set([])
    for left in range(n - ans + 1):
        if left == 0:
            hash_ = shash[ans]
            check[hash_] = left
            #y.add(hash_)
        else:
            hash_ = base * hash_ - b[ans] * s[left - 1] + s[left + ans - 1]
            hash_ %= mod
            if hash_ in check.keys():
                # print("tmp = ", tmp)
                if check[hash_] <= left - ans:
                    print(ans)
                    # a = check[hash_][tmp-1]
                    # at = "".join(map(lambda x: chr(x + ord("a")), s[a:a+ans]))
                    # for j in range(ans):
                        # if s[a+j] != s[left+j]:
                            # print("Fail")
                            # exit()
                    # print("Success")
                    sys.exit()
            else:
                check[hash_] = left
                #y.add(hash_)
        # print(hash_, s[left:left+ans])
print(0)
### BUGGY CODE ###

import sys
import numpy as np

input = sys.stdin.readline

N, W = map(int, input().split())
Weight, V = [], []
for i in range(N):
    w, v = map(int, input().split())
    Weight.append(w)
    V.append(v)

dp = np.zeros((N+1, W+1))

maximum = 0
for i in range(N):
    for w in range(W+1):
        if w >= Weight[i]:
            dp[i+1, w] = dp[i, w - Weight[i]] + V[i]
        else:
            dp[i+1, w] = dp[i, w]
        if maximum < dp[i+1,w]:
            maximum = dp[i+1,w]

        
print(int(maximum))


### FIXED CODE ###

N, W = map(int, input().split())
#i個目の品物までで重さw以下のときの価値の最大値 
dp = [[0]*(W+1) for _ in range(N+1)]
"""
dp[i, wi:W+1] = max(i番目の重さwiの品物を入れた場合, 入れなかった場合)
         = np.max(dp[i-1, :W-wi+1] + v, dp[i-1, wi:W+1])
"""

for i in range(1, N+1):
    w, v = map(int, input().split())

    for j in range(W+1):
        if j - w >= 0:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
        else:
            dp[i][j] = dp[i-1][j]

print(dp[-1][-1])
### BUGGY CODE ###

def f_pond_skater():
    from fractions import Fraction
    from heapq import heappop, heappush
    from math import ceil
    H, W, K = [int(i) for i in input().split()]
    start_row, start_col, target_row, target_col = [int(i) - 1 for i in input().split()]
    Grid = [input() for _ in range(H)]

    def is_inside(row, col):
        return (0 <= row < H) and (0 <= col < W)

    dp = [[[float('inf')] * 4 for j in range(W)] for i in range(H)]
    dr, dc = (0, -1, 0, 1), (-1, 0, 1, 0)  # '0123' と '左上右下' を対応
    queue = [(0, start_row, start_col, i) for i in range(4)]
    while queue:
        cost, row, col, direction = heappop(queue)
        dp[row][col][direction] = cost

        # 1マス直進する
        nr, nc = row + dr[direction], col + dc[direction]
        if (is_inside(nr, nc) and Grid[nr][nc] == '.' and
                dp[nr][nc][direction] > cost + Fraction(1, K)):
            heappush(queue, (dp[row][col][direction] + Fraction(1, K), nr, nc, direction))

        # 向きを 90 度変える
        for i in (1, 3):
            if dp[row][col][(direction + i) % 4] > ceil(float(cost)):
                heappush(queue, (ceil(float(cost)), row, col, (direction + i) % 4))

    ans = min(dp[target_row][target_col][d] for d in range(4))
    return ceil(float(ans)) if ans != float('inf') else -1

print(f_pond_skater())

### FIXED CODE ###

def f_pond_skater():
    from heapq import heappush, heappop
    H, W, K = [int(i) for i in input().split()]
    start_row, start_col, target_row, target_col = [int(i) - 1 for i in input().split()]
    Grid = [input() for _ in range(H)]

    heap = []
    dist = [[float('inf')] * W for _ in range(H)]
    dist[start_row][start_col] = 0

    diff = ((0, 1), (1, 0), (0, -1), (-1, 0))
    heappush(heap, (0, start_row, start_col))
    while heap:
        cost, row, col = heappop(heap)
        cost_next = cost + 1

        if row == target_row and col == target_col:
            return cost

        for dr, dc in diff:
            nr, nc = row, col
            for _ in range(K):
                nr += dr
                nc += dc
                if not (0 <= nr < H and 0 <= nc < W) or Grid[nr][nc] == '@':
                    break
                if dist[nr][nc] > cost_next:
                    dist[nr][nc] = cost_next
                    heappush(heap, (cost_next, nr, nc))
                elif dist[nr][nc] == cost_next:
                    continue
                else:
                    break
    return -1

print(f_pond_skater())
### BUGGY CODE ###

n, w = list(map(int, input().strip().split()))
data = []
for i in range(n):
    data.append(list(map(int, input().strip().split())))

dp = {}

# i 個までで重さを z 以下にしたときの最大値
def rec(i, z):
    global dp
    if (i, z) in dp:
        return dp[(i, z)]

    if i < 0:
        ret = 0
    # i 個目のものを入れられない場合
    elif data[i][0] > z:
        ret = rec(i - 1, z)
    else:
        # 入れられる場合、入れるときと入れないときのうち大きい方を返す
        # 入れるとき
        v1 = data[i][1] + rec(i - 1, z - data[i][0])
        # 入れないとき
        v2 = rec(i - 1, z)
        ret = max(v1, v2)
        dp[(i, z)] = ret
    return ret

print(rec(n - 1, w))


### FIXED CODE ###

n, w = map(int, input().strip().split())
data = [list(map(int, input().strip().split())) for _ in range(n)]

# i番目に重さがj以下となるように選んだときの価値の総和の最大値
dp = [[0] * (w + 1) for _ in range(n)]

for i in range(0, n):
    for j in range(w + 1):
        # i 番目の品物の重さと価値
        wi, vi = data[i]
        if i == 0:
            take = vi if j - wi >= 0 else 0
            miss = 0
            dp[i][j] = max(take, miss)
        else:
            # i番目の品物を入れる場合
            take = dp[i - 1][j - wi] + vi if j - wi >= 0 else 0
            # 入れない場合
            miss = dp[i - 1][j]
            dp[i][j] = max(take, miss)

print(max(dp[n - 1]))
### BUGGY CODE ###

a = input()

a = int(a)

b = a

b = int(b)

if a % 9 == 0:

    for i in range(a):
        b += b % pow(10, i)

else:
    print("No")
    exit()

if b % 9 == 0:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

a = input()

a = int(a)

if a % 9 == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

# ABC 142 C go to school
n = int(input())
s = list(map(int,input().split()))

# ソートされたリストのインデックスを返す
for i in range(len(s)):
    print(sorted(range(len(s)), key=lambda k:s[k])[i] + 1, end=" ")

### FIXED CODE ###

# ABC 142 C go to school
n = int(input())
s = list(map(int,input().split()))

# ソートされたリストのインデックスを返す
s = sorted(range(len(s)), key=lambda k:s[k])
ans = [x+1 for x in s]
print(*ans)
### BUGGY CODE ###

n = int(input())
p = list(map(float, input().split()))
dp = [[0.0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1.0
for i in range(1, n + 1):
    for j in range(n + 1):
        dp[i][j] = dp[i - 1][j] * (1 - p[i - 1]) + dp[i - 1][j - 1] * p[i - 1]
ans = sum(dp[n][i] for i in range(n // 2 + 1, n + 1))
print(ans)


### FIXED CODE ###

n = int(input())
p = list(map(float, input().split()))
dp = [[0.0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1.0
for i in range(1, n + 1):
    for j in range(n + 1):
        dp[i][j] = dp[i - 1][j] * (1 - p[i - 1]) + dp[i - 1][j - 1] * p[i - 1]
ans = sum(dp[n][i] for i in range(n // 2 + 1, n + 1))
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
l = list()
r = list()
for i in range(m):
    a, b = map(int, input().split())
    l.append(a)
    r.append(b)

ans = 0

for j in range(n):
    flag = 1
    for k in range(m):
        if j < l[k]-1 or j > r[k]-1:
            flag = 0
    if flag == 1:
        ans += 1

print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
l = list()
r = list()
for i in range(m):
    a, b = map(int, input().split())
    l.append(a)
    r.append(b)

if min(r) >= max(l):
    print(min(r) - max(l) + 1)
else:
    print(0)
### BUGGY CODE ###

N = int(input())
A = input().split()
A = [int(n) for n in A]
for i in range(N):
	A_init = A
	A = [n for n in A if n != i+1]
	print(len(A_init) - len(A))

### FIXED CODE ###

N = int(input())
A =[int(n) for n in input().split()]
b = [0]*N
for i in A:
  b[i-1]+=1
for i in range(N):
  print(b[i])
### BUGGY CODE ###

# https://atcoder.jp/contests/abc097/tasks/arc097_a
# C - K-th Substring

s = input().split()[0]
K = int(input().split()[0])

sub_s_list = []

for i in range(len(s)):
    for j in range(len(s)):
        sub_s = s[i:i+j+1]
        sub_s_list.append(sub_s)

sub_s_list = list(set(sub_s_list) - set(['']))
ans = sorted(sub_s_list)[K-1]
print(ans)


### FIXED CODE ###


# https://atcoder.jp/contests/abc097/tasks/arc097_a
# C - K-th Substring

s = input().split()[0]
K = int(input().split()[0])

sub_s_list = []
N = len(s)
sorted_char_list = sorted(list(set(s)))
char_N = len(sorted_char_list)

# Kは最大で5であることに着目する
# 全部列挙する必要はなく、5番目まで見つかればよい
# 最初の1文字目
start_index_list = [i for i, char in enumerate(s) if char == sorted_char_list[0]]
pattern = sorted_char_list[0]
sorted_char_list.remove(pattern)
char_i = 0
j = 1

waiting_list = []

while len(sub_s_list) < 5:
    # print(pattern)
    sub_s_len = len(pattern)
    sub_s_list.append(pattern)
    next_list = [s[i:i+sub_s_len+1]
                for i in start_index_list
                if (i <= N - (sub_s_len + 1)) and (s[i:i+sub_s_len] == pattern)]

    if not next_list:
        if min(start_index_list) + sub_s_len > N:
            # 末尾まで伸びた
            if waiting_list:
                pattern = waiting_list[0]
                waiting_list.remove(pattern)
            elif sorted_char_list:
                pattern = sorted_char_list[0]
                start_index_list = [i for i, char in enumerate(s) if char == sorted_char_list[0]]
                sorted_char_list.remove(pattern)
        else:
            # 末尾まで伸ばす
            next_waiting_list =  [s[i:i+sub_s_len+1] for i in start_index_list
                                    if (i <= N - (sub_s_len + 1))]
            # print(next_waiting_list)
            waiting_list += next_waiting_list
            waiting_list = list(set(waiting_list))

            if waiting_list:
                waiting_list = sorted(waiting_list)
                pattern = waiting_list[0]
                waiting_list.remove(pattern)
            elif sorted_char_list:
                pattern = sorted_char_list[0]
                start_index_list = [i for i, char in enumerate(s) if char == sorted_char_list[0]]
                sorted_char_list.remove(pattern)
    else:
        waiting_list += next_list
        waiting_list = sorted(list(set(waiting_list)))
        pattern = waiting_list[0]
        waiting_list.remove(pattern)
    # print(waiting_list)

sub_s_list = list(set(sub_s_list))
ans = sorted(sub_s_list)[K-1]
print(ans)
### BUGGY CODE ###

l, r = map(int, input().split())

mod = 2019
minij = l * (l + 1)

for i in range(l, r):
    for j in range(i+1, r+1):
        if (i * j) % mod < minij:
            minij = (i*j) % mod
            if minij == 0:
                print(minij)
                exit(0)

print(minij)

### FIXED CODE ###

l, r = map(int, input().split())

mod = 2019
minij = 2020

for i in range(l, r):
    for j in range(i+1, r+1):
        if (i * j) % mod < minij:
            minij = (i*j) % mod
            if minij == 0:
                print(minij)
                exit(0)

print(minij)
### BUGGY CODE ###

#!/usr/bin/python
# -*- coding: utf-8 -*-

# 入力はstringで入る．
# intにしたければ int(input())
# floatで受け取ると 1.0 になる．

# 入力 : N
# 入力 : A1 A2 ... AN
N = int(input())
A = list(map(int, input().split()))

Number = []

for i in range(N):
    Number.append(A.count(i+1))

Total = 0

for i in range(N):
    Total = Total + Number[i]*(Number[i]-1)/2

for k in range(N):
    print(int(Total - Number[A[k]-1]*(Number[A[k]-1]-1)/2 + (Number[A[k]-1]-1)*(Number[A[k]-1]-2)/2))


### FIXED CODE ###


import collections

# 入力 : N
# 入力 : A1 A2 ... AN
N = int(input())
A = list(map(int, input().split()))

C = collections.Counter(A)

Total = sum([i*(i-1)/2 for i in C.values()])

for Ak in A:
    print(int(Total - C[Ak]+1))
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]

I = a.count(1)
J = a.count(2)
K = a.count(3)

dp = [[[0 for _ in range(K+1)] for __ in range(J+K+1)] for ___ in range(I+J+K+1)]

for k in range(K+1):
    for j in range(J+K+1-k):
        for i in range(I+J+K+1-k-j):
            if i == 0 and j == 0 and k == 0:
                continue
            if k-1 > -1 and j+1 < J+K+1:
                dp[i][j][k] += (n/(i+j+k))*(k/n)*dp[i][j+1][k-1]
            if j-1 > -1 and i+1 < I+J+K+1:
                dp[i][j][k] += (n/(i+j+k))*(j/n)*dp[i+1][j-1][k]
            if i-1 > -1:
                dp[i][j][k] += (n/(i+j+k))*(i/n)*dp[i-1][j][k]
            dp[i][j][k] += n/(i+j+k)

print(dp[I][J][K])


### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]

I = a.count(3)
J = a.count(2)
K = a.count(1)

dp = [[[0 for _ in range(I+J+K+1)] for __ in range(I+J+1)]
      for ___ in range(I+1)]

for i in range(I+1):
    for j in range(I+J+1-i):
        for k in range(I+J+K+1-i-j):
            if i + j + k == 0:
                continue
            if k-1 > -1:
                dp[i][j][k] += (n/(i+j+k))*(k/n)*dp[i][j][k-1]
            if j-1 > -1:
                dp[i][j][k] += (n/(i+j+k))*(j/n)*dp[i][j-1][k+1]
            if i-1 > -1:
                dp[i][j][k] += (n/(i+j+k))*(i/n)*dp[i-1][j+1][k]
            dp[i][j][k] += n/(i+j+k)

print(dp[I][J][K])
### BUGGY CODE ###

n, k = map(int, input().split())
p = tuple(map(int, input().split()))

prev = 0
ind = 0
for i in range(n - k + 1):
    nex = 0
    for j in range(i, i + k):
        nex += p[j]

    if prev < nex:
        prev = nex
        ind = i

total = 0
for i in range(ind, ind + k):
    total += (1 + p[i]) * (p[i] / 2) / p[i]

print(total)


### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))

prev = sum(p[1:k])
current = sum(p[1:k])
ind = 0

for i in range(1, n - k + 1):
    current = current - p[i - 1] + p[i + k - 1]

    if prev < current:
        prev = current
        ind = i

total = 0
for i in range(ind, ind + k):
    total += p[i] / 2 + 0.5

print(total)
### BUGGY CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
AGC023 B
"""

from itertools import product

n = int(input())
sli = [input() for i in range(n)]

ans = 0
for k in range(n):
    if all((sli[i][j] == sli[(j+k) % n][(i-k) % n] for i, j in product(range(n), repeat=2))):
        ans += n

print(ans)



### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
AGC023 B
"""

from itertools import product

n = int(input())
sli = [input() for i in range(n)]

ans = 0
for k in range(n):
    if all((sli[i][j] == sli[(j+k) % n][(i-k) % n] for i, j in product(range(n), repeat=2))):
        ans += n

print(ans)
### BUGGY CODE ###

# 数列aの最小値min_aの最大値はM//N
# 他の要素がmin_aの倍数であれば、min_aが最大公約数となる
# すなわち、(M-min_a)をmin_aで割った余りが0

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

if M%2 == 0:
    for i in range(M//N, 0, -1):
        if (M - i)%i == 0:
            break
    print(i)    
else:
    if M//N % 2 == 0:
        min_a = M//N - 1
    else:
        min_a = M//N
    for i in range(min_a, 0, -2):
        if (M - i)%i == 0:
            break
    print(i)      

### FIXED CODE ###

# 数列aの最小値min_aの最大値はM//N
# 他の要素がmin_aの倍数であれば、min_aが最大公約数となる
# すなわち、(M-min_a)をmin_aで割った余りが0

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

if M%2 == 0:
    for i in range(M//N, 0, -1):
        if (M - i)%i == 0:
            break
    print(i)    
else:
    if M//N % 2 == 0:
        min_a = M//N - 1
    else:
        min_a = M//N
    for i in range(min_a, 0, -2):
        if (M - i)%i == 0:
            break
    print(i)
### BUGGY CODE ###

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

tmp = 1
for num in A:
    tmp *= num
if tmp <= 1e18:
    print(tmp)
else:
    print(-1)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
 
tmp = 1
for num in A:
    tmp *= num
    if tmp > 1e18:
      break
  
if tmp <= 1e18:
    print(tmp)
elif 0 in A:
    print(0)
else:
    print(-1)
### BUGGY CODE ###

import fractions
import functools

MOD = 10**9+7

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

n = int(input())
a = [int(_) for _ in input().split()]
LCM = functools.reduce(lambda x, y : lcm(x, y), a, 1)

ans_arr = [0] * n
for i in range(len(a)):
    ans_arr[i] = LCM // a[i]
print(sum(ans_arr) % MOD)

### FIXED CODE ###

from fractions import gcd
from functools import reduce

MOD = 1000000007

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

n = int(input())
a = [int(_) for _ in input().split()]
LCM = reduce(lcm, a)

arr = [LCM // _ for _ in a]
print(sum(arr) % MOD)
### BUGGY CODE ###

#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

N = int(input().strip())
A = set([])

for _ in range(N - 1):
    u, v = tuple(map(int, input().strip().split()))
    A.add((u-1, v-1))

V = 0
for l in range(N):
    for r in range(l, N):
        V += r - l + 1

E = 0
for u in range(N):
    for v in range(u, N):
        if (u, v) in A or (v, u) in A:
            E += (u + 1) * (N - v)

print(V - E)

##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker


### FIXED CODE ###

#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

N = int(input().strip())
A = set([])

for _ in range(N - 1):
    u, v = tuple(map(int, input().strip().split()))
    A.add((u, v))

V = 0
for l in range(1, N + 1):
    V += (N - l + 1) * (N - l + 2) // 2

E = 0
for u, v in A:
    a = min(u, v)
    b = max(u, v)
    E += a * (N - b + 1)

print(V - E)

##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker
### BUGGY CODE ###

import itertools
n,p = [int(x) for x in input().split()]
s = input()
if p!=2 and p!=5:
  r = [0]
  for i in range(n):
    a = int(s[i:])%p
    r.append(a)
  #print(r)
  r.sort()
  ans = 0
  cnt=1
  for i in range(len(r)-1):
    if r[i]==r[i+1]:
      cnt+=1
    else:
      ans +=cnt*(cnt-1)//2
      cnt=1
  print(ans+cnt*(cnt-1)//2)
elif p==2:
  ans = 0
  for i in range(n):
    if int(s[i])%2==0:
      ans +=i+1
  print(ans)
elif p==5:
  ans = 0
  for i in range(n):
    if int(s[i])%5==0:
      ans +=i+1
  print(ans)

### FIXED CODE ###

from collections import defaultdict,deque
import itertools
n,p = [int(x) for x in input().split()]
s = list(input())
if p!=2 and p!=5:
  r = defaultdict(int)
  a =[]
  s1 = s[::-1]
  for i in range(n):
    a.append((int(s1[i])%p*pow(10,i,p))%p)
  a = [0]+a[::-1]
  b = list(itertools.accumulate(a))
  for i in b:
    r[i%p]+=1
  ans = 0
  for i in r.values():
    ans+=(i*(i-1))//2
  print(ans)
elif p==2:
  ans = 0
  for i in range(n):
    if int(s[i])%2==0:
      ans +=i+1
  print(ans)
elif p==5:
  ans = 0
  for i in range(n):
    if int(s[i])%5==0:
      ans +=i+1
  print(ans)
### BUGGY CODE ###

n = int(input())
a = [0] * (n+1)
for i in range(n):
    a[i+1] = tuple(map(int, input().split()))
from queue import Queue
todo = [0] * (n+1)
matched = Queue()
for i in range(1, n+1):
    matched.put(i)
days = 0
while True:
    update = []
    while matched.empty() == False:
        i = matched.get()
        if todo[i] < n - 1 and i not in update:
            p = a[i][todo[i]]
            if a[p][todo[p]] == i:
                update.append(i)
                update.append(p)
    for j in update:
        todo[j] += 1
        matched.put(j)
    days += 1
    #print(todo)
    if update == []:
        days = -1
        break
    elif todo[1:] == [n - 1] * n:
        break
print(days)


### FIXED CODE ###

n = int(input())
a = []
for _ in range(n+1):
    a.append([-1])
for i in range(n):
    inp = list(map(int, input().split()))
    for j in range(n-2, -1, -1):
        a[i+1].append(inp[j])
matched = [i for i in range(1, n+1)]
finish = 0
days = 0
while True:
    used = set()
    while matched != []:
        i = matched.pop()
        p = a[i][-1]
        if p != -1 and a[p][-1] == i and (i not in used) and (p not in used) :
            a[i].pop()
            a[p].pop()
            used.add(i)
            used.add(p)
            if a[i][-1] == -1:
                finish += 1
            if a[p][-1] == -1:
                finish += 1
    days += 1
    matched = list(used)
    if len(used) == 0:
        days = -1
        break
    elif finish == n:
        break
print(days)