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

h,w,d = [int (i) for i in input().split()]
index = [[0,0] for i in range(h*w)]
sum = 0
for i in range(h):
    temp = [int(i) for i in input().split()]
    for j in range(w):
        index[temp[j]-1][0] = i
        index[temp[j]-1][1] = j
q = int(input())
for i in range(q):
    sum = 0
    a,b = [int (i) for i in input().split()]
    c = (b-a)//d
    for i in range(c):
        sum += abs(index[a-1][0] - index[a+d-1][0])+abs(index[a-1][1] - index[a+d-1][1])
        a += d
    print(sum)

### FIXED CODE ###

h,w,d = [int (i) for i in input().split()]
index = [[0,0] for i in range(h*w)]
sum = 0
for i in range(h):
    temp = [int(i) for i in input().split()]
    for j in range(w):
        index[temp[j]-1][0] = i
        index[temp[j]-1][1] = j
q = int(input())
dick = [0 for i in range (h*w)]
for i in range (d,h*w):
    dick[i] = dick[i-d] + abs(index[i][0]-index[i-d][0])+abs(index[i][1]-index[i-d][1])
for i in range(q):
    a,b = [int(i) for i in input().split()]
    print(dick[b-1] - dick[a-1])
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,weight=map(int,input().split())
    WV=[tuple(map(int,input().split())) for i in range(n)]
    dp=[[0]*(weight+1) for _ in range(n+1)] #品物iまでについて，ナップサックの重さの総和がjのときの価値の総和
    for i in range(n):
        ni=i+1
        w,v=WV[ni-1]
        for j in range(weight+1):
            dp[ni][j]=max(dp[ni][j],dp[i][j])
            if j+w<=weight and (j==0 or dp[i][j]>0):
                dp[ni][j+w]=max(dp[ni][j+w],dp[i][j]+v)
    print(max(dp[n]))
            



if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,weight=map(int,input().split())
    WV=[tuple(map(int,input().split())) for i in range(n)]
    dp=[[0]*(weight+1) for _ in range(n+1)] #品物iまでについて，ナップサックの重さの総和がjのときの価値の総和
    for i in range(n):
        ni=i+1
        w,v=WV[ni-1]
        for j in range(weight+1):
            dp[ni][j]=max(dp[ni][j],dp[i][j])
            if j+w<=weight and (j==0 or dp[i][j]>0):
                dp[ni][j+w]=max(dp[ni][j+w],dp[i][j]+v)
    print(max(dp[n]))
            



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

n,m,k = map (int,input().split())
def comb(n, r, mod):
  a = 1
  b = 1
  r = min(r, n - r)
  for i in range(r):
    a = a * (n - i) % mod
    b = b * (i + 1) % mod
  return a * pow(b, mod - 2, mod) % mod
mod = 998244353
ans = 0
for i in range(k+1):

    ans += (comb (n-1,i,mod) * pow(m-1,n-1-i,mod) * m) % mod
print(ans % mod)

### FIXED CODE ###

n,m,k = map (int,input().split())
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p


p = 998244353
N = n-1  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

mod = 998244353
ans = 0
#if k <=  n//2:
for i in range(k+1):
    ans += (cmb(n-1,i,mod) * pow(m-1,n-1-i,mod) * m) % mod
print(ans % mod)
### BUGGY CODE ###

# 結局は木+1辺
from collections import defaultdict
from itertools import count

N = int(input())
P = list(map(lambda x:int(x)-1,input().split()))
D = [0]*N
for p in P:
  D[p] += 1

rE = defaultdict(list)
for i,p in enumerate(P):
  rE[p] += [i]

S = [p for p in range(N) if D[p] == 0]
L = [None]*N

while S:
  n = S.pop()
  prev = set(L[a] for a in rE[n])
  if prev:
    for i in count():
      if i not in prev:
        L[n] = i
  else:
    L[n] = 0
  
  m = P[n]
  D[m] -= 1
  if D[m] == 0:
    S.append(m)

# cycle check
try:
  start = D.index(1)
except ValueError:
  print('POSSIBLE')
  exit()

def helper(n):
  s = set(L[a] for a in rE[n] if L[a] is not None)
  rlt = []
  for i in count():
    if i not in s:
      rlt.append(i)
      if len(rlt) >= 2:
        return rlt

