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

N = int(input())
X = list(input())
 
 
def f(cnt):
    if (cnt > 0):
        p_count = bin(cnt).count('1')
        return f(cnt % p_count) + 1
    else:
        return 0
 
 
for i, x in enumerate(X):
    if (x == '1'):
        X[i] = '0'
        num = int(''.join(X), 2)
        print(f(num))
        X[i] = '1'
    else:
        X[i] = '1'
        num = int(''.join(X), 2)
        print(f(num))
        X[i] = '0'

### FIXED CODE ###

#!/usr/bin/env python3
N = int(input())
X = input()

x_num = int(X, 2)
cnt1 = X.count('1')

p_zero = x_num % (cnt1 + 1)
p_one = (x_num % (cnt1 - 1) if cnt1 - 1 > 0 else 1)


def f(cnt):
    if (cnt > 0):
        pcount = p_count(cnt)
        return f(cnt % pcount) + 1
    else:
        return 0


def p_count(x):
    cnt = 0
    while (x > 0):
        if x % 2 != 0:
            cnt += 1
        x //= 2
    return cnt


def f1(x):
    cnt = 0
    while (x > 0):
        x %= bin(x).count('1')
        cnt += 1
    return cnt


for i, x in enumerate(list(X)):
    if (x == '1'):
        #x_num = int(''.join(X), 2)
        if cnt1 - 1 > 0:
            xxx = (p_one - pow(2, (N - (i + 1)), cnt1 - 1)) % (cnt1 - 1)
            xxx += cnt1 - 1 if xxx < 0 else 0
            print(f1(xxx) + 1)
        else:
            print(0)
    else:
        #x_num = int(''.join(X), 2)
        xxx = (p_zero + pow(2, (N - (i + 1)), cnt1 + 1)) % (cnt1 + 1)
        xxx += cnt1 + 1 if xxx < 0 else 0
        print(f1(xxx) + 1)
### BUGGY CODE ###

def main():
    a, b, m = map(int, input().split())
    priceOfMicrowaves = list(map(int, input().split()))
    priceOfRefrigerators = list(map(int, input().split()))
    priceTable = [list(map(int,input().split())) for i in range(m)]
    cheepest = priceOfMicrowaves[0] + priceOfRefrigerators[0]
    for price in priceTable:
        if priceOfMicrowaves[price[0]-1]+priceOfRefrigerators[price[1]-1]-price[2] < cheepest:
            cheepest = priceOfMicrowaves[price[0]-1]+priceOfRefrigerators[price[1]-1]-price[2]
    for p in priceOfMicrowaves:
        if p >= cheepest:
            continue
        for q in priceOfRefrigerators:
            if q >= cheepest:
                continue
            if p + q < cheepest:
                cheepest = p + q
    print(cheepest)
    
main()

### FIXED CODE ###

a, b, m = map(int, input().split())
priceOfMicrowaves = list(map(int, input().split()))
priceOfRefrigerators = list(map(int, input().split()))
priceTable = [list(map(int,input().split())) for i in range(m)]
cheepest = priceOfMicrowaves[0] + priceOfRefrigerators[0]
for price in priceTable:
    if priceOfMicrowaves[price[0]-1]-price[2] >= cheepest:
        continue
    elif priceOfRefrigerators[price[1]-1]-price[2] >= cheepest:
        continue
    elif priceOfMicrowaves[price[0]-1]+priceOfRefrigerators[price[1]-1]-price[2] < cheepest:
        cheepest = priceOfMicrowaves[price[0]-1]+priceOfRefrigerators[price[1]-1]-price[2]
if cheepest > min(priceOfMicrowaves) + min(priceOfRefrigerators):
    cheepest = min(priceOfMicrowaves) + min(priceOfRefrigerators)
print(cheepest)
### BUGGY CODE ###

MOD = 10 ** 9 + 7
n, m = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))

# 前計算
for i in range(n - 1):
    x[i] = x[i + 1] - x[i]

for i in range(m - 1):
    y[i] = y[i + 1] - y[i]

