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

from collections import deque
import sys
input=sys.stdin.readline
calc=lambda x,y:x*1000007+y
def main():
  h,w,k=map(int,input().split())
  sx,sy,tx,ty=map(int,input().split())
  b=[[-1]*(w+2)]
  for i in range(h):
    s=input()
    bb=[-1]
    for j in s:
      if j==".":bb.append(0)
      else:bb.append(-1)
    bb.append(-1)
    b.append(bb)
  b.append([-1]*(w+2))
  d=deque()
  d.append(calc(sx,sy))
  s=set()
  while d:
    x,y=divmod(d.popleft(),1000007)
    if calc(x,y)in s:
      s.discard((x,y))
      continue
    if x==tx and y==ty:
      exit(print(b[x][y]))
    for i in range(1,k+1):
      if b[x-i][y]<=b[x][y] and b[x-i][y]!=0:break
      d.append(calc(x-i,y))
      if b[x-i][y]!=0:
        s.add((x-i,y))
      b[x-i][y]=b[x][y]+1
    for i in range(1,k+1):
      if b[x+i][y]<=b[x][y] and b[x+i][y]!=0:break
      d.append(calc(x+i,y))
      if b[x+i][y]!=0:
        s.add((x+i,y))
      b[x+i][y]=b[x][y]+1
    for j in range(1,k+1):
      if b[x][y-j]<=b[x][y] and b[x][y-j]!=0:break
      d.append(calc(x,y-j))
      if b[x][y-j]!=0:
        s.add((x,y-j))
      b[x][y-j]=b[x][y]+1
    for j in range(1,k+1):
      if b[x][y+j]<=b[x][y] and b[x][y+j]!=0:break
      d.append(calc(x,y+j))
      if b[x][y+j]!=0:
        s.add((x,y+j))
      b[x][y+j]=b[x][y]+1
  print(-1)
if __name__ == "__main__":
  main()


### FIXED CODE ###

import sys
input=sys.stdin.readline
h,w,k=map(int,input().split())
si,sj,ti,tj=map(int,input().split())
si-=1
sj-=1
ti-=1
tj-=1
b=[input()for _ in range(h)]
ans=[[-1]*w for _ in range(h)]
ans[si][sj]=0
from collections import deque
d=deque()
d.append((si,sj))
while d:
  x,y=d.popleft()
  if x==ti and y==tj:
    exit(print(ans[x][y]))
  for dx,dy in [[1,0],[-1,0],[0,-1],[0,1]]:
    for i in range(1,k+1):
      xx=x+dx*i
      yy=y+dy*i
      if not(0<=xx<h and 0<=yy<w) or b[xx][yy]=="@":break
      if 0<=ans[xx][yy]<=ans[x][y]:break
      if ans[xx][yy]==-1:d.append((xx,yy))
      ans[xx][yy]=ans[x][y]+1
print(-1)
### BUGGY CODE ###

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

print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for i in range(k + 1):
    for j in range(k + 1):
        l = s - i - j
        if l >= 0 and l <= k:
            count += 1

print(count)
### BUGGY CODE ###

def resolve():
  base = 998244353
  N, K = map(int, input().split(" "))

  step_lengthes = []
  for _ in range(K):
    L, R = map(int, input().split(" "))
    step_lengthes.extend(range(L, R+1))
  step_lengthes.sort()
  dp = [0] * (N+1)
  dp[1] = 1

  for i in range(1, N+1):
    for d in step_lengthes:
      if i+d <= N:
        dp[i+d] += dp[i]
        if i+d == N and dp[i+d] >= base:
          dp[i+d] %= base
      else:
        break
  print(dp[-1]%base)

if __name__ == "__main__":
  resolve()

### FIXED CODE ###

def resolve():
  base = 998244353
  N, K = map(int, input().split(" "))

  LRs = []
  for _ in range(K):
    (L, R) = map(int, input().split(" "))
    LRs.append((L, R))

  dp = [0] * (N+1)
  dp_sum = [0] * (N+1)
  dp[1] = 1
  dp_sum[1] = 1

  for i in range(2, N+1):
    for lr in LRs:
      left = max(i - lr[1] - 1, 0)
      right = max(i - lr[0], 0)
      dp[i] += dp_sum[right] - dp_sum[left]
      if dp[i] >= base:
        dp[i] %= base
      dp_sum[i] = dp_sum[i-1] + dp[i]
  print(dp[-1])

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

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
mod = 10**9+7
dq = [0] * (n+1)
dq[0] = 1
for i in range(1, n+1):
  dq[i] = dq[i-1] + dq[i-2]
  if i in a:
    dq[i] = 0
