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

from collections import deque
def bfs():
    d = [[float("inf") for i in range(W)] for j in range(H)]
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    que = deque([])
    ans = 0

    for i in range(W):
        for j in range(H):
            if S[j][i] == "#":
                d[j][i] = 0
                que.append((i,j))

    while que:
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0<=nx<W and 0<=ny<H and S[ny][nx] != "#" and d[ny][nx] == float("inf"):
                que.append((nx,ny))
                d[ny][nx] = d[p[1]][p[0]] + 1
                ans = max(ans,d[ny][nx])
    return ans

H,W = map(int,input().split())
S = [list(input()) for i in range(H)]

print(bfs())


### FIXED CODE ###

from collections import deque
h,w = map(int,input().split())
grid = []
dq = deque([])
dx = [1,-1,0,0]
dy = [0,0,1,-1]
ans = 0
d = [[-1 for i in range(w)] for j in range(h)]
for i in range(h):
    maze = list(input())
    for j in range(w):
        if maze[j] == "#":
            dq.append((j,i))
            d[i][j] = 0
    grid.append(maze)
while dq:
    x,y = dq.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx <= w-1 and 0 <= ny <= h-1 and grid[ny][nx] != "#" and d[ny][nx] == -1:
            dq.append((nx,ny))
            d[ny][nx] = d[y][x] + 1
            ans = max(ans,d[ny][nx])
print(ans)
### BUGGY CODE ###

B,W=map(int,input().split())
mod=10**9+7
kaijo=[1]
Xdiv=[1]
two=pow(2,mod-2,mod)
for i in range(1,1+B+W):
    kaijo.append((kaijo[-1])*i%mod)
    Xdiv.append((Xdiv[-1]*two)%mod)
from collections import deque
gyaku=deque()
gyaku.append(pow(kaijo[B+W],mod-2,mod))
for i in range(B+W,0,-1):
    gyaku.appendleft((gyaku[0]*i)%mod)
def conb(a,b):
    return (kaijo[a]*gyaku[a-b]*gyaku[b])%mod
Blost,Wlost=0,0
if B==W:
    for k in range(1,B):
        print(two)
    for k in range(B,B+W):
        print(((1+Wlost-Blost)*two)%mod)
        Blost=(Blost+conb(k-1,B-1)*Xdiv[k])%mod
        Wlost=(Wlost+conb(k-1,W-1)*Xdiv[k])%mod
    print(((1+Wlost-Blost)*two)%mod)
elif B<W:
    for k in range(1,B):
        print(two)
    for k in range(B,W):
        print(((1+Wlost-Blost)*two)%mod)
        Blost=(Blost+conb(k-1,B-1)*Xdiv[k])%mod
    for k in range(W,B+W):
        print(((1+Wlost-Blost)*two)%mod)
        Blost=(Blost+conb(k-1,B-1)*Xdiv[k])%mod
        Wlost=(Wlost+conb(k-1,W-1)*Xdiv[k])%mod
    print(((1+Wlost-Blost)*two)%mod)
elif B>W:
    for k in range(1,W):
        print(two)
    for k in range(W,B):
        print(((1+Wlost-Blost)*two)%mod)
        Wlost=(Wlost+conb(k-1,W-1)*Xdiv[k])%mod
    for k in range(B,B+W):
        print(((1+Wlost-Blost)*two)%mod)
        Blost=(Blost+conb(k-1,B-1)*Xdiv[k])%mod
        Wlost=(Wlost+conb(k-1,W-1)*Xdiv[k])%mod
    print(((1+Wlost-Blost)*two)%mod)

### FIXED CODE ###

B,W=map(int,input().split())
mod=10**9+7
kaijo={0:1}
Xdiv={0:1}
two=pow(2,mod-2,mod)
for i in range(1,1+B+W):
    kaijo[i]=(kaijo[i-1]*i)%mod
    Xdiv[i]=(Xdiv[i-1]*two)%mod
gyaku={B+W:pow(kaijo[B+W],mod-2,mod)}
for i in range(B+W,0,-1):
    gyaku[i-1]=(gyaku[i]*i)%mod
def conb(a,b):
    if a<b:return 0
    return (kaijo[a]*gyaku[a-b]*gyaku[b])%mod
Blost,Wlost=0,0
for k in range(1,B+W):
    print(((1+Wlost-Blost)*two)%mod)
    Blost=(Blost+conb(k-1,B-1)*Xdiv[k])%mod
    Wlost=(Wlost+conb(k-1,W-1)*Xdiv[k])%mod