N = [n - 1]
for i in range((n)//2 - 1):
    N.append((N[i] + (n - 1 - 2 * (i + 1))) % MOD)

M = [m - 1]
for i in range((m)//2 - 1):
    M.append((M[i] + (m - 1- 2 * (i + 1))) % MOD)

if N[0] % 2 == 0:
    N += N[::-1]
elif N[0] != 1:
    N += N[1::-1]
if M[0] % 2 == 0:
    M += M[::-1]
elif M[0] != 1:
    M += M[1::-1]

# print (x)
# print (y)
# print (N)
# print (M)

if len(x) - 1 != len(N):
    while True:
        pass

if len(y) - 1 != len(M):
    while True:
        pass


X_sum = 0
for i in range(n - 1):
    X_sum += x[i] * N[i]
    X_sum %= MOD

Y_sum = 0
for i in range(m - 1):
    Y_sum += y[i] * M[i]
    Y_sum %= MOD

print ((X_sum * Y_sum) % MOD)

### FIXED CODE ###

MOD = 10 ** 9 + 7
n, m = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))

# 前計算
for i in range(n - 1):
    x[i] = x[i + 1] - x[i]

for i in range(m - 1):
    y[i] = y[i + 1] - y[i]

N = [n - 1]
for i in range(n - 3, 0, -2):
    N.append(N[-1] + i)
    # N.append((N[i] + (n - 1 - 2 * (i + 1))) % MOD)

M = [m - 1]
for i in range(m - 3, 0, -2):
    M.append(M[-1] + i)
    # M.append((M[i] + (m - 1- 2 * (i + 1))) % MOD)

if N[0] % 2 == 0:
    N += N[::-1]
elif N[0] != 1:
    N += N[-2::-1]

if M[0] % 2 == 0:
    M += M[::-1]
elif M[0] != 1:
    M += M[-2::-1]

# print (x)
# print (y)
# print (N)
# print (M)

if len(x) - 1 > len(N):
    while True:
        pass

if len(y) - 1 > len(M):
    while True:
        pass


X_sum = 0
for i in range(n - 1):
    X_sum += x[i] * N[i]
    X_sum %= MOD

Y_sum = 0
for i in range(m - 1):
    Y_sum += y[i] * M[i]
    Y_sum %= MOD

print ((X_sum * Y_sum) % MOD)
### BUGGY CODE ###

from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7




