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

H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(list(input()))
    
## 横方向につながっているか
yoko = [0]*(H*W)
for i in range(H):
  hold = 0
  for j in range(W):
    if S[i][j] == '#':
      hold = 0
    else:
      hold += 1
      yoko[i*W+j] = hold
  ## 今度は逆順に辿る
  hold = 0
  for j in range(W):
    if S[i][W-1-j] == '#':
      hold = 0
    else:
      hold = max(hold, yoko[i*W+(W-1-j)])
      yoko[i*W+(W-1-j)] = hold
      
## 縦方向につながっているか
tate = [0]*(H*W)
for j in range(W):
  hold = 0
  for i in range(H):
    if S[i][j] == '#':
      hold = 0
    else:
      hold += 1
      tate[i*W+j] = hold
  ## 今度は逆順に辿る
  hold = 0
  for i in range(H):
    if S[H-1-i][j] == '#':
      hold = 0
    else:
      hold = max(hold, tate[(H-1-i)*W+j])
      tate[(H-1-i)*W+j] = hold
      
solver = []
for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      continue
    else:
      var = yoko[i*W+j] + tate[i*W+j] - 1
      solver.append(var)

print(max(solver))



### FIXED CODE ###

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
      
H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(list(input()))
    
UF = UnionFind(2*H*W)
## 横方向につながっているか
for i in range(H):
  hold = []
  for j in range(W):
    if S[i][j] == '#':
      hold = []
    elif len(hold) == 0:
      hold = [(i,j)]
    else:
      UF.Unite(hold[0][0]*W+hold[0][1], i*W+j)

## 縦方向につながっているか
for j in range(W):
  hold = []
  for i in range(H):
    if S[i][j] == '#':
      hold = []
    elif len(hold) == 0:
      hold = [(i,j)]
    else:
      UF.Unite(hold[0][0]*W+hold[0][1]+(H*W), i*W+j+(H*W))
      
solver = []
for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      continue
    else:
      var = UF.Count(i*W+j) + UF.Count(i*W+j+(H*W)) - 1
      solver.append(var)

print(max(solver))
### BUGGY CODE ###

import numpy as np
n, m = map(int, input().split())
card = np.ones(n+1, dtype=int)
for i in range(m):
    l, r = map(int, input().split())
    card[:l] = 0
    card[r+1:] = 0

print(int(sum(card)))

### FIXED CODE ###

import sys
n, m = map(int, input().split())

min_id = 1
max_id = n
for i in range(m):
    l, r = map(int, input().split())

    if min_id < l <= max_id:
        min_id = l
    elif max_id < l:
        print(0)
        sys.exit()

    if min_id <= r < max_id:
        max_id = r
    elif r < min_id:
        print(0)
        sys.exit()

print(max_id - min_id + 1)
### BUGGY CODE ###

import math
def sosu(n):
    sosu=1
    if n==1:
        sosu=0
    sq=int(math.sqrt(n))
    for x in range(2,sq+2):
        if n%x==0 and x<n:
            sosu=0
            break
    return sosu  #素数なら1、そうでなければ0
n=int(input())
so=[]
count=0
if n==1:
    count=0
elif sosu(n)==1:
        count=1
else:
    for x in range(2,int(n/2)+2):
        if x>n:
            break
        hantei=sosu(x)
        shisu=1
        if hantei==1:
            while n%(x**shisu)==0:
                count+=1
                shisu+=1
                n=n/(x**(shisu-1))
print(count)

### FIXED CODE ###

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
n=int(input())
if n==1:
    ans=0
else:
    a=prime_factorize(n)
    if a==[]:
        ans=1
    else:
        ans=0
        xzen=a[0]
        count=1
        ans+=1
        for x in range(1,len(a)):
            if xzen==a[x]:
                count+=1
                if count==3 or count==6 or count==10 or count==15 or count==21 or count==28 or count==36:
                    ans+=1
            else:
                xzen=a[x]
                count=1
                ans+=1
print(ans)
### BUGGY CODE ###

N = int(input())
S = list(input())
ans = N + 1

for i in range(1,N - 1):
    E = S[:i - 1].count('W')
    W = S[i + 1:].count('E')
    ans = min(ans, E + W)

first = S[0:].count('E')
end = S[:N - 1].count('W')
ans = min(ans, first, end)