print(dq[n] % mod)

### FIXED CODE ###

n, m = map(int, input().split())
dq = [1]*(n+1)
for _ in range(m):
  dq[int(input())]=0
mod = 10**9+7
x, y = 0, 1
for i in range(1, n+1):
  x,y = y, dq[i] * (x+y) % mod
print(y)
### BUGGY CODE ###

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

ans=1
for i in range(n):
    ans*=a[i]
    if ans>10**18:
        ans=-1   
if ans<0:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

ans=1
for i in range(n):
    ans*=a[i]
    if ans>10**18:
        ans=-1
        break

if min(a)==0:
    print(0)
else:
    print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

h,w=map(int,input().split())
s=[[]*w for i in range(h)]
for i in range(h):
    s[i]=list(input())

ww=[[0]*w for i in range(h)]
for i in range(h):
    jsum=0
    jst=0
    jed=0
    for j in range(w):
        if s[i][j]==".":
            jsum+=1
            jst=min(j,jst)
            jed=max(j,jed)
        else:
#            print(jsum,jst,jed)
            if jsum!=0:
                for jj in range(jst,jed+1):
                    ww[i][jj]=jsum
            jsum=0
            jst=j+1
            jed=j+1
        if jst<w:
            for jj in range(jst,jed+1):
                ww[i][jj]=jsum
                
hh=[[0]*w for i in range(h)]
for j in range(w):
    isum=0
    ist=0
    ied=0
    for i in range(h):
        if s[i][j]==".":
            isum+=1
            ist=min(i,ist)
            ied=max(i,ied)
        else:
#            print(isum,ist,ied)
            if isum!=0:
                for ii in range(ist,ied+1):
                    hh[ii][j]=isum
            isum=0
            ist=i+1
            ied=i+1
        if ist<h:
            for ii in range(ist,ied+1):
                hh[ii][j]=isum
            
ijmax=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ijmax=max(ijmax,ww[i][j]+hh[i][j]-1)

print(ijmax)
             


### FIXED CODE ###

import sys
input = sys.stdin.readline

h,w=map(int,input().split())
s=[[] for i in range(h)]
for i in range(h):
    si=input()
    s[i]=si
"""
h,w=4,6
s=[['#', '.', '.', '#', '.', '.'], ['.', '.', '.', '.', '.', '#'], ['.', '.', '.', '.', '#', '.'], ['#', '.', '#', '.', '.', '.']]    
"""
ww=[[0]*w for i in range(h)]
#www=[[0]*w for i in range(h)]
www=[0]*w
for i in range(h):
    jsum=0
    jcnt=1
    jj=[0]*(w+1)
    for j in range(w):
        if s[i][j]==".":
#            www[i][j]=jcnt
            www[j]=jcnt
            if j<w-1 and s[i][j+1]=="#":
                jcnt+=1
            jsum+=1
        else:
#            print(jsum,jst,jed)
            if jsum!=0:
                jj[jcnt-1]=jsum
            jsum=0
    jcnt+=1
    jj[jcnt-1]=jsum
            
    for j in range(w):
        if s[i][j]==".":
#            ww[i][j]=jj[www[i][j]]
            ww[i][j]=jj[www[j]]
#    print(jj)
                
hh=[[0]*w for i in range(h)]
hhh=[0]*h
for j in range(w):
    isum=0
    icnt=1
    ii=[0]*(h+1)
    for i in range(h):
        if s[i][j]==".":
#            www[i][j]=jcnt
            hhh[i]=icnt
            if i<h-1 and s[i+1][j]=="#":
                icnt+=1
            isum+=1
        else:
#            print(jsum,jst,jed)
            if isum!=0:
                ii[icnt-1]=isum
            isum=0
    icnt+=1
    ii[icnt-1]=isum
            
    for i in range(h):
        if s[i][j]==".":
#            ww[i][j]=jj[www[i][j]]
            hh[i][j]=ii[hhh[i]]
#    print(jj)
            
ijmax=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ijmax=max(ijmax,ww[i][j]+hh[i][j]-1)

print(ijmax)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n-2):
    num1=i+a[i]
    if n-1-num1>0:
        for j in range(num1+1,n):
            if j-num1==a[j]:
                ans+=1