def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    f = list(map(int, input().split()))
    a.sort()
    f = sorted(f,reverse=True)

    def ok(v):
        cnt = 0
        sa = 0
        for i in range(n):
            t = a[i]*f[i]
            if v - t >= 0:
                continue
            cnt += a[i] - (v//f[i])
        
        if cnt <= k:
            return True
        else:
            return False





    l, r = 0, 10 ** 19
    for i in range(200):
        m = (l + r) / 2
        if ok(m):
            r = m
        else:
            l = m
    print(int(m))

    
            
    

    

    

if __name__ == '__main__':
    main()


### FIXED CODE ###

from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7




def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    f = list(map(int, input().split()))
    a.sort()
    f = sorted(f,reverse=True)

    def ok(v):
        cnt = 0
        sa = 0
        for i in range(n):
            t = a[i]*f[i]
            if v - t >= 0:
                continue
            cnt += a[i] - (v // f[i])
            if cnt > k:
                return False
        
        if cnt <= k:
            return True
        else:
            return False





    l, r = 0, 10 ** 18
    for i in range(80):
        m = (l + r) // 2
        if ok(m):
            r = m
        else:
            l = m
    print(r)

    
            
    

    

    

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

s=input()
n=len(s)
if n%2==1:
  print("No")
  exit()
while 1==1:
  if s[:2]=="hi":
    s=s[2:]
  elif len(s)==0:
    print("Yes")
    exit()
  else:
    print("No")

### FIXED CODE ###

s=input()
n=len(s)
if n%2==1:
  print("No")
  exit()
while 1==1:
  if s[:2]=="hi":
    s=s[2:]
  elif len(s)==0:
    print("Yes")
    exit()
  else:
    print("No")
    exit()
### BUGGY CODE ###

n, m = map(int, input().split())
h = list(map(int, input().split()))
h = [[i, h[i-1]] for i in range(1, n+1)]
path = [list(map(int, input().split())) for i in range(m)]
conn = {key: [] for key in range(1, n+1)}
tower = list(range(1, n+1))


for p in path:
    # h0 > h1
    if h[p[0]-1][1] == h[p[1]-1][1]:
        conn[p[0]].append(p[1])
        conn[p[1]].append(p[0])
    elif h[p[0]-1][1] > h[p[1]-1][1]:
        conn[p[0]].append(p[1])
    else:
        conn[p[1]].append(p[0])

h.sort(key=lambda x: x[1], reverse=True)
for t in h:
    c = set(conn[t[0]])
    for i in c:
        if i in tower:
            tower.remove(i)
print(len(tower), end="")


### FIXED CODE ###

n, m = map(int, input().split())
h = list(map(int, input().split()))
# h = [[i, h[i-1]] for i in range(1, n+1)]
# path = [list(map(int, input().split())) for i in range(m)]
# conn = {key: [] for key in range(1, n+1)}
tower = list(range(1, n+1))
ma = [0]*n

for i in range(m):
    p = list(map(int, input().split()))
    ma[p[0]-1] = max(ma[p[0]-1], h[p[1]-1])
    ma[p[1]-1] = max(ma[p[1]-1], h[p[0]-1])
    """
    # h0 > h1
    if h[p[0]-1] == h[p[1]-1]:
        if p[0] in tower:
            tower.remove(p[0])
        if p[1] in tower:
            tower.remove(p[1])
    elif h[p[0]-1] > h[p[1]-1]:
        if p[1] in tower:
            tower.remove(p[1])
    else:
        if p[0] in tower:
            tower.remove(p[0])
    """
cnt = 0
for i in range(n):
    cnt += (h[i] > ma[i])
print(cnt, end="")
### BUGGY CODE ###

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

total = 1
for n in A:
    total *= n
print(total if total <= 10 ** 18 else -1)

### FIXED CODE ###

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

if 0 in A:
    print(0)
else:
    ans = 1
    a = sorted(A, reverse=True)
    for i in a:
        ans *= i
        if ans > 10 ** 18:
            print(-1)
            break
    else:
        print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

input_line = list(map(int,input().split()))
input_hp = list(map(int,input().split()))
try:
    [(input_hp.sort(reverse=True) ,input_hp.pop(_)) for _ in range(input_line[1])]
    print(sum(input_hp))
except IndexError:
    print('0')

### FIXED CODE ###

input_line = list(map(int,input().split()))
input_hp = list(map(int,input().split()))

if input_line[0] <= input_line[1]:
    print('0')
else:
    input_hp.sort()
    result_input_hp = len(input_hp) - input_line[1]
    sum_total = sum(input_hp[:result_input_hp])
    print(sum_total)
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))

    flag = True
    count = 0
    for i in a:
        if(i%2 == 1):
            flag = False

    while flag == True:
        count += 1
        a = list(map( lambda x: int(x/2), a))
        for i in a:
            if(i%2 != 0):
                False
    
    print(count)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))

    flag = True
    count = 0
    for i in a:
        if(i%2 == 1):
            flag = False

    while flag == True:
        count += 1
        a = list(map( lambda x: int(x/2), a))
        for i in a:
            if(i%2 != 0):
                flag = False
    
    print(count)

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

N=int(input()) 
import math
A=list(map(int, input().split())) 
k =  len(bin(max(A))[2:])
mod = 10**9+7

c = [0]*k

for i in A:
  bit = bin(i)[2:].zfill(k)
  for j in range(k):
    if bit[j] == '1':
      c[-1-j] +=1
      
ans = 0
for i in range(k):
  ans = (ans +(2**i)*(c[i]*(N-(c[i]))))%mod
  
print(ans)
  
  
  
  




### FIXED CODE ###

N=int(input()) 
import math
A=list(map(int, input().split())) 
k =  len(bin(max(A))[2:])
mod = 10**9+7

c = [0]*k

for i in A:
  bit = bin(i)[2:].zfill(k)
  for j in range(k):
    if bit[j] == '1':
      c[-1-j] +=1
      
ans = 0
for i in range(k):
  ans = (ans +(2**i)*(c[i]*(N-(c[i]))))%mod
  
print(ans)
### BUGGY CODE ###

# coding:utf-8

import sys

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()


N, W = LI()
L = [LI() for _ in range(N)]

dp = [[0] * (W + 1) for _ in range(N + 1)]
for i in range(N):
    weight, value = L[i]
    for w in range(W + 1):
        if w - weight >= 0:
            dp[i + 1][w] = max(dp[i][w], dp[i][w - weight] + value)
        else:
            dp[i + 1][w] = dp[i][w]

print(dp[N][W])


### FIXED CODE ###

# coding:utf-8

import sys

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()


N, W = LI()
L = [LI() for _ in range(N)]

# dp[w]: 容量wのナップザックの価値の総和の最大値
dp = [0] * (W + 1)
for weight, value in L:
    for w in range(W + 1)[::-1]:
        if w - weight < 0:
            continue
        dp[w] = max(dp[w], dp[w - weight] + value)