s1,s2 = helper(start)
G = []
n = P[start]
while n != start:
  G.append(helper(n))
  n = P[n]


del N,P,D,rE,S,L


# 可能な初期値をそれぞれシミュレート
# 1
n = s1
for g in G:
  if g[0] == n:
    n = g[1]
  else:
    n = g[0]
if n != s1:
  print('POSSIBLE')
  exit()

# 2
n = s2
for g in G:
  if g[0] == n:
    n = g[1]
  else:
    n = g[0]
if n == s1:
  print('POSSIBLE')
  exit()

print('IMPOSSIBLE')

### FIXED CODE ###

# 結局は木+1辺
from collections import defaultdict
import heapq as hq

N = int(input())
P = list(map(lambda x:int(x)-1,input().split()))
D = [0]*N
for p in P:
  D[p] += 1

child_L = defaultdict(list)

S = [p for p in range(N) if D[p] == 0]
L = [None]*N

while S:
  n = S.pop()

  q = child_L[n]
  del child_L[n]

  hq.heapify(q)
  i = 0
  while q:
    t = hq.heappop(q)
    if i < t:
      break
    else:
      i += (i==t)
  
  L[n] = i
  m = P[n]
  child_L[m].append(i)
  D[m] -= 1
  if D[m] == 0:
    S.append(m)

# cycle check
try:
  start = D.index(1)
except ValueError:
  print('POSSIBLE')
  exit()

def helper(n):
  q = child_L[n]
  del child_L[n]
  
  hq.heapify(q)
  i = 0
  while q:
    t = hq.heappop(q)
    if i < t:
      break
    else:
      i += (i==t)

  j = i+1
  while q:
    t = hq.heappop(q)
    if j < t:
      break
    else:
      j += (j==t)

  return (i,j)


s1,s2 = helper(start)
G = []
n = P[start]
while n != start:
  G.append(helper(n))
  n = P[n]


del N,P,D,child_L,S,L


# 可能な初期値をそれぞれシミュレート
# 1
n = s1
for g in G:
  if g[0] == n:
    n = g[1]
  else:
    n = g[0]
if n != s1:
  print('POSSIBLE')
  exit()

# 2
n = s2
for g in G:
  if g[0] == n:
    n = g[1]
  else:
    n = g[0]
if n == s1:
  print('POSSIBLE')
  exit()

print('IMPOSSIBLE')
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

def cur(x):
    for i in neighbor[x]:
        ans[i]+=ans[x]
        neighbor[i].remove(x)
        cur(i)

n,q=map(int,input().split())
neighbor=[[]  for _ in range(n+1)]
ans=[0]*(n+1)

for _ in range(n-1):
    a,b=map(int,input().split())
    neighbor[a].append(b)
    neighbor[b].append(a)


for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x

cur(1)
print(*ans[1:])

### FIXED CODE ###

n,q=map(int,input().split())
neighbor=[[]  for _ in range(n+1)]
ans=[0]*(n+1)

for _ in range(n-1):
    a,b=map(int,input().split())
    neighbor[a].append(b)
    neighbor[b].append(a)


for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x

visit=[True]*(n+1)
tmp=[1]
for x in tmp:
    visit[x]=False
    for y in neighbor[x]:
        if visit[y]:
            tmp.append(y)
            ans[y]+=ans[x]

print(*ans[1:])
### BUGGY CODE ###

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