print(ans)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
num1=[0]*(2*(10**5)+10)
num2=[0]*(2*(10**5)+10)
for i in range(n):
    if a[i]+i+1<2*(10**5)+5:
        num1[a[i]+i+1]+=1
    if a[i]+1<i+1:
        num2[-a[i]+i+1]+=1
ans=0
for i in range(len(num1)):
    ans+=num1[i]*num2[i]
print(ans)
### BUGGY CODE ###

from collections import deque

n=int(input())
g=[[] for i in range(n+1)]
clst=[-1]*(n-1)

for i in range(n-1):
    a,b=list(map(int,input().split()))

    g[a].append([b,i])
    g[b].append([a,i])


q=deque([[1,0]])
k=0

while len(q)>0:
    u,c=deque.popleft(q)

    clrs=list(range(1,c))+list(range(c+1,len(g[u])+1))
    cnt=0

    for v,i in g[u]:
        if clst[i]==c:
            continue
        clst[i]=clrs[cnt]
        deque.append(q,[v,clst[i]])
        cnt+=1


    if len(clrs)>0:
        k=max(k,clrs[-1])

print(k)

for i in range(n-1):
    print(clst[i])


### FIXED CODE ###

from collections import deque

n=int(input())
g=[[] for i in range(n+1)]
clst=[-1]*(n-1)

for i in range(n-1):
    a,b=list(map(int,input().split()))

    g[a].append([b,i])
    g[b].append([a,i])


q=deque([[1,0]])
k=0

while len(q)>0:
    u,c=deque.popleft(q)

    clr=1

    for v,i in g[u]:
        if clst[i]==c:
            continue
        if clr==c:
            clr+=1
        
        clst[i]=clr
        deque.append(q,[v,clr])

        clr+=1


    k=max(k,clr-1)

print(k)

for i in range(n-1):
    print(clst[i])
### BUGGY CODE ###

D,G=map(int, input().split())

L=[]
for i in range(D):
    p,c=map(int, input().split())
    L.append((p,c))

from itertools import permutations
from math import ceil
ans=float("INF")
for t in permutations(range(1,D+1)):
    #print(t)
    t=list(t)
    now=G
    sub=0
    for x in t:
        p,c=L[x-1]
        if now/(x*100)<=p:
            sub+=ceil(now/(x*100))
            break
        elif x*p*100+c>=now:
            sub+=p
            break
        else:
            now-=x*p*100+c
            sub+=p

    #print(t, sub)
    ans=min(ans, sub)
    
print(ans)

### FIXED CODE ###

D,G=map(int, input().split())

L=[]
for i in range(D):
    p,c=map(int, input().split())
    L.append((p,c))

from itertools import permutations
from math import ceil
ans=float("INF")
for t in permutations(range(1,D+1)):
    #print(t)
    t=list(t)
    now=G
    sub=0
    for x in t:
        p,c=L[x-1]
        if now/(x*100)<=p:
            sub+=ceil(now/(x*100))
            break
        elif x*p*100+c>=now:
            sub+=p
            break
        else:
            now-=x*p*100+c
            sub+=p

    #print(t, sub)
    ans=min(ans, sub)
    
print(ans)
### BUGGY CODE ###

import copy
n = int(input())
a = [int(input()) for _ in range(n)]
ex_a = []
for i in range(n):
  ex_a = copy.deepcopy(a)
  ex_a[i] = -1
  print(max(ex_a))

### FIXED CODE ###

#import copy
# 最大値が2つ以上あるものと1つしかないもので場合分けをする
n = int(input())
a = [int(input()) for _ in range(n)]
b = sorted(a)
if b[-1] == b[-2]:
  for i in range(n):
    print(b[-1])
else:
  p = a.index(b[-1])
  for i in range(n):
    if i == p:
      print(b[-2])
    else:
      print(b[-1])
#deepcopy is so slow!!
# ex_a = []
# for i in range(n):
#   ex_a = copy.deepcopy(a)
#   ex_a[i] = -1
#   print(max(ex_a))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
from collections import deque

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

n = getN()