print(dp[W])
### BUGGY CODE ###

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

judge = [1]*N
for i in range(N):
  for j in range(i):
    if P[i] > P[j]:
      judge[i] = 0
print(judge.count(1))

### FIXED CODE ###

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

ans = 1
tmp = P[0]
for i in range(1,N):
  if P[i] <= tmp:
    ans+=1
    tmp = P[i]
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
for i in range(1,N+1):
    print(A.count(i))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=[0]*N
for i in A:
    ans[i-1]+=1
for j in ans:
    print(j)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

K = int(input())


# 1,,,9をenqueue
queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]

x = 0
i = 0
# K回繰り返す
while i < K:
    # x = dequeue
    x = queue.pop(0)

    one = x % 10
    # xの一桁目が0でなければ(x * 10 + xの一桁目に1加算した値)をenqueue
    if one != 0:
        queue.append(x * 10 + one - 1)

    # x * 10をenqueue
    queue.append(x * 10 + one)

    # xの一桁目が9でなければ(x * 10 - xの一桁目から1減算した値)をenqueue
    if one != 9:
        queue.append(x * 10 + one + 1)

    i += 1

# xが答え
print(x)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import queue

K = int(input())


# 1,,,9をenqueue
q = queue.Queue()
for i in range(1, 10):
    q.put(i)

x = 0
i = 0
# K回繰り返す
while i < K:
    # x = dequeue
    x = q.get()

    one = x % 10
    # xの一桁目が0でなければ(x * 10 + xの一桁目に1加算した値)をenqueue
    if one != 0:
        q.put(x * 10 + one - 1)

    # x * 10をenqueue
    q.put(x * 10 + one)

    # xの一桁目が9でなければ(x * 10 - xの一桁目から1減算した値)をenqueue
    if one != 9:
        q.put(x * 10 + one + 1)

    i += 1

# xが答え
print(x)
### BUGGY CODE ###

from sys import stdin

# input
[n] = [int(x) for x in stdin.readline().rstrip().split()]
s = []
for i in range(n):
    raw = list(str(stdin.readline().rstrip()))
    raw.sort()
    s.append("".join(raw))

c = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        if i > j:
            continue
        if s[i] == s[j]:
            c += 1
print(c)


### FIXED CODE ###

from collections import defaultdict, Counter
from heapq import heapify, heappop, heappush
from sys import stdin
 
def main():
    n = int(input())
    S = ["".join(sorted(input())) for _ in range(n)]

    ans = 0
    dd = defaultdict(int)
    for s in S:
        ans += dd[s]
        dd[s] += 1
    print(ans)
 
input = lambda: stdin.readline().rstrip()
main()
### BUGGY CODE ###

k,s = map(int, input().split())
count = 0
for i in range(0,k+1,1):
  for j in range(0,k+1,1):
    for k in range(0,k+1,1):
      if i+j+k == s:
        count = count+1
print(count)

### FIXED CODE ###

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

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


m = max(a)
for i in range(100):
    if 2**i>m:
        n = i
        break


mat = []
for j in a:
    b=[1 if j >> i &1 else 0 for i in reversed(range(n))] 
    mat.append(b)


for i in range(n):
    f = [part[i] for part in mat]
    if sum(f)%2==0:
        ans = f
#         print(ans)
    else:
        ans = [1 if j==0 else 0 for j in f]
#         print(ans)
    for j in range(len(ans)):
        mat[j][i] = ans[j]
res = []
for m in mat:
    ans = 0
    for i in range(len(m)):
        ans += 2**i*m[-i-1]
    
    res.append(ans)
print(" ".join(map(str,res)))

### FIXED CODE ###

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


m = max(a)
for i in range(100):
    if 2**i>m:
        n = i
        break


mat = []
for j in a:
    b=[1 if j >> i &1 else 0 for i in reversed(range(n))] 
    mat.append(b)


for i in range(n):
    f = [part[i] for part in mat]
    if sum(f)%2==0:
        ans = f
#         print(ans)
    else:
        ans = [1 if j==0 else 0 for j in f]
#         print(ans)
    for j in range(len(ans)):
        mat[j][i] = ans[j]
res = []
for m in mat:
    ans = 0
    for i in range(len(m)):
        ans += 2**i*m[-i-1]
    
    res.append(ans)
print(" ".join(map(str,res)))
### BUGGY CODE ###