print(((1+Wlost-Blost)*two)%mod)
### BUGGY CODE ###


def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [tuple(map(int, input().split())) for i in range(N)]

    id = [0]*N
    Lock = [-1]*N
    ans = 0
    min_id = 0
    M = (N*(N-1)) // 2

    while(min_id < N-1):
        ans += 1
        if ans > M:
            break
        tmp = set()
        for i in range(N):
            if id[i] >= N-1:
                continue
            else:
                if Lock[i] >= 0:
                    continue
                else:
                    a = A[i][id[i]]
                    if Lock[a-1] == i and i not in tmp:
                        Lock[a-1] = -1
                        id[a-1] += 1
                        tmp.add(a-1)
                        id[i] += 1
                    else:
                        if i not in tmp:
                            Lock[i] = A[i][id[i]]-1
        min_id = min(id)
    if ans > M:
        print(-1)
    else:
        print(ans)


main()


### FIXED CODE ###

def main():
    import sys
    import time
    input = sys.stdin.buffer.readline
    start = time.time()
    N = int(input())
    A = [tuple(map(int, input().split())) for i in range(N)]

    id = [0]*N
    Lock = [-1]*N
    ans = 0
    min_id = 0
    M = (N*(N-1)) // 2

    while(min_id < N-1):
        now = time.time()
        if now - start > 1.9:
            ans = M
            break
        ans += 1
        if ans > M:
            break
        tmp = set()
        for i in range(N):
            if id[i] >= N-1:
                continue
            else:
                if Lock[i] >= 0:
                    continue
                else:
                    a = A[i][id[i]]
                    if Lock[a-1] == i and i not in tmp:
                        Lock[a-1] = -1
                        id[a-1] += 1
                        tmp.add(a-1)
                        id[i] += 1
                    else:
                        if i not in tmp:
                            Lock[i] = A[i][id[i]]-1
        min_id = min(id)
    if ans > M:
        print(-1)
    else:
        print(ans)


main()
### BUGGY CODE ###

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

for i in a:
    ans *= i

if ans > 10**18:
    ans = -1

print(ans)


### FIXED CODE ###

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

for i in a:
    ans *= i
    if ans > 10**18:
        ans = -1
        break

if a.count(0) > 0:
    ans = 0

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

s = list(input())
q = int(input())
dummy = ""
for i in range(q):
  q_list = input().split()
  if q_list[0] == "1":
    s.reverse()
  else:
    if q_list[1] == "1":
      s.insert(0,q_list[2])
    else:
      s.append(q_list[2])
print("".join(s))

### FIXED CODE ###

s = input()
q = int(input())
turn = 1
start = []
end = []
for i in range(q):
    q_list = list(input().split())
    if q_list[0] == "1":
        turn *= -1
    else:
        if q_list[1] == "1":
            if turn == 1:
                start.append(q_list[2])
            else:
                end.append(q_list[2])
        else:
            if turn == -1:
                start.append(q_list[2])
            else:
                end.append(q_list[2])

dum1 = "".join(start)
dum2 = "".join(end)
if turn == 1:
    print(dum1[::-1]+s+dum2)
else:
    print(dum2[::-1] + s[::-1] + dum1)
### BUGGY CODE ###

N, M = map(int, input().split())
l = []
for _ in range(M):
    a, b = map(int, input().split())
    c = tuple(map(int, input().split()))
    l.append((a, c))

inf = 10**12
dp = [inf]*(2**N)
dp[0] = 0

for i in range(2**N):
    for cost, j in l:
        v=0
        for k in j:
            v+=2**(k-1)
        dp[i|v] = min(dp[i|v], dp[i]+cost)

print(dp[2**N-1] if dp[2**N-1]!=inf else -1)

### FIXED CODE ###

N, M = map(int, input().split())
l = []
for _ in range(M):
    a, b = map(int, input().split())
    c = tuple(map(int, input().split()))
    l.append((a, c))

inf = 10**12
dp = [inf]*(2**N)
dp[0] = 0

for i in range(2**N):
    for cost, j in l:
        v=0
        for k in j:
            v+=2**(k-1)
        dp[i|v] = min(dp[i|v], dp[i]+cost)

print(dp[2**N-1] if dp[2**N-1]!=inf else -1)
### BUGGY CODE ###