print(ans)

### FIXED CODE ###

N = int(input())
S = input()

rcost = 0
lcost = S.count('E')
if S[0] == 'E':
    lcost -= 1
ans = lcost

for i in range(N-1):
        if S[i] == 'W':
            rcost += 1
        if S[i+1] == 'E':
            lcost -= 1
        ans = min(ans, rcost+lcost)
    
print(ans)
### BUGGY CODE ###

import numpy as np

N, K = list(map(int, input().split(' ')))

marks = list(map(int, input().split(' ')))

stan = min(marks) - 1

marks = list(map(lambda x: x - stan, marks))

# print(marks)

scores = np.array([ np.array([marks[K+pivot-i-1] for i in range(K)]).prod() for pivot in range(N-K+1) ])

# print(scores)

for i in range(N-K):
  if scores[i] >= scores[i+1]:
    print('No')
  else:
    print('Yes')

### FIXED CODE ###

N, K = list(map(int, input().split(' ')))

marks = list(map(int, input().split(' ')))

for i in range(N-K):
  if marks[i] < marks[K+i]:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

k,s = map(int,input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            sum = x+y+z
            if sum == s:
                ans += 1
print(ans)

### FIXED CODE ###

k,s = map(int,input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-(x+y)
        if 0 <= z and z<=k:
            ans += 1 
print(ans)
### BUGGY CODE ###

INF = float('inf')
n, m = list(map(int, input().split()))
a, b, c = [], [], []
for _ in range(m):
    abc = list(map(int, input().split()))
    a.append(abc[0])
    b.append(abc[1])
    c.append(-abc[2]) # convert pos-neg

dist = [INF]*(n+1)
dist[1] = 0
for loop in range(n-1):
    for i in range(m):
        if dist[a[i]] == INF:
            continue
        if dist[b[i]] > dist[a[i]] + c[i]:
            dist[b[i]] = dist[a[i]] + c[i]
ans = dist[-1]

negative = [False]*(n+1) # negative closed path
for loop in range(n):
    for i in range(m):
        if dist[a[i]] == INF:
            continue
        if dist[b[i]] > dist[a[i]] + c[i]:
            dist[b[i]] = dist[a[i]] + c[i]
            negative[b[i]] = True
        if negative[a[i]] is True:
            negative[b[i]] = True

# print(dist, negative)
if negative[-1] is True:
    print('inf')
else:
    print(-ans)


### FIXED CODE ###

INF = float('inf')
n, m = list(map(int, input().split()))
a, b, c = [], [], []
for _ in range(m):
    abc = list(map(int, input().split()))
    a.append(abc[0])
    b.append(abc[1])
    c.append(-abc[2]) # convert pos-neg

dist = [INF]*(n+1)
dist[1] = 0
for loop in range(n-1):
    for i in range(m):
        if dist[a[i]] == INF:
            continue
        if dist[b[i]] > dist[a[i]] + c[i]:
            dist[b[i]] = dist[a[i]] + c[i]
ans = dist[-1]

negative = [False]*(n+1) # negative closed path
for loop in range(n):
    for i in range(m):
        if dist[a[i]] == INF:
            continue
        if dist[b[i]] > dist[a[i]] + c[i]:
            dist[b[i]] = dist[a[i]] + c[i]
            negative[b[i]] = True
        if negative[a[i]] is True:
            negative[b[i]] = True

    if negative[-1] is True:
        break
# print(dist, negative)
if negative[-1] is True:
    print('inf')
else:
    print(-ans)
### BUGGY CODE ###

from collections import Counter

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

cumA = [0] * (N + 1)

for i in range(N):
    cumA[i + 1] += cumA[i] + A[i]

cntA = Counter(cumA)

fact = [1] * (N + 2)
for i in range(1, N + 1):
    fact[i] *= fact[i - 1] * i

def ncr(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fact[n] // fact[n - r] // fact[r]

ans = 0
for _, c in cntA.items():
    ans += ncr(c, 2)

print(ans)

### FIXED CODE ###

from collections import Counter

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

cumA = [0] * (N + 1)

for i in range(N):
    cumA[i + 1] += cumA[i] + A[i]

cntA = Counter(cumA)

ans = sum([c * (c - 1) // 2 for c in cntA.values()])

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

a = input()
q = int(input())

for i in range(q):
  qi = input()
  if( qi == "1"):
    a = a[::-1]
  else:
    if( qi[2] == "2" ):
      a = a + qi[4]
    else:
      a = qi[4] + a
      
print( a )

### FIXED CODE ###

a = input()
q = int(input())

fflag = 0
ato = ""
mae = ""
for i in range(q):
  qi = input()
  if( qi == "1"):
    fflag += 1 
  else:
    if( fflag%2 == 0 ):
      if( qi[2] == "2" ):
        ato += qi[4]
      else:
        mae += qi[4]
    else:
      if( qi[2] == "2" ):
        mae += qi[4]
      else:
        ato += qi[4]      
    
a = mae[::-1] + a + ato    
    
if( fflag%2==0 ):
  print( a )
else:
  print( a[::-1] )
### BUGGY CODE ###

S=list(map(int,input()))
N=len(S)#S[0]~S[N-1]
count=0
j=0
def make_list(x,S):#x:元の配列から切り取る番号 S:リスト受け取り
    a=[]
    for i in range(0,x):#S[0]~S[x-1]までを追加
        a.append(S[i])
    if x<len(S)-2:
        for i in range(x+2,len(S)):
            a.append(S[i])
    return a
while j==0 and N!=1:
    for i in range(N-1):#S[0]~S[N-2]
        if (S[i]==0 and S[i+1]==1)or(S[i]==1 and S[i+1]==0):
            count+=2
            S=make_list(i,S)#Sの書き換え
            N=len(S)#Nの書き換え
            if N==0:
                j=1
            break
        elif i==N-2:
            j=1
print(count)

### FIXED CODE ###

S=list(map(int,input()))
a=0
b=0
for i in range(len(S)):
    if S[i]==1:
        a+=1
    else:
        b+=1
print(2*min(a,b))
### BUGGY CODE ###

N,A=map(int, input().split())
x=[int(x) for x in input().split()]
W=sum(x)
dp=[[[0]*(W+1) for _ in range(N+1)] for _ in range(N+1)]
for j in range(N+1):
    dp[j][0][0]=1
for j in range(1,N+1):
    xj=x[j-1]
    for k in range(1, N+1):
        for s in range(1, W+1):
            if s<xj:
                dp[j][k][s]=dp[j-1][k][s]
            else:
                dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-xj]

ans=0
for k in range(1,N+1):
    if k*A<=W:
        ans+=dp[N][k][k*A]
print(ans)


### FIXED CODE ###

import sys
from sys import stdin
input = stdin.readline

def solve(N, A, x):
    W=sum(x)
    dp=[[[0]*(W+1) for _ in range(N+1)] for _ in range(N+1)]
    for j in range(N+1):
        dp[j][0][0]=1
    for j in range(1,N+1):
        xj=x[j-1]
        for k in range(1, N+1):
            for s in range(1, W+1):
                if s<xj:
                    dp[j][k][s]=dp[j-1][k][s]
                else:
                    dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-xj]

    ans=0
    for k in range(1,N+1):
        if k*A<=W:
            ans+=dp[N][k][k*A]
        else:
            break
    return ans


def main(args):
    N,A=map(int, input().split())
    x=[int(x) for x in input().split()]
    ans=solve(N,A,x)
    print(ans)

if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

import sys

S=input()
if len(S)<2: print(0),sys.exit()
elif len(S)==3:
    print(1 if S=="ABC" else 0)
    sys.exit()

s=[]
a=[]
x=ord("A")
l=len(S)
for i in range(l-2):
    s.append(ord(S[i])-x)
    if S[i:i+3]=="ABC": a.append(i)
s.append(ord(S[l-2])-x)
s.append(ord(S[l-1])-x)
s.append
a=[a[i] for i in range(len(a)-1,-1,-1)]


tmp=0
abc,bca=[0,1,2],[1,2,0]
ans=0
while True:
    if a==[] or a[-1]>=len(s)-2: break
    tmp=a[-1]
    if s[tmp]==0 and s[tmp+1]==1 and s[tmp+2]==2:
        s[tmp],s[tmp+1],s[tmp+2]=1,2,0
        a.append(tmp+2)
        if tmp>0 and s[tmp-1]==0: a.append(tmp-1)
        ans+=1
    else: a.pop(-1)

print(ans)

### FIXED CODE ###

import sys

S=input()
if len(S)<2: print(0),sys.exit()
elif len(S)==3:
    print(1 if S=="ABC" else 0)
    sys.exit()



s=[S[i] for i in range(len(S))]
tmp=0
abc,bca=["A","B","C"],["B","C","A"]
ans=0
a,bc=0,0
i=0
while i<len(s)-1:
    if s[i]=="A": a+=1
    elif s[i]=="B" and s[i+1]=="C":
        bc+=1
        i+=1
        ans+=a
    
    else:
        a,bc=0,0
    i+=1
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,W = map(int,input().split())
weight = []
val = []
for i in range(n):
    a,b = map(int,input().split())
    weight.append(a)
    val.append(b)
max_v = sum(val) + 10 # 全部使ったとしてもこれ以上の勝ちにはならない
# point : v < =10^3 でn <= 10^2なので、n**2 vでもOK
# wが使えないときには変数を入れ替える
INF = 10**12+7 #Wより大きな値
dp = [[INF]*(max_v+1) for i in range(n+1)]
#初期化は 価値が0になる最小の重さが0なので、dp[i][0] = 0
# 漸化式：dp[i+1][j] = min(dp[i][j],dp[i][j-v[i]]+w[i])
# i+1　は i番目までの品物を使うとする
# 先にどっちからループを回した方が良い？価値か、品数か
#　品数が全部埋まってから、価値を更新する方が楽そう
for i in range(n+1):
    dp[i][0] = 0
for i in range(n):
    for j in range(max_v+1):
        if j-val[i] >= 0:
            #print("yes")
            dp[i+1][j] = min(dp[i][j],dp[i][j-val[i]]+ weight[i])
        else: dp[i+1][j] = dp[i][j]
    if i == n-1:
        #print("Yes")
        #print(dp[i+1])
        #大きい方から見ていく
        for j in range(1,max_v+1):
            #print(j)
            if dp[i+1][-j] <= W:
                print(max_v - j + 1)
                break


### FIXED CODE ###

#!/usr/bin/env python3
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,W = map(int,input().split())
weight = []
val = []
for i in range(n):
    a,b = map(int,input().split())
    weight.append(a)
    val.append(b)
max_v = sum(val) + 10 # 全部使ったとしてもこれ以上の勝ちにはならない
# point : v < =10^3 でn <= 10^2なので、n**2 vでもOK
# wが使えないときには変数を入れ替える
INF = 10**12+7 #Wより大きな値
dp = [[INF]*(max_v+1) for i in range(n+1)]
#初期化は 価値が0になる最小の重さが0なので、dp[i][0] = 0
# 漸化式：dp[i+1][j] = min(dp[i][j],dp[i][j-v[i]]+w[i])
# i+1　は i番目までの品物を使うとする
# 先にどっちからループを回した方が良い？価値か、品数か
#　品数が全部埋まってから、価値を更新する方が楽そう
for i in range(n+1):
    dp[i][0] = 0
for i in range(n):
    for j in range(max_v+1):
        if j-val[i] >= 0:
            #print("yes")
            dp[i+1][j] = min(dp[i][j],dp[i][j-val[i]]+ weight[i])
        else: dp[i+1][j] = dp[i][j]
    if i == n-1:
        #print("Yes")
        #print(dp[i+1])
        #大きい方から見ていく
        for j in range(1,max_v+1):
            #print(j)
            if dp[i+1][-j] <= W:
                print(max_v - j + 1)
                break
### BUGGY CODE ###

from math import factorial

n, m = map(int, input().split())


ans = 1

if m != 1:
    factorization = {}
    while True:
        for i in range (2, m//2 + 1):
            if m % i == 0:
                if i in factorization:
                    factorization[i] += 1
                else:
                    factorization[i] = 1
                m = m // i
                break
        else:
            if m in factorization:
                    factorization[m] += 1
            else:
                factorization[m] = 1
            break


    for i in factorization.keys():
        k = factorization[i]

        num = 1
        for i in range(k):
            num *= (n+k-1-i)
        num //= factorial(k)
        ans *= num % (10**9+7)
        ans = ans % (10**9+7)



print(ans)





### FIXED CODE ###

from math import factorial, sqrt

n, m = map(int, input().split())


ans = 1

if m != 1:
    factorization = {}
    while True:
        for i in range (2, int(sqrt(m))+1):
            if m % i == 0:
                if i in factorization:
                    factorization[i] += 1
                else:
                    factorization[i] = 1
                m = m // i
                break
        else:
            if m in factorization:
                    factorization[m] += 1
            else:
                factorization[m] = 1
            break


    for i in factorization.keys():
        k = factorization[i]

        num = 1
        for i in range(k):
            num *= (n+k-1-i)
        num //= factorial(k)
        ans *= num % (10**9+7)
        ans = ans % (10**9+7)



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

N = int(input())
A = [int(input()) for _ in range(N)]

pnext = 1
pvisited = []
while True:
	pvisited.append(pnext)
	pnext = A[pnext - 1]
	if pnext == 2:
		print(len(pvisited))
		exit()
	if pnext in pvisited:
		print(-1)
		exit()


### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

count = 0
pnext = 1
while count < N:
	count += 1
	pnext = A[pnext - 1]
	if pnext == 2:
		print(count)
		break
else:
	print(-1)
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
for i in range(Q):
    l,r = map(int,input().split())
    new_S = S[l-1:r]
    print(new_S.count('AC'))

### FIXED CODE ###

import bisect

N,Q = map(int,input().split())
S = input()
L = []
for i in range(N):
    if S[i:i+2] == 'AC':
        L.append(i)
for i in range(Q):
    l,r = map(int,input().split())
    a = bisect.bisect_left(L,l-1)
    b = bisect.bisect_right(L,r-2)
    print(b-a)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
n,q = list(map(int,input().split()))
ball = list(map(int,input().split()))
 
h = Bit(n+1)

L_most = {}
J = [[] for _ in range(n+1)]
jump = {}
on = set()

for i,b in enumerate(ball):
  if b not in L_most:
    L_most[b]=i
    h.add(i+1,1)
    on.add(i+1)
  J[b].append(i)
    
for i in range(n+1):
  for j in range(len(J[i])):
    if j+1<len(J[i]):
      jump[J[i][j]+1] = J[i][j+1]+1

Q = []
 
for _ in range(q):
  l,r = list(map(int,input().split()))
  Q.append((l,r))
  
LOO = list(Q)
Q.sort(key=lambda x:x[0])

c = 1
ans = {}
#print(on)

for l,r in Q:
  for i in range(c,l):
    if i in on:
      on.remove(i)
      h.add(i,-1)
      if i in jump:
        dest = jump[i]
        h.add(dest,1)
        on.add(dest)

  tmp = h.sum(r)- h.sum(l-1)
  ans[(l,r)] = tmp
  c = l

for q in LOO:
  print(ans[q])
  
  

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
n,q = list(map(int,input().split()))
ball = list(map(int,input().split()))
 
h = Bit(n+1)

L = {}
jump = {}
on = set()

for i,b in enumerate(ball):
  if b not in L:
    h.add(i+1,1)
    on.add(i+1)
  if b in L:
    jump[L[b]]=i+1
  L[b] = i+1

Q = []
 
for _ in range(q):
  l,r = list(map(int,input().split()))
  Q.append((l,r))
  
LOO = list(Q)
Q.sort(key=lambda x:x[0])

c = 1
ans = {}

for l,r in Q:
  for i in range(c,l):
    if i in on:
      on.remove(i)
      h.add(i,-1)
      if i in jump:
        dest = jump[i]
        h.add(dest,1)
        on.add(dest)

  tmp = h.sum(r)- h.sum(l-1)
  ans[(l,r)] = tmp
  c = l

p = []
for q in LOO:
  p.append(ans[q])
  
print(*p, sep="\n")
### BUGGY CODE ###

import itertools
K, S = map(int, input().split())

ans = 0
for x in range(K+1):
    for y in range (K+1):
        for z in range(K+1):
            if x+y+z == S:
                ans +=1

print(ans)

### FIXED CODE ###

K, S = map(int, input().split())

ans = 0
for x in range(K+1):
    for y in range (K+1):
        if  0 <= S - x- y <= K:
            ans +=1

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

N=int(input())
A=[list(map(int,input().split())) for _ in range(N)]
finish=[0]*N
day=0
tired=[False]*N
while 1:
  day+=1
  battle=False
  for i in range(N):
    tired[i]=False
    if finish[i]==N-1:
      continue
    enemy=A[i][finish[i]]-1
    if i==A[enemy][finish[enemy]]-1 and i>enemy and not tired[enemy]:
      finish[enemy]+=1
      finish[i]+=1
      tired[enemy]=True
      tired[i]=True
      battle=True
      #print("day:{0},{1}vs{2}".format(day,i+1,enemy+1))
  if battle==False:
    day-=1
    break
if min(finish)<N-1:
  print(-1)
else:
  print(day)




### FIXED CODE ###

N=int(input())
A=[list(map(int,input().split())) for _ in range(N)]
wait=[[float("inf")]*N for _ in range(N)]
for i in range(N):
  wait[A[i][0]-1][i]=0
L=[list(range(N)),[]]
finish=[0]*N

day=0
ind=0
while L[ind]:
  battle=False
  day+=1
  for player in L[ind]:
    if finish[player]>=N-1:
      continue
    enemy=A[player][finish[player]]-1
    if wait[player][enemy]<day and wait[enemy][player]<day:
      battle=True
      #print("day{},{}vs{}".format(day,player+1,enemy+1))
      finish[player]+=1
      finish[enemy]+=1
      if finish[player]<N-1:
        wait[A[player][finish[player]]-1][player]=day
      if finish[enemy]<N-1:
        wait[A[enemy][finish[enemy]]-1][enemy]=day
      L[(ind+1)%2].append(player)
      L[(ind+1)%2].append(enemy)
  L[ind]=[]   
  ind=(ind+1)%2
  if not battle:
    day-=1
    break
if min(finish)<N-1:
  print(-1)
else:
  print(day)
### BUGGY CODE ###

n, k = [int(x) for x in input().split()]
hs = [int(x) for x in input().split()]
dp = [0] * (n+1)
for i in range(2, n + 1):
    mn = 10**10
    minIndex = max(1, i - k)
    for j in range(minIndex, i):
        v = dp[j] + abs(hs[i-1] - hs[j-1])
        mn = min(mn, v)
    dp[i] = mn
print(dp[n])


### FIXED CODE ###

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

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

dp = [0] * n

for i in range(1, min(k,n)):
	dp[i] = min([dpj + abs(hs[i] - hj) for dpj, hj in zip(dp[:i], hs[:i])])

if k < n:
	for i in range(k, n):
		dp[i] = min([dpj + abs(hs[i] - hj) for dpj, hj in zip(dp[i-k:i], hs[i-k:i])])

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

n = int(input())
V = list(map(int,input().split()))
a = [0]*10000000
b = [0]*10000000
v1=[]
v2=[]

if len(set(V)) == 1:
    print(n//2)

else:
    for i in range(n):
        if i%2 == 0:
            a[V[i]-1] += 1
            v1.append(V[i])
        else:
            b[V[i]-1] += 1
            v2.append(V[i])

    max1 = 0
    max2 = 0

    for j in range(len(a)):
        if max1 < a[j]:
            max1 = a[j]
            c1 = j
    for k in range(len(b)):
        if max2 < b[k]:
            max2=b[k]
            c2=k

    if c1 != c2:
        print(n-max1-max2)
    else:
        a.sort()
        b.sort()
        print(min(n-max1-b[-2],n-max2-a[-2]))


### FIXED CODE ###

from collections import Counter

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

Odd = Counter(S[::2]).most_common()+([(0,0)])
Even = Counter(S[1::2]).most_common()+([(0,0)])

if Odd[0][0] != Even[0][0]:
	print(n-Odd[0][1]-Even[0][1])
else:
	print(min(n-Odd[1][1]-Even[0][1],n-Odd[0][1]-Even[1][1]))
### BUGGY CODE ###

n = int(input())
s = input()
cnt = 0
for i in range(0, n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if s[i]!=s[j] and s[j]!=s[k] and s[i]!=s[k] and j-i!=k-j:
                cnt += 1
                
print(cnt)

### FIXED CODE ###

n = int(input())
s = input()
r = s.count('R')
g = s.count('G')
b = s.count('B')
ans = r*g*b
for i in range(n-2):
    for j in range(i+1, n-1):
        k = 2*j - i
        if k >= n:
            break 
        if s[i]!=s[j] and s[k]!= s[i] and s[j]!=s[k]:
            ans -= 1
print(ans)