H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
#print(S)
idx = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == '.':
      S[i][j] = idx
      idx += 1
#print(S)
D = [[float('inf') for _ in range(idx)] for _ in range(idx)]
for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      continue
    for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
      if 0 <= i+dy < H and 0 <= j+dx < W and S[i+dy][j+dx] != '#':
        D[S[i][j]][S[i+dy][j+dx]] = 1
        D[S[i+dy][j+dx]][S[i][j]] = 1
for i in range(idx):
  D[i][i] = 0

for k in range(idx):
  for i in range(idx):
    for j in range(idx):
      D[i][j] = min(D[i][k]+D[k][j],D[i][j])
#print(D)
ans = 0
for d in D:
  ans = max(max(d),ans)
print(ans)

### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline
  
  H,W = map(int,input().split())
  S = [list(input()) for _ in range(H)]
  #print(S)
  idx = 0
  for i in range(H):
    for j in range(W):
      if S[i][j] == '.':
        S[i][j] = idx
        idx += 1
  #print(S)
  D = [[float('inf') for _ in range(idx)] for _ in range(idx)]
  for i in range(H):
    for j in range(W):
      if S[i][j] == '#':
        continue
      for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
        if 0 <= i+dy < H and 0 <= j+dx < W and S[i+dy][j+dx] != '#':
          D[S[i][j]][S[i+dy][j+dx]] = 1
          D[S[i+dy][j+dx]][S[i][j]] = 1
  for i in range(idx):
    D[i][i] = 0
  
  for k in range(idx):
    for i in range(idx):
      for j in range(idx):
        D[i][j] = min(D[i][k]+D[k][j],D[i][j])
  #print(D)
  ans = 0
  for d in D:
    ans = max(max(d),ans)
  print(ans)

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

import numpy as np

n,m,k=map(int,input().split())
a=np.array(list(map(int,input().split())))
b=np.array(list(map(int,input().split())))

ak=np.cumsum(a,dtype=np.int64)
bk=np.cumsum(b,dtype=np.int64)
ak=ak[ak<=k]
bk=bk[bk<=k]
lak=len(ak)
lbk=len(bk)

an=lak
j=0
for i in range(lak-1,-1,-1):
    while bk[j]+ak[i]<=k:
        an=max(an,i+j+2)
        j+=1
        if j>=lbk:
            j=0
            break
an=max(an,lbk)

print(an)

### FIXED CODE ###

import numpy as np

n,m,k=map(int,input().split())
a=np.array(list(map(int,input().split())))
b=np.array(list(map(int,input().split())))

ak=np.cumsum(a,dtype=np.int64)
bk=np.cumsum(b,dtype=np.int64)
ak=ak[ak<=k]
bk=bk[bk<=k]
lak=len(ak)
lbk=len(bk)

an=lak
j=0
for i in range(lak-1,-1,-1):
    while bk[j]+ak[i]<=k:
        an=max(an,i+j+2)
        j+=1
        if j>=lbk:
            j-=1
            break
an=max(an,lbk)

print(an)
### BUGGY CODE ###

import bisect,sys
n = int(input())
A = [int(input()) for i in range(n)]
tmp = [A[0]]
if n == 1:
  print(1)
  sys.exit()
for a in A[1:]:
  if a <= min(tmp):
    tmp.insert(0,a)
  else:
    tmp[bisect.bisect_left(tmp,a)-1] =a
print(len(tmp))

### FIXED CODE ###

import bisect
n = int(input())
a = [- int(input()) for i in range(n)]
tmp = [a[0]]
for i in range(1,n):
  idx=bisect.bisect_right(tmp,a[i])
  if idx==len(tmp):
    tmp.append(a[i])
  else:
    tmp[idx] =a[i]
print(len(tmp))
### BUGGY CODE ###

mod = 10**9+7
n, k = [ int(v) for v in input().split() ]
a_list = [ int(v) for v in input().split() ]

dp_list = [ 0 for i in range(k+1) ]
dp_list[0] = 1

for i in range(n):
    new_dp_list = [ 0 for i in range(k+1) ]
    for j in range(k+1):
        for h in range(a_list[i]+1):
            if j+h <= k:
                new_dp_list[j+h] += dp_list[j]
    dp_list = [ i % mod for i in new_dp_list ]

print(dp_list[-1])

### FIXED CODE ###