S=input()
k={}
t=0
k[0]=1
for i,s in enumerate(S[::-1]):
  t+=int(s)*(10**i)
  l=t%2019
  if l in k:
    k[l]+=1
  else:
    k[l]=1
  
ans=0
for i in k.values():
  ans+=i*(i-1)//2
print(ans)

### FIXED CODE ###

S=input()
k=[0]*2019
t=0
k[0]=1
for i,s in enumerate(S[::-1]):
  t+=int(s)*pow(10,i,2019)
  t%=2019
  k[t]+=1
  
ans=0
for l in k:
  ans+=l*(l-1)//2
print(ans)
### BUGGY CODE ###

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

def add_car(S,s,is_left,is_rev):
    if is_rev:
        is_left = not(is_left)
    if is_left:
        S = s+S
    else:
        S = S+s
    return S

is_rev = False
for q in range(Q):
    x = input().split(' ')
    if len(x) == 1:
        is_rev = not is_rev
    else:
        S = add_car(S,x[2],x[1]=='1',is_rev)

if is_rev:
    S = ''.join(reversed([s for s in S]))
print(S)

### FIXED CODE ###

S = input()
S_h = ''
S_t = ''
Q = int(input())

def add_car(S_h,S_t,s,is_left,is_rev):
    if is_rev:
        is_left = not(is_left)
    if is_left:
        S_h = ''.join([S_h,s])
    else:
        S_t = ''.join([S_t,s])
    return S_h,S_t

is_rev = False
for q in range(Q):
    x = input().split(' ')
    if len(x) == 1:
        is_rev = not is_rev
    else:
        S_h,S_t = add_car(S_h,S_t,x[2],x[1]=='1',is_rev)

if is_rev:
    S_t = ''.join(list(reversed(S_t)))
    S = ''.join(list(reversed(S)))
    print(''.join([S_t,S,S_h]))
else:
    S_h = ''.join(list(reversed(S_h)))
    print(''.join([S_h,S,S_t]))
### BUGGY CODE ###

def resolve():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))

    max_tmp = [0] * K
    for i in range(len(P) - K + 1):
        tmp = P[i: i + K]
        if sum(max_tmp) < sum(tmp):
            max_tmp = tmp

    ans = 0
    for number in max_tmp:
        dice = list(range(1, number + 1))
        for x in dice:
            p = 1 / number
            px = p * x
            ans += px

    print(ans)


resolve()

### FIXED CODE ###

import itertools


def resolve():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))

    P = [(1 + p) / 2 for p in P]
    accumulate_P = [0] + list(itertools.accumulate(P))

    ans = 0
    for ii in range(N - K + 1):
        range_sum_P = accumulate_P[ii + K] - accumulate_P[ii]
        ans = max(ans, range_sum_P)

    print(ans)

resolve()
### BUGGY CODE ###

import sys
import collections
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    n = I()
    mylist = list(MI())
    mylist.sort(reverse = True)
    mylist = tuple(mylist)
    if mylist[n-1] in mylist[:n-1]:
        result = 0
    else:
        result = 1
    for i in range(n-1):
        temp = mylist[i]
        if mylist.count(temp) <= 1:
            divide = True
            for j in range(i+1,n):
                if temp % mylist[j] == 0:
                    divide = False
                    break
            if divide:
                result += 1
    print(result)

main()

### FIXED CODE ###