match = [0 for i in range((n*(n-1))//2)]
child = [[] for i in range((n*(n-1))//2)]
isroot = [True for i in range((n*(n-1))//2)]


def bfs():
    q = deque([])
    for root, rt in enumerate(isroot):
        if rt:
            q.append(root)
            match[root] = 1
    # print(match)
    while(q):
        item = q.popleft()
        # print(q, item, child[item])
        for ch in child[item]:
            if match[ch] < match[item] + 1:
                match[ch] = match[item] + 1
                q.append(ch)

    return




for idd in range(n):
    nums = getList()
    i = idd + 1
    for j,k in zip(nums, nums[1:]):
        ii, j = min(i, j), max(i,j)
        iii, k = min(i, k), max(i,k)
        idx1 = ((j-1)*(j-2))//2 + (ii-1)
        idx2 = ((k - 1) * (k - 2)) // 2 + (iii - 1)
        isroot[idx2] = False
        child[idx1].append(idx2)
        # print(i, j, k)
        # print(idx1, idx2)

#
# print(child)
# print(isroot)
# # sys.exit()

bfs()
# print("gg")
ans = 1
for m in match:
    if m > ans:
        ans = m
    if m == 0:
        print(-1)
        sys.exit()

print(ans)



### FIXED CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(100000)
from collections import deque


def getN():
    return int(input())


def getList():
    return list(map(int, input().split()))


import math

n = getN()

match = [0 for i in range((n * (n - 1)) // 2)]
child = [[] for i in range((n * (n - 1)) // 2)]
iriji = [0 for i in range((n * (n - 1)) // 2)]


def toposo(n, iriji, child):
    order = [0 for i in range((n*(n+1))//2)]
    q = deque([])
    for i, iri in enumerate(iriji):
        if iri == 0:
            q.append(i)
            order[i] = 1
    while(q):
        start = q.popleft()
        target = child[start]
        for tgt in target:
            iriji[tgt] -= 1
            if iriji[tgt] == 0:
                q.append(tgt)
                order[tgt] = order[start] + 1

    if sum(iriji) != 0:
        return -1

    else:
        return max(order)


for idd in range(n):
    nums = getList()
    i = idd + 1
    for j, k in zip(nums, nums[1:]):
        ii, j = min(i, j), max(i, j)
        iii, k = min(i, k), max(i, k)
        idx1 = ((j - 1) * (j - 2)) // 2 + (ii - 1)
        idx2 = ((k - 1) * (k - 2)) // 2 + (iii - 1)
        iriji[idx2] += 1
        child[idx1].append(idx2)
        # print(i, j, k)
        # print(idx1, idx2)

#
# print(child)
# print(isroot)
# # sys.exit()
#
# bfs()
# # print("gg")
# ans = 1
# for m in match:
#     if m > ans:
#         ans = m
#     if m == 0:
#         print(-1)
#         sys.exit()
# print(iriji, child)

print(toposo(n, iriji, child))
### BUGGY CODE ###

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

count = 0

for r in range(0, N//R+1):
    #print('-'*10)
    #print(r)
    
    for g in range(0, N//G+1):
        #print(g)
        # compute b
        b = (N - r*R - g*G) / B
        #print(b)
        
        # judge
        if b.is_integer() and b >=0:
            count += 1
            #print('*'*10, count, '*'*10)

print(count)        

### FIXED CODE ###

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

count = 0

for r in range(N//R+1):

  for g in range((N-r*R)//G+1):
    if (N - r*R - g*G) % B == 0:
      count += 1

print(count)
### BUGGY CODE ###

from collections import deque
a,b=map(int,input().split())
List=[]
q=deque([[0,0]])
for i in range(a):
  l=list(input())
  for _ in range(b):
    if l[_]=="#":
      q.append([i,_])
      l[_]=0
  List.append(l)
q.popleft()
aaa=[[0,1],[0,-1],[1,0],[-1,0]]
ans=0
while q:
  h,w=q.popleft()
  for x,y in aaa:
    if 0<=h+x<a and 0<=w+y<b:
      if List[h+x][w+y]==".":
        List[h+x][w+y]=List[h][w]+1
        q.append([h+x,w+y])
        if List[h+x][w+y]>ans:
          ans=List[h+x][w+y]
print(ans)

### FIXED CODE ###

from collections import deque
a,b=map(int,input().split())
List=[]
q=deque([[0,0]])
for i in range(a):
  l=list(input())
  for _ in range(b):
    if l[_]=="#":
      q.append([i,_])
      l[_]=0
  List.append(l)
q.popleft()
aaa=[[0,1],[0,-1],[1,0],[-1,0]]
ans=0
while q:
  h,w=q.popleft()
  for x,y in aaa:
    if 0<=h+x<a and 0<=w+y<b:
      if List[h+x][w+y]==".":
        List[h+x][w+y]=List[h][w]+1
        q.append([h+x,w+y])
        if List[h+x][w+y]>ans:
          ans=List[h+x][w+y]
print(ans)
### BUGGY CODE ###

# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# a=100
# b=0.987654321
# print('{0:06d}-{1:6f}'.format(a,b))  # 0埋めのときの出力
# 000100-0.987654

import numpy as np
import math
import copy


N,M=map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
update = []

for _ in range(M):
    B,C=map(int, input().split())
    for _ in range(B):
        update.append(C)

update = sorted(update,reverse=True)

#max_sum = sum(A)

for i in range(N):
    if i >= len(update):
        break
    if(A[i] > update[i]):
        break
    A[i] = update[i]
    #max_sum = max(max_sum, sum(A))

print(sum(A))

### FIXED CODE ###

# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# a=100
# b=0.987654321
# print('{0:06d}-{1:6f}'.format(a,b))  # 0埋めのときの出力
# 000100-0.987654

import numpy as np
import math
import copy
from time import time

N,M=map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
update = []

for _ in range(M):
    temp = list(map(int, input().split()))
    update.append(temp)

# C_i の値をkeyにしてソートする
update = sorted(update,key = lambda x:x[1], reverse=True)

idx = 0
for b, c in update:
    for i in range(b):
        if idx >= N:
            break
        if A[idx] < c:
            A[idx] = c
            idx += 1
        else:
            break

print(sum(A))
### BUGGY CODE ###

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



Asum=[0]
for i in A:
  if Asum[-1]+i>K:break
  Asum.append(Asum[-1]+i)
    
Bsum=[0]
for i in B:
  if Bsum[-1]+i>K:break
  Bsum.append(Bsum[-1]+i)

maxval=len(Asum)-1

for i in range(len(Asum)):
  for j in range(len(Bsum)):
    if Asum[-i-1]+Bsum[j]>K:
      maxval=max(maxval,len(Asum)-1-i+j-1)
      break
    elif j==len(Bsum)-1:
      maxval=max(maxval,len(Asum)-1-i+j)
      
print(maxval)

### FIXED CODE ###

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

Asum=[0]
for i in A:
  if Asum[-1]+i>K:break
  Asum.append(Asum[-1]+i)
import numpy as np
Asum=np.array(Asum)
Bsum=[0]
for i in B:
  if Bsum[-1]+i>K:break
  Bsum.append(Bsum[-1]+i)
Bsum=np.array(Bsum)

maxval=len(Asum)-1

tmp=0
lenB=len(Bsum)
lenA=len(Asum)
for i in range(lenA):
  if lenA-1-i+lenB<maxval:break
  for j in range(lenB):
    j=tmp+j
    if Asum[-i-1]+Bsum[j]>K:
      maxval=max(maxval,len(Asum)-1-i+j-1)
      tmp=j
      break
    elif j==lenB-1:
      maxval=max(maxval,lenA-1-i+j)
      break
print(maxval)
### BUGGY CODE ###

n,k = map(int, input().split())
A = list(map(int, input().split()))
import collections
res = collections.deque('1')
rep = [0,0]
for i in range(n):
    #print(res)
    if str(A[int(res[-1])-1]) not in res:
        res.append(str(A[int(res[-1])-1]))
    else:
        rep[0] = res.index(str(A[int(res[-1])-1]))
        rep[1] = len(res)
        break

#print(res)
#print(rep)
if k < len(res):
    print(res[k])
else:
    rep_num = rep[1] - rep[0]
    remainder = (k-rep[0])%rep_num
    print(res[rep[0] +remainder])

### FIXED CODE ###

n,k = map(int, input().split())
b = list(map(int, input().split()))
a=0
for i in range(n):
    b[i] -= 1
if k<n:
    for i in range(k):
        a = b[a]
    print(a+1)
    exit()
c = [-1]*n
cc = 0
se = set()
while a not in se:
    c[a] = cc
    cc += 1
    se.add(a)
    a = b[a]
for i in range((k-c[a])%(cc-c[a])):
    a = b[a]
print(a+1)
### BUGGY CODE ###

import copy
N, K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))
X = []
A = sorted(A)
F = sorted(F)[::-1]
for i in range(N):
  X.append(A[i] * F[i])
XX = copy.deepcopy(X)

import heapq
from heapq import heapify

heapq._heapify_max(X)

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    lastelt = heap.pop()
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

for i in range(K):
    x = _heappop_max(X)
    id = XX.index(x)
    if x < 1:
        _heappush_max(X,x)
        break
    else:
        A[id] -= 1
        x = A[id] * F[id]
        XX[id] = x
        _heappush_max(X,x)
print(max(X))

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,K = map(int,readline().split())
A = np.array(readline().split(),np.int64)
F = np.array(readline().split(),np.int64)

A.sort(); F.sort(); F=F[::-1]

def test(x):
    return np.maximum(0,A-x//F).sum() <= K

left = -1
right = 10**13
while left+1 < right:
    mid = (left+right)//2
    if test(mid):
        right = mid
    else:
        left = mid
answer = right
print(answer)
### BUGGY CODE ###

def lucas(i):
    if i == 0:
        return 2
    elif i == 1:
        return 1
    else:
        return lucas(i - 1) + lucas(i - 2)

n = int(input())
print(lucas(n))


### FIXED CODE ###

n = int(input())

l = [2, 1]
for i in range(2, n + 1):
    l.append(l[(i - 1)] + l[(i - 2)])
print(l[n])
### BUGGY CODE ###

N,Q=map(int,input().split())
S=str(input().strip())
arr=[]
for i in range(len(S)-1):
    if S[i]=="A" and S[i+1]=="C":
        arr.append(1)
    else:
        arr.append(0)
arr.append(0)
num=[]
for i in range(Q):
    l,r=map(int,input().split())
    num.append(sum(arr[l-1:r-1]))

for i in num:
    print(i)


### FIXED CODE ###

N,Q=map(int,input().split())
S=str(input())

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

#!/usr/bin/env python3

# from typing import Optional
from typing import List

# from typing import Dict
from typing import Tuple

# from typing import Sequence

Cod = Tuple[int, int]


def main():
    args = input().split()
    H = int(args[0])
    W = int(args[1])
    M = int(args[2])

    codList: List[Cod] = []
    for i in range(M):
        args = input().split()
        codList.append((int(args[0]), int(args[1])))

    maxRowCount = 0
    maxRowIndexList: List[int] = []
    for row in range(H):
        hitList = list(filter(lambda x: x[0] == row + 1, codList))
        counter = len(hitList)
        if counter > maxRowCount:
            maxRowCount = counter
            maxRowIndexList = [row + 1]
        elif counter == maxRowCount:
            maxRowIndexList.append(row + 1)

    maxColumnCount = 0
    maxColumnIndexList: List[int] = []
    for column in range(W):
        hitList = list(filter(lambda x: x[1] == column + 1, codList))
        counter = len(hitList)
        if counter > maxColumnCount:
            maxColumnCount = counter
            maxColumnIndexList = [column + 1]
        elif counter == maxColumnCount:
            maxColumnIndexList.append(column + 1)

    result = maxRowCount + maxColumnCount
    for row in maxRowIndexList:
        for column in maxColumnIndexList:
            if (row, column) in codList:
                continue
            else:
                print(result)
                return

    print(result - 1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

# from typing import Optional
from typing import List

# from typing import Dict
from typing import Tuple
from typing import Set

# from typing import Sequence

Cod = Tuple[int, int]


def main():
    args = input().split()
    H = int(args[0])
    W = int(args[1])
    M = int(args[2])

    codList = {}
    columnSumList: List[int] = [0] * W
    rowSumList: List[int] = [0] * H
    for i in range(M):
        h, w = map(lambda x: int(x), input().split())
        item = (h, w)
        codList.setdefault(h, {})
        codList[h][w] = item
        columnSumList[w - 1] += 1
        rowSumList[h - 1] += 1

    maxColumnSum = max(columnSumList)
    maxColumIndexList = [i for i, x in enumerate(columnSumList) if x == maxColumnSum]
    maxRowSum = max(rowSumList)
    maxRowIndexList = [i for i, x in enumerate(rowSumList) if x == maxRowSum]

    result = maxColumnSum + maxRowSum
    for row in maxRowIndexList:
        for column in maxColumIndexList:
            if row + 1 in codList and column + 1 in codList[row + 1]:
                continue
            else:
                print(result)
                return

    print(result - 1)


if __name__ == "__main__":
    main()