def cumsum(inlist):
    s = 0
    outlist = [0]
    for i in inlist:
        s += i
        outlist.append(s)
    return outlist

mod = 10**9+7
n, k = [ int(v) for v in input().split() ]
a_list = [ int(v) for v in input().split() ]

dp_list = [ 0 for i in range(k+1) ]
dp_list[0] = 1

for i in range(n):
    cum_dp_list = cumsum(dp_list)

    new_dp_list = [ 0 for i in range(k+1) ]
    for j in range(k+1):
        r = min(j+1,k+1)
        l = max(0,j-a_list[i]) 
        new_dp_list[j] = cum_dp_list[r] - cum_dp_list[l]
    dp_list = [ i % mod for i in new_dp_list ]

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


from collections import defaultdict
from collections import deque

def main():
        
    N = int(input())
    """
    before[(i,j)]
    iとjの試合より前に終わらせておく必要のある直前の対戦者の組の数

    nxt[(i,j)]
    iとjの試合より後に行える対戦者の組

    例２
    4
    2 3 4
    1 3 4
    4 1 2
    3 1 2
    について、
    before[(1,3)] = 2
    before[(1,4)] = 2
    nxt[(1,2)] = set((1,3), (2,3))
    みたいな
    """
    before = defaultdict(int)
    #nxt = defaultdict(set)
    nxt = defaultdict(list)

    A = [list(map(int, input().split())) for _ in range(N)]

    for i in range(N):

        for j,a in enumerate(A[i]):
            l, h = min(i+1, a), max(i+1, a)
            if j != 0:
                before[(l,h)] += 1
                #nxt[b].add((l,h))
                nxt[b].append((l,h))
            b = (l,h)



    match_today = deque()
    checked = defaultdict(bool)
    for i in range(N):
        l,h = min(i+1, A[i][0]), max(i+1, A[i][0])
        #print(l,h, before[(l,h)])
        if before[(l,h)] == 0 and not checked[(l,h)]:
            match_today.append((l,h))
            checked[(l,h)] = True

    """
    for i in range(1, N):
        for j in range(i+1, N+1):
            if before[(i, j)] == 0:
                match_today.append((i,j))
    """
                

    
    ans = 0
    cnt_match = 0 
    f = True
    while f:
        f = False
        #print( match_today)
        ans += 1
        
        for _ in range(len(match_today)):
            l,h = match_today.popleft()
            cnt_match += 1
            for nl, nh in nxt[(l,h)]:
                before[(nl, nh)] -= 1
                
                if before[(nl, nh)] == 0:
                    match_today.append((nl, nh))
                    f = True
        
       


    if cnt_match == N*(N-1) // 2:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()


### FIXED CODE ###


from collections import deque

N = int(input())
match_order = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]


q = deque(range(N))
finish_by = [0] * N
next_opponent = [None] * N

while q:
    a = q.popleft()
    # aの残りの順で一番初めに戦う対戦相手を取り出す
    b = match_order[a].popleft()
    if next_opponent[b] == a:
        finish_by[a] = finish_by[b] = max(finish_by[a], finish_by[b]) + 1
        # a,bについて、まだ対戦相手が残っているならキューに積む
        if match_order[a]:
            q.append(a)
        if match_order[b]:
            q.append(b)
    # bの残りの順で戦う相手がaではないなら、順番が来るまで待つ
    else:
        next_opponent[a] = b

# 対戦相手が残っている人がいる場合、条件通りに終わることができない
if any(match_order):
    print(-1)
else:
    print(max(finish_by))
### BUGGY CODE ###




def start_process(length, q_num, char):
    for i in range(q_num):
        start_ind, fin_ind = map(int, input().split())
        now_str = char[start_ind - 1:fin_ind]
        print(now_str.count('AC'))



def main():
    length, q_num = map(int, input().split())
    char = input()
    start_process(length, q_num, char)

if __name__ == '__main__':
    main()


### FIXED CODE ###




def start_process(length, q_num, char):
    data = [0 for i in range(length + 1)]
    char = list(char)

    for i in range(1, length):
        if char[i] == 'C' and char[i - 1] == 'A':
            data[i] = data[i - 1] + 1
        else:
            data[i] = data[i - 1]

    for i in range(q_num):
        start_ind, fin_ind = map(int, input().split())
        print(data[fin_ind - 1] - data[start_ind - 1])


def main():
    length, q_num = map(int, input().split())
    char = input()
    start_process(length, q_num, char)

if __name__ == '__main__':
    main()