import sys
import collections
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    n = I()
    mylist = list(MI())
    max_a = max(mylist)
    exclude_set = set()
    tlist = [False] * (max_a+1)
    for a in mylist:
        if tlist[a]:
            exclude_set.add(a)
        else:
            tlist[a] = True
    ans = 0
    
    for i in range(1, max_a//2 + 1):
        if not tlist[i]:
            continue
        else:
            for j in range(2*i, max_a+1, i):
                tlist[j]=False
    for i in range(len(tlist)):
        if tlist[i] and not i in exclude_set:
            ans += 1
    print(ans)
                
    

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

import itertools
n = int(input())
l = list(map(int,input().split()))
cnt = 0

for x,y,z in itertools.combinations(l,3):
  if x+y >z and y+z >x and z+x >y:
    cnt += 1
print(cnt)

### FIXED CODE ###

import bisect
n = int(input())
l = sorted(list(map(int,input().split())))
cnt = 0

for i in range(n):
  for j in range(1+i,n):
    a,b = l[i],l[j]
    cnt += bisect.bisect_left(l,a+b)-(j+1)
    
print(cnt)
### BUGGY CODE ###

def main():
    N,K = list(map(int, input().split()))
    p = list(map(int, input().split()))
    n = N-K+1
    kitai = [None] * n
    for i in range(N-K+1):
        kitai[i] = ((sum((p[i:i+K]))+K)*0.5)
    print('{:.12f}'.format(max(kitai)))
main()


### FIXED CODE ###

N,K = list(map(int, input().split()))
p = list(map(int, input().split()))
p2 = [p[i]*0.5 + 0.5 for i in range(N)]
size = N + 1
cusum = [0] * size
max = 0

for i in range(N):
    cusum[i+1] = cusum[i] + p2[i]

for i in range(N-K+1):
    tmp = cusum[i+K] - cusum[i]
    if max < tmp:
        max = tmp
print(max)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint
from collections import deque

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

A = []
B = []


# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

# for a, b in zip(A, B):
#     route2[a - 1].append(b - 1)
#     route2[b - 1].append(a - 1)


# 隣接行列
route = [[0 for j in range(N)] for i in range(N)]

for a, b in zip(A, B):
    route[a - 1][b - 1] = route[b - 1][a - 1] = 1


room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue)>0:
    now = queue.popleft()
    # now = stack.pop()
    # next_room = [r for r in room_connection[now] if r not in visited]
    # print('now=', now)
    # print('next_room', next_room)

    # for i in route2[now]:
    #     if i not in visited:

    for i, node in enumerate(route[now]):
        if node == 0:
            continue
    #
        if i not in visited:

            # for r in route2[now]:
            # for r in range(N):
            #     if r not in visited:
            # if route[now][r] and r not in visited:
            # print('r=', r)
            # for r in next_room:
            # if r not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

            # stack.append(r)
            # print(room_depth[now], room_depth[r])

            # if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
            if room_depth[i]:
                room_depth[i] = min(room_depth[now] + 1, room_depth[i])
            else:
                room_depth[i] = room_depth[now] + 1
            #
            # room_sign[i] = now + 1

    # visited.append(now)

    # if set(visited) == set(range(N)):
    #     break

    # print('queue', queue)
    # print('visited', visited)
    # print('depth', room_depth)
    # print('stack', stack)
    # print('sign', room_sign)
    # print('-----')

print('Yes')
for s in room_sign[1:]:
    print(s)


### FIXED CODE ###

# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

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

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
MOD = 1000000007
for i in range(len(A)):
    A[i]=A[i]%MOD
import itertools
c = itertools.combinations(A, 2)
q=0
for v in c:
    q +=v[0]*v[1]%MOD
print(q%MOD)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
MOD = 1000000007
B=0
tem = sum(A)
for i in range(len(A)):
    tem -= A[i]
    B+= (A[i]%MOD)*(tem%MOD)
print(B%MOD)
### BUGGY CODE ###

X = int(input())
i = 1
a = 0
b = 0
while a==0 and b==0:
    for j in range(-i,i):
        if j**5 - i**5 ==X:
            a = j
            b = i
    i = i + 1

### FIXED CODE ###

X = int(input())
# X = a**5 - b**5 
#   = (a-b)(a**4 + a**3 * b + a**2 * b**2 + a * b**3 + b**4)
# よって、X は　a-b　の倍数 X%(a-b) = 0

# a**5  = b**5 + X
#   a   = ( b**5 + X )**(1/5)
# X< 10**9 を満たす a,bの最大値は、120 , 119
flag = False
for ai in range(-119,120):
    for bi in range(-120,119):
        if ai - bi != 0 and X > (ai - bi):
            if X % (ai - bi) == 0:
                if ai**5 - bi**5 ==X:
                    print(int(ai),int(bi))
                    flag = True
                    break
        else:
            if ai**5 - bi**5 ==X:
                print(int(ai),int(bi))
                flag = True
                break
    if flag:
        break
### BUGGY CODE ###

from bisect import bisect

N = int(input())
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
C = sorted(list(map(int,input().split())))
ans = 0
for a in A:
    bIdx = bisect(B,a)
    if N - bIdx > 0:
        for j in range(bIdx,N):
            b = B[j]
            cIdx = bisect(C,b)
            if N - cIdx > 0:
                ans += N-cIdx

print(ans)


### FIXED CODE ###