ans = 0
for i in range(0, n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if j-i == k-j: continue
            x = s[i] + s[j] + s[k]
            c = x.count('R') * x.count('G') * x.count('B')
            if c == 1: ans += 1
print(ans)

### FIXED CODE ###

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

r = s.count('R')
g = s.count('G')
b = s.count('B')

count = 0
#count second conditions satisfied
for i in range(n):
    for j in range(i+1,n):
        #search j - i = k - j ⇔ k = 2 * j - i
        k = 2 * j - i
        if k >= n: break
        if s[i] != s[j] and s[j] != s[k] and s[i] != s[k]: count += 1
print((r * g * b) - count)
### BUGGY CODE ###

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

s = [0]
for i in range(n):
    s.append((s[-1]+l[i])%m)
s.sort()

ans = 0
while s:
    cnt = s.count(s[0])
    s = s[cnt:]
    ans += cnt*(cnt-1)//2

print(ans)

### FIXED CODE ###

from collections import Counter

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

s = [0]
for i in range(n):
    s.append((s[-1]+l[i])%m)

c = Counter(s)

ans = 0
for x in c.values():
    ans += x*(x-1)//2

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

import sys
from pprint import pprint

R,C,K=map(int,input().split())

grid=[[0]*C for _ in range(R+1)]
for _ in range(K):
    r,c,v=map(int,input().split())
    grid[r][c-1]=v

for i in range(1,R+1):
    cell=[0]*4
    for j in range(C):
        cell[0]=max(cell[0],grid[i-1][j])
        for k in range(2,-1,-1):
            cell[k+1]=max(cell[k+1],cell[k]+grid[i][j])
        grid[i][j]=max(cell)

print(grid[-1][-1])


### FIXED CODE ###

import sys
from pprint import pprint

R,C,K=map(int,input().split())

grid=[[0]*C for _ in range(R+1)]
for _ in range(K):
    r,c,v=map(int,input().split())
    grid[r][c-1]=v

for i in range(1,R+1):
    cell=[0]*4
    for j in range(C):
        cell[0]=max(cell[0],grid[i-1][j])
        for k in range(2,-1,-1):
            cell[k+1]=max(cell[k+1],cell[k]+grid[i][j])
        grid[i][j]=max(cell)

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

import collections
import numpy as np

h, w, m = map(int, input().split())
lst_ = []
for i in range(m):
    h, m = map(int, input().split())
    lst_.append([h, m])

lst = np.array(lst_)
h_lst = collections.Counter(lst[:,0])
w_lst = collections.Counter(lst[:,1])

def get_cand(sub_lst):
    sub_lst = sub_lst.most_common()
    cand = []
    for sub in sub_lst:
        if sub[1] != sub_lst[0][1]:
            break
        cand.append(sub[0])
    return cand, sub_lst[0][1]

h_cand, h_count = get_cand(h_lst)
w_cand, w_count = get_cand(w_lst)

flag = False
for h in h_cand:
    if flag:
        break
    for w in w_cand:
        if not [h,w] in lst_:
            #print("bomber: ", h_count, w_count)
            flag = True
            break
ans = h_count + w_count
if flag:
    print(ans)
else:
    print(ans-1)





### FIXED CODE ###

import collections
import numpy as np

h, w, m = map(int, input().split())
lst_ = []
h_lst = [0]*h
w_lst = [0]*w
for i in range(m):
    h_, w_ = map(int, input().split())
    lst_.append([h_, w_])
    h_lst[h_-1] += 1
    w_lst[w_-1] += 1

h_count = max(h_lst)
w_count = max(w_lst)
h_cand = set([i+1 for i, h_ in enumerate(h_lst) if h_ == h_count])
w_cand = set([i+1 for i, w_ in enumerate(w_lst) if w_ == w_count])
#print(h_cand, w_cand)

count = 0
for bomb in lst_:
    if bomb[0] in h_cand and bomb[1] in w_cand:
        count += 1

ans = max(h_lst) + max(w_lst)
if count < len(h_cand)*len(w_cand):
    print(ans)
else:
    print(ans-1)
### BUGGY CODE ###

def main():
    import sys
    from collections import defaultdict
    S=sys.stdin.readline().strip()
    L=[0]*len(S)

    now=0
    for i in range(len(S)):
        now+=int(S[-i-1])*10**i
        L[-i-1]=now%2019

    dic=defaultdict(int)
    for a in L:
        dic[a]+=1

    
    output=0
    for _,val in dic.items():
        output+=val*(val-1)//2
    
    output+=dic[0]
    print(output)

main()


### FIXED CODE ###

def pow_with_mod(x, n, m):
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
            K %= m
        x *= x
        x %= m
        n //= 2

    return (K * x) % m

def main():
    import sys
    S=sys.stdin.readline().strip()
    N=len(S)
    L=[0]*2019
    now=0
    for i in range(N):
        now+=int(S[-i-1])*pow_with_mod(10, i, 2019)
        now%=2019
        L[now]+=1  
    print(L[0]+sum([x*(x-1)//2 for x in L]))
main()
### BUGGY CODE ###

import queue
def main():
    n,m,k=map(int,input().split())
    root={}
    ng={}
    for i in range(n):
        root[i]=[]
        ng[i]=[]
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1].append(b-1)
        root[b-1].append(a-1)
        ng[a-1].append(b-1)
        ng[b-1].append(a-1)
    for i in range(k):
        a,b=map(int,input().split())
        ng[a-1].append(b-1)
        ng[b-1].append(a-1)
    
    Vstd=[]
    checkVst=[0]*n
    num=[0]*n
    ToVst=queue.Queue()
   
    for i in range(n):
        
        Vstd=[]
        if checkVst[i]!=0:
            continue
        now=i
        Vstd.append(now)
        checkVst[now]=1
        

        for kouho in root[now]:
            if checkVst[kouho]!=1:
                ToVst.put(kouho)
                checkVst[kouho]=1
              
        while ToVst.empty()==False:
            now=ToVst.get()
            Vstd.append(now)
            checkVst[now]=1
           
            for kouho in root[now]:
                if checkVst[kouho]!=0:
                    continue
                ToVst.put(kouho)
                checkVst[kouho]=1
                
        lengh=len(Vstd)
        for v in Vstd:
            num[v]=lengh-1
            num[v]-=len(set(ng[v])&set(Vstd))
            


    
    print(*num)
    #print(" ".join(map(str,num)))
   

if __name__=="__main__":
    main()
    
        

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n,m,k=map(int,input().split())
uf=UnionFind(n)
block={}
for i in range(n):
    block[i]=[i]
for i in range(m):
    a,b=map(int,input().split())
    uf.union(a-1,b-1)
    block[a-1].append(b-1)
    block[b-1].append(a-1)
    
for i in range(k):
    a,b=map(int,input().split())
    block[a-1].append(b-1)
    block[b-1].append(a-1)
ans=[]
#print(block)
for i in range(n):
    res=uf.size(i)
 #   print(res)
    for value in block[i]:
        if uf.same(value,i):
            res-=1
    ans.append(res)
print(*ans)
### BUGGY CODE ###

l=[0]*42
n,k=map(int,input().split())
#"ans=n
ans=0
t=1
for i in range(n,k+1):
    for j,k in enumerate(bin(i)[::-1][:-2]):
        if k=="1": l[j]=(l[j]+1)%2
for i in l:
    ans+=(i*t)
    t*=2
print(ans)

### FIXED CODE ###

p=[0]*42
q=[0]*42
x=1
a,b=map(int,input().split())
if a==b:
    print(a)
    exit()

a-=1
for i in range(42):
    if b//x<1: break
    if x==1:
        q[0]=((b+1)//2)%2
    else:
        q[i]=[0,((b+1)%x)%2][(b//x)%2]
    x*=2
x=1
for i in range(42):
    if a//x<1: break
    if x==1:
        p[0]=((a+1)//2)%2
    else:
        p[i]=[0,((a+1)%x)%2][(a//x)%2]
    x*=2
x=1
ans=0
for i in range(42):
    ans+=(p[i]^q[i])*x
    x*=2
print(ans)
### BUGGY CODE ###

N=int(input())
P= [int(x) for x in input().split()]
cnt=0
for i in range(N):
  if min(P[:i+1])==P[i]:
    cnt+=1
print(cnt)

### FIXED CODE ###

N=int(input())
P=[int(x) for x in input().split()]
cnt=0
tmp=P[0]
for i in range(N):
  if P[i]<=tmp:
    cnt+=1
    tmp=P[i]
print(cnt)
### BUGGY CODE ###

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

addFlag = True

for x in range(n):
    text = input()
    addFlag = True
    for y in list:
        if text == y:
            addFlag = False
            break
    if addFlag:
        list.append(text)
        
print(len(list))

### FIXED CODE ###

import sys
import collections

n = int(sys.stdin.readline().strip())
data = []

for x in range(n):
    data.append(input())

print(len(collections.Counter(data)))
### BUGGY CODE ###

k = int(input())

def lunlun(x):
    if x == 0:
        return False
    s = str(x)
    good = True
    for i in range(1, len(s)):
        if abs(int(s[i - 1]) - int(s[i])) > 1:
            good = False
    return good

n = 0
last = 0
total = 0
while total < k:
    if lunlun(n):
        last = n
        total += 1
    n += 1

print(last)

### FIXED CODE ###

k = int(input())

def lunlun(x):
    s = str(x)
    good = 0
    for i in range(1, len(s)):
        if abs(int(s[i - 1]) - int(s[i])) > 1:
            # what is the "digit value" of s[i]
            return 10 ** (len(s) - i - 1)
    return good

n = 1
last = 0
total = 0
while total < k:
    skip = lunlun(n)
    if skip == 0:
        last = n
        total += 1
        n += 1
    else:
        n += skip

print(last)
### BUGGY CODE ###

X = int(input())

for a in range(0 , 10**4 , 1):
  for b in range(0 , X+1 , 1):
    if(a**5-b**5==X):
      print(a, b)
      exit()
    else:
      continue
      
for a in range(0 , 10**4 , 1):
  for b in range(0 , -X , -1):
    if(a**5-b**5==X):
      print(a, b)
      exit()
    else:
      continue

### FIXED CODE ###

X = int(input())
 
for a in range(-119 , 120 , 1):
  A = a**5
  for b in range(-119 , 120 , 1):
    B = b**5
    if(A-B==X):
      print(a, b)
      exit()
    else:
      continue
### BUGGY CODE ###

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

ans = 1
s = [a[0]]
 
for i in a[1:]:
    if i in s:
        continue
    else:
        ans += 1
        s.append(i)

print(ans) 

### FIXED CODE ###

import collections
N=int(input())
S=[]
for i in range(N):
    S.append(input())
s=collections.Counter(S)
s_key=s.keys()
print(len(s_key))
### BUGGY CODE ###

import sys
from collections import defaultdict

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

pen_dic=defaultdict(lambda: 0)
ac=set()

for line in sys.stdin:
  p, s = line.split()
  p = int(p)
  if p in set(ac):
    continue

  if s == "AC":
    ac.add(p)
  else:
    pen_dic[p] += 1
print(len(ac), sum(pen_dic[i] for i in ac))

### FIXED CODE ###

import sys
from collections import defaultdict

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

wa=defaultdict(lambda: 0)
already=set()
ac = 0
for line in sys.stdin:
  p, s = line.split()
  p = int(p)
  if p in already:
    continue

  if s == "AC":
    ac+=1
    already.add(p)
  else:
    wa[p] += 1

print(ac, sum(wa[i] for i in already))
### BUGGY CODE ###

N = int(input())
L= sorted(list(map(int, input().split())))

count = 0
for i in range(N):
  for j in range(i + 1, N):
    x = L[i] + L [j]
    y = L[j]
    count += sum(x > p > y for p in L)
    #print(count)
print(count)


### FIXED CODE ###

N = int(input())
L= sorted(list(map(int, input().split())))

count = 0
for i in range(N):
  z = 0
  for j in range(i + 1, N):
    x = L[i] + L[j]
    if z < N:
      while L[z] < x:
        z += 1
        if z == N:
          break
    count += z - j - 1
    #print(count)
print(count)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
a_list = list(map(int, input().split()))

M = 0
box_dict = {}
for i in reversed(range(N)):
    idx = i + 1
    multi_sum = 0
    for key, value in box_dict.items():
        if key % (idx * 2) == 0:
            multi_sum += value
    if a_list[i] - multi_sum == 0:
        box_dict[idx] = 0
    else:
        box_dict[idx] = 1
        M += 1

print(M)
if M > 0:
    b_list = [key for key, value in box_dict.items() if value == 1]
    print(" ".join(map(str, b_list)))

### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
a_list = list(map(int, input().split()))

M = 0
box_dict = {}
for i in reversed(range(N)):
    idx = i + 1
    multi_sum = 0
    if N // idx < 2:
        if a_list[i] == 0:
            box_dict[idx] = 0
        else:
            box_dict[idx] = 1
            M += 1
    else:
        for j in range(2, (N // idx) + 1):
            multi_sum += box_dict[idx * j]
        if a_list[i] - (multi_sum % 2) == 0:
            box_dict[idx] = 0
        else:
            box_dict[idx] = 1
            M += 1

print(M)
if M > 0:
    b_list = [key for key, value in box_dict.items() if value == 1]
    print(" ".join(map(str, b_list)))
### BUGGY CODE ###

def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        a = input()
        A.append(a)
    bl = []
    wl = []
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                bl.append((i, j))
            else:
                wl.append((i, j))
    r = 0
    for i in wl:
        t = 10**9
        for j in bl:
            t = min(t, abs(i[0]-j[0]) + abs(i[1]-j[1]))
        r = max(r, t)
    return r
print(main())


### FIXED CODE ###

def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        a = input()
        A.append(a)
    bl = []
    wl = set()
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                bl.append((i, j))
            else:
                wl.add((i, j))
    r = 0
    while wl:
        bln = []
        for i in bl:
            if (i[0] + 1, i[1]) in wl:
                wl.remove((i[0] + 1, i[1]))
                bln.append((i[0] + 1, i[1]))
            if (i[0] - 1, i[1]) in wl:
                wl.remove((i[0] - 1, i[1]))
                bln.append((i[0] - 1, i[1]))
            if (i[0], i[1] + 1) in wl:
                wl.remove((i[0], i[1] + 1))
                bln.append((i[0], i[1] + 1))
            if (i[0], i[1] - 1) in wl:
                wl.remove((i[0], i[1] - 1))
                bln.append((i[0], i[1] - 1))
        bl = bln
        r += 1
    return r
print(main())
### BUGGY CODE ###

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

input_lines = [list(map(int,input().split())) for i in range(b)]
input_lines = sorted(input_lines,key=lambda x: x[1]) #各要素において[1]に基づきソートする

c=[0]
for i in input_lines:
    p=0
    for j in c:
        if j > i[0]:
            p=1
    if p==0:
        c.append(i[1])
        
print(len(c)-1)




### FIXED CODE ###

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

input_lines = [list(map(int,input().split())) for i in range(b)]
input_lines = sorted(input_lines,key=lambda x: x[1]) #各要素において[1]に基づきソートする

c=[0]
for i in input_lines:
    #for j in c:
    #   if j > i[0]:
    #        p=1
    if max(c)<=i[0]:
        c.append(i[1])
        
print(len(c)-1)
### BUGGY CODE ###

import sys

n = sys.stdin.readline()

astr = sys.stdin.readline()
bstr = sys.stdin.readline()
cstr = sys.stdin.readline()

a = map(int, astr.strip().split(' '))
b = map(int, bstr.strip().split(' '))
c = map(int, cstr.strip().split(' '))

a.sort()
b.sort()
c.sort()

cnt = 0

for ai in a:
        bt = filter(lambda x:x > ai, b)
        for bi in bt:
                ct = filter(lambda x:x > bi, c)
                cnt = cnt + len(ct)

print(cnt)

### FIXED CODE ###

import sys

import time


def main():
        n = sys.stdin.readline()

        astr = sys.stdin.readline()
        bstr = sys.stdin.readline()
        cstr = sys.stdin.readline()

        a = list(map(int, astr.strip().split(' ')))
        b = list(map(int, bstr.strip().split(' ')))
        c = list(map(int, cstr.strip().split(' ')))

        a.sort()
        b.sort()
        c.sort()

        cnt = 0

        bc = []
        sum = 0
        timesum = 0
        for bi in reversed(b):
                sum += len(c) - binary(bi,c)
                bc.append(sum)
        bc.reverse()

        cnt = 0
        for ai in a:
                bi = binary(ai, b)
                if(bi < len(bc)):
                    cnt += bc[bi]

        print(cnt)


def binary(x, li):
    upper = len(li)
    lower = -1
    index = int((upper + lower) / 2)

    while upper - lower > 1:
        if (x < li[index]):
            upper = index
        else:
            lower = index
        index = int((upper + lower)/2)
    
    return upper


main()
### BUGGY CODE ###

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


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
AC = [int(S[i:i+2] == 'AC') for i in range(len(S)-1)]
for i in range(1, len(AC)):
    AC[i] = AC[i] + AC[i-1]
AC.insert(0, 0)
for i in range(Q):
    l, r = map(int, input().split())
    # print(AC[r-1], AC[l-1])
    print(AC[r-1]-AC[l-1])
### BUGGY CODE ###

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

output = 1
for i in range(1, M//N+1):
    if M % i == 0 and output < i:
        output = i
print(output)


### FIXED CODE ###

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

output = 1
for i in range(M//N, 0, -1):
    if M % i == 0 and output < i:
        output = i
        break
print(output)