"""
前処理で下記のようなメモを作っておく必要がある。
candidate[j] -> 昇順ソートされたBの中でインデックスj以降のパーツを使えるときに、考えられるB,Cの組み合わせの数。
candidateリストを作成するためにまずは、下記のmemoを用意して、その総和としてcandidateを作成する。
memo[j] -> Bの中のインデックスjのパーツを使った場合に使用可能なCの数。
"""

def main():
    from bisect import bisect
    import sys
    sys.setrecursionlimit(200000)

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

    memo = [0]*(N)
    for j in range(N):
        b = B[j]
        cIdx = bisect(C,b)
        memo[j] = N-cIdx
    candidate = [0]*(N)
    candidate[-1] = memo[-1]
    for j in range(N-2,-1,-1):
        candidate[j] += candidate[j+1]+memo[j]

    ans = 0
    for a in A:
        bIdx = bisect(B,a)
        if bIdx < N:
            ans += candidate[bIdx]

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

s=int(input())
import math
sq=math.ceil(math.sqrt(s))

big=sq**2
sma=big-s

for i in range(math.floor(math.sqrt(big)),big+1):
    if big%i==0:
        big1=i
        big2=big//i
        break

#print(big1,big2)

if sma!= 0:
    
    for i in range(math.floor(math.sqrt(sma)),sma+1):
        if sma%i==0:
            sma1=i
            sma2=sma//i
            break
else:
    sma1=0
    sma2=0
#print(sma1,sma2)

x1=big1
y1=sma1
x2=sma2
y2=big2
x3=0
y3=0

print(x1,y1,x2,y2,x3,y3)

### FIXED CODE ###

s=int(input())
import math
sq=math.ceil(math.sqrt(s))

big=sq**2
sma=big-s

for i in range(math.floor(math.sqrt(big)),big+1):
    if big%i==0:
        big1=i
        big2=big//i
        break

#print(big1,big2)


if sma!= 0:
    
    for i in range(math.floor(math.sqrt(sma)),0,-1):
        if sma%i==0:
            sma1=i
            sma2=sma//i
            break
else:
    sma1=0
    sma2=0
#print(sma1,sma2)

x1=big1
y1=sma1
x2=sma2
y2=big2
x3=0
y3=0

print(x1,y1,x2,y2,x3,y3)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from collections import deque

from sys import setrecursionlimit

setrecursionlimit(1000000)

INF = float("inf")
# Input#
# n = int(input())
n, m = map(int, input().split())
# a = list(map(int, input().split()))

d = deque()
d_tmp = deque()
x = [-1]
y = [-1]

for _ in [0] * m:
    x_in, y_in = map(int, input().split())
    #    x.append(x_in)
    #    y.append(y_in)
    d.append((x_in, y_in))

memo = [-1] * (n + 1)
ans = -1


def dp(i):
    global ans
    if memo[i] == -1:
        ret = 0
        for x_in, y_in in d:
            if x_in == i:
                tmp = dp(y_in) + 1
                if tmp > ret:
                    ret = tmp
        memo[i] = ret
        if ret > ans:
            ans = ret
        return ret
    else:
        return memo[i]


for i, _ in d:
    if memo[i] == -1:
        dp(i)

print("{}".format(ans))


### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import deque

from sys import setrecursionlimit

setrecursionlimit(1000000)

INF = float("inf")
# Input#
# n = int(input())
n, m = map(int, input().split())
# a = list(map(int, input().split()))

d = deque()
d_tmp = deque()
x = [-1]
y = [[-1] for _ in range((n + 1))]

for _ in [0] * m:
    x_in, y_in = map(int, input().split())
    #    x.append(x_in)
    y[x_in].append(y_in)
    d.append((x_in, y_in))

memo = [-1] * (n + 1)
ans = -1


def dp(i):
    global ans
    if memo[i] == -1:
        ret = 0
        for x_in in y[i][1:]:
            tmp = dp(x_in) + 1
            if tmp > ret:
                ret = tmp
        memo[i] = ret
        if ret > ans:
            ans = ret
        return ret
    else:
        return memo[i]


for i, _ in d:
    if memo[i] == -1:
        dp(i)

print("{}".format(ans))
### BUGGY CODE ###

def main():
  n,k,*a = map(int,open(0).read().split())
  c = [0]
  visit = [False]*n
  visit[0] = True
  for i in range(n):
    nt = a[c[-1]]-1
    if visit[nt]:
      ws = c.index(nt)
      wst = c[:ws]
      wrt = c[ws:]
      wr = len(wrt)
    else:
      c.append(nt)
      visit[nt] = True
  if ws > k:
    ans = wst[k]
  else:
    ans = wrt[(k-ws)%wr]
  print(ans+1)
main()

### FIXED CODE ###

def main():
  n,k,*a = map(int,open(0).read().split())
  c = [0]
  visit = [False]*n
  visit[0] = True
  for i in range(n):
    nt = a[c[-1]]-1
    if visit[nt]:
      ws = c.index(nt)
      wst = c[:ws]
      wrt = c[ws:]
      wr = len(wrt)
      break
    else:
      c.append(nt)
      visit[nt] = True
  if ws > k:
    ans = wst[k]
  else:
    ans = wrt[(k-ws)%wr]
  print(ans+1)
main()
### BUGGY CODE ###

import sys
from bisect import bisect
from itertools import accumulate
import numpy as np

n, t, *ab = map(int, sys.stdin.buffer.read().split())
constant = []
variable = []
for a, b in zip(ab[0::2], ab[1::2]):
    if a == 0:
        constant.append(b + 1)
    else:
        variable.append((a / (b + 1), a, b))
constant.sort()
variable.sort(reverse=True)
INF = 10 ** 10
t += 1
t2 = t.bit_length() + 1
# dp[j]: (i番目まで見て) j件の店で買い物を完了した時の、次の店に到着できる最短時間
dp = np.full(t2, INF, dtype=np.int64)
dp[0] = 1
for _, a, b in variable:
    ndp = (a + 1) * dp + b + 1
    dp[1:] = np.minimum(dp[1:], ndp[:-1])
dp = dp[dp <= t]

const_acc = np.cumsum(constant)
extra = np.searchsorted(const_acc, t - dp, side='right')
print((np.arange(len(extra)) + extra).max())


### FIXED CODE ###

import sys
from bisect import bisect
from itertools import accumulate

n, t = map(int, input().split())
constant = []
variable = []
for line in sys.stdin:
    a, b = map(int, line.split())
    if a == 0:
        constant.append(b + 1)
    else:
        variable.append((a / (b + 1), a, b))
constant.sort()
variable.sort(reverse=True)
INF = 10 ** 10
t += 1
t2 = t.bit_length() + 1
# dp[j]: (i番目まで見て) j件の店で買い物を完了した時の、次の店に到着できる最短時間
dp = [INF] * t2
dp[0] = 1
for _, a, b in variable:
    for j in range(t2 - 1, -1, -1):
        if dp[j] == INF:
            continue
        tmp = (a + 1) * dp[j] + b + 1
        if tmp > t:
            continue
        if dp[j + 1] > tmp:
            dp[j + 1] = tmp

const_acc = list(accumulate(constant))
ans = 0

for i, c in enumerate(dp):
    if c == INF:
        break
    remaining = t - c
    k = bisect(const_acc, remaining)
    ans = max(ans, i + k)

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

import functools, fractions

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

gcd_max = 0

for i in range(n):
  ad = a[:]
  ad[i] = ad[i - 1]
  gcd = functools.reduce(fractions.gcd, ad)
  if gcd > gcd_max:
    gcd_max = gcd

print(gcd_max)

### FIXED CODE ###

from fractions import gcd

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

gcdl = [0] * n
gcdr = gcdl[:]

gcdl[0]  = a[0]
gcdr[-1] = a[-1] 

for i in range(1, n):
  gcdl[i] = gcd(a[i], gcdl[i - 1])

for i in range(n - 2, -1, -1):
  gcdr[i] = gcd(a[i], gcdr[i + 1])

max_gcd = max(gcdl[-2], gcdr[1])

for i in range(1, n - 1):
  temp_gcd = gcd(gcdl[i - 1], gcdr[i + 1])
  if temp_gcd > max_gcd:
    max_gcd = temp_gcd

print(max_gcd)
### BUGGY CODE ###

import itertools
n,k = map(int,input().split())
p = list(map(int,input().split()))
lstp = []
for i in range(n-k+1):
    lstp.append(p[i:i+k])
lstpp = []
for j in lstp:
    lstpp.append(0.5*(sum(j)+k))
print("{:.10f}".format(max(lstpp)))

### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
wa = sum(p[0:k])
next_wa = wa
for i in range(n-k):
    next_wa = next_wa - p[i] + p[i+k]
    if  next_wa > wa:
        wa = next_wa
print(0.5*(wa+k))