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

N = int(input())
b = [int(_) for _ in input().split()]


def delitable(numbers):
    return [v for i, v in enumerate(numbers) if v == i + 1]


b_searched = set()
b_unsearched = []


b_searched.add(tuple(b))
delit = delitable(b)

if delit == []:
    print("-1")
for delit_num in delit:
    b_unsearched.append([[v for i, v in enumerate(b) if delit_num != i + 1], [str(delit_num)]])

while b_unsearched:
    b, log = b_unsearched.pop()

    b_tuple = tuple(b)
    b_searched.add(b_tuple)
    delit = delitable(b)
    if not delit:
        if not b:
            log.reverse()
            print("\n".join(log))
            break
        else:
            continue
    for delit_num in delit:
        b_temp = [v for i, v in enumerate(b) if delit_num != i + 1]
        if not tuple(b_temp) in b_searched:
            b_unsearched.append([b_temp, log + [str(delit_num)]])
else:
    print("-1")

### FIXED CODE ###

N = int(input())
b = [int(_) for _ in input().split()]


def delitable(numbers):
    return [v for i, v in enumerate(numbers) if v == i + 1]


log = []
while b:
    delit = delitable(b)
    if not delit:
        print(-1)
        break
    del b[delit[-1] - 1]
    log.append(delit[-1])
else:
    log.reverse()
    print("\n".join(map(str, log)))
### BUGGY CODE ###

n,k = map(int, input().split( ))
s = input()
c0 = 0
c1 = 0
l0 = []
 
l1 = []
if s[0]=="0":
    l1 = [0]
for i in range(n):
    if s[i]=="0":
        c0+=1
        if c1!=0:
            l1.append(c1)
            c1 = 0
    else:
        c1+=1
        if c0!=0:
            l0.append(c0)
            c0 = 0
if c0:
    l0.append(c0)
if c1:
    l1.append(c1)
 
l1.append(0)

ans = 0
if k >= len(l0):
    print(n)
else:
    nl1 = len(l1)
    for i in range(nl1-k):
        ans = max(ans,(sum(l0[i:i+k])+sum(l1[i:i+k+1])))
    print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
s = list(input())
 
l0 = []
l1 = []
pred = s[0]
if s[0] == "0":
    l0.append(1)
    l1.append(0)
else:
    l1.append(1)
 
for i in range(1,n):
    if pred == s[i]:
        if s[i] == "0":
            l0[-1] += 1
        else:
            l1[-1] += 1
    else:
        if s[i] == "0":
            l0.append(1)
        else:
            l1.append(1)
    pred = s[i]
if s[-1] == "0":    
    l1.append(0)
 
ans = sum(l0[:k])+sum(l1[:k+1])
tmp = ans
for i in range(k,min(len(l0),len(l1))):
    tmp -= l0[i-k]
    tmp -= l1[i-k]
    tmp += l0[i]
    tmp += l1[i+1]
    ans = max(ans, tmp)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import defaultdict
 
def empty_list():
    return [0] * 26
 
class RollingHash():
    def __init__(self, s):
        length = len(s)
        base = 1009
        # self.mod = (1 << 61) - 1
        self.mod = 67280421310721
        self.hash = [0] * (length + 2)
        self.pow = [1] * (length + 2)
 
        for i in range(length):
            self.hash[i+1] = (self.hash[i] + s[i]) * base % self.mod
            self.pow[i+1] = self.pow[i] * base % self.mod
        self.pow[length+1] = self.pow[length] * base % self.mod 
 
    def get(self, l, r):
        t = self.hash[r] - self.hash[l] * self.pow[r-l] % self.mod
        return t % self.mod
 
ss = []
n = int(input())
for _ in range(n):
    ss.append([ord(item) for item in input().rstrip()])
ss.sort(key=lambda x: len(x), reverse=True)
 
orda = ord("a")
words = defaultdict(empty_list)
ans = 0
for s in ss:
    word_len = len(s)
    s_rev = s[::-1]
    RH = RollingHash(s_rev)
    rh = RH.get(0, word_len-1)
    ans += words[rh][s_rev[-1] - orda]
    initial = [0] * 26 
    for i, ch in enumerate(s):
        initial[ch - orda] = 1
        for j, is_initial in enumerate(initial):
            if is_initial:
                rh = RH.get(0, word_len-i-1)
                words[rh][j] += 1
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import defaultdict

def empty_list():
    return [0] * 26

class RollingHash():
    def __init__(self, s):
        length = len(s)
        base = 1009
        # self.mod = (1 << 61) - 1
        self.mod = 67280421310721
        self.hash = [0] * (length + 2)
        self.pow = [1] * (length + 2)

        for i in range(length):
            self.hash[i+1] = (self.hash[i] + s[i]) * base % self.mod
            self.pow[i+1] = self.pow[i] * base % self.mod
        self.pow[length+1] = self.pow[length] * base % self.mod 

    def get(self, l, r):
        t = self.hash[r] - self.hash[l] * self.pow[r-l] % self.mod
        return t % self.mod

ss = []
n = int(input())
for _ in range(n):
    ss.append([ord(item) for item in input().rstrip()])
ss.sort(key=lambda x: len(x), reverse=True)

orda = ord("a")
words = defaultdict(empty_list)
ans = 0
for s in ss:
    word_len = len(s)
    s_rev = s[::-1]
    RH = RollingHash(s_rev)
    rh = RH.get(0, word_len-1)
    ans += words[rh][s_rev[-1] - orda]
    initial = [0] * 26 
    for i, ch in enumerate(s):
        initial[ch - orda] = 1
        for j, is_initial in enumerate(initial):
            if is_initial:
                rh = RH.get(0, word_len-i-1)
                words[rh][j] += 1
print(ans)
### BUGGY CODE ###

n, h = map(int, input().split())
A, B = [], []
for _ in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

B = sorted(B, reverse=True)
bigger = [x for x in B if x >= max(A)]
throw_b = len(bigger)

throw = 0
check = 0

while check == 0:
    if throw >= throw_b:
        break
    h = h - B[throw]
    throw += 1
    if h <= 0:
        break

if h <= 0:
    ans = throw
else:
    ans = throw + -(-h//max(A))

print(ans)

### FIXED CODE ###

n, h = map(int, input().split())
A, B = [], []
for _ in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

B = sorted(B, reverse=True)
a_max = max(A)

bigger = [x for x in B if x >= a_max]
throw_b = len(bigger)

throw = 0
check = 0

while check == 0:
    if throw >= throw_b:
        break
    h = h - B[throw]
    throw += 1
    if h <= 0:
        break

if h <= 0:
    ans = throw
else:
    ans = throw + -(-h//max(A))

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

n = int(input())
ws = []
for _ in range(n):
    ws.append(input())

nums = []
for w in ws:
    v = [0] * 52
    for c in w:
        if "Z" < c:
            v[ord(c) - ord("a")] += 1
        else:
            v[ord(c) - ord("A") + 26] += 1
    nums.append(v)

r = 0
for i in range(n):
    for j in range(n):
        if j <= i:
            continue
        v = 1
        for k in range(52):
            if nums[i][k] != nums[j][k]:
                v = 0
                break
        r += v

print(r)


### FIXED CODE ###

n = int(input())
ws = [list(input()) for _ in range(n)]

def sort_l(l):
    l.sort()
    return l
ws = list(map(sort_l, ws))
ws.sort()

i = 0
j = 0
r = 0
ans = 0
while(i<n-1):
    i += 1
    if ws[i] == ws[j]:
        r += 1
    else:
        ans += r * (r+1) // 2
        r = 0
        j = i
ans += r * (r+1) // 2

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

N, K = map(int,input().split())
H = list(map(int,input().split()))
DP = [0]*(N+1)  #DP[i] iに来るための最小コスト
def dH(i,j):
  return abs(H[i-1] - H[j-1])
for i in range(2,N+1):
  DP[i] = DP[i-1] + dH(i-1, i)
  for j in range(2,K+1):
    if (i-j)>=1:
      DP[i] = min( DP[i], DP[i-j] + dH(i-j, i) )
print(DP[N])

### FIXED CODE ###

N, K = map(int,input().split())
H = list(map(int,input().split()))
import numpy as np
dp = np.zeros(N,dtype=np.int)
harr = np.array(H)
for i in range(1,N):
  St = max(0,i-K)
  Hi = harr[i]
  dp[i] = min(dp[max(0,i-K):i] + np.abs(Hi - harr[max(0,i-K):i]))
print(dp[-1])
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
k = 0
while True:
    for i in l :
        if i % 2 != 0:
            break
        elif i == 2:
            break
        i = i/2
    k += 1
print(k)


### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
k = 0
m = 0
for _ in range(100):
    for i in range(len(l)) :
        if l[i] % 2 != 0  :
            m = 10
            break
        else:
            l[i] = l[i]/2
    if m != 0 :
        break
    k += 1
print(k)
### BUGGY CODE ###

i = list(map(int, input().split()))
limit = int(input())
k = 0
while not i[0] < i[1] < i[2]:
    if i[2] < i[1]:
        i[2] *= 2
        k += 1
    if k == limit:
        break
    if i[1] < i[0]:
        i[1] *= 2
        k += 1
    if k == limit:
        break
if k <= limit and i[0] < i[1] < i[2]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

i = list(map(int, input().split()))
limit = int(input())
k = 0
while not i[0] < i[1] < i[2]:
    if i[2] <= i[1]:
        i[2] *= 2
        k += 1
    if k == limit:
        break
    if i[1] <= i[0]:
        i[1] *= 2
        k += 1
    if k == limit:
        break
if k <= limit and i[0] < i[1] < i[2]:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

N,K = map(int, input().split())
A = [int(i) for i in input().split()]

l=[]
for i in range(N+1):
  l.append(A.count(i))

ls = sorted(l,reverse=True)

j= K
ans = 0
while ls[j] != 0:
  ans += ls[j]

print(ans)

### FIXED CODE ###

import collections as co
N,K = map(int, input().split())
A = list(map(int, input().split()))

ldic = co.Counter(A)        
l = list(ldic.values())
ls = sorted(l,reverse=True)

print(sum(ls[K:]))
### BUGGY CODE ###

mod=10**9+7
n,k=map(int,input().split())
coef=[]
for i in range(1,int(n**0.5)+1):
  coef.append((n//i)-(n//(i+1)))
coef+=[1]*(n-sum(coef))
coef=coef[::-1]
nn=len(coef)
dp=[[0]*nn for _ in range(k+1)]
dp[0][0]=1
for i in range(1,k+1):
  tmp=0
  for j in range(nn-1,-1,-1):
    tmp+=dp[i-1][(nn-1)-j]
    dp[i][j]=coef[j]*tmp
    dp[i][j]%=mod
print(sum(dp[k])%mod)

### FIXED CODE ###

mod=10**9+7
n,k=map(int,input().split())
coef=[]
for i in range(1,int(n**0.5)+1):
  coef.append((n//i)-(n//(i+1)))
coef+=[1]*(n-sum(coef))
coef=coef[::-1]
nn=len(coef)
dp=[[0]*nn for _ in range(k+1)]
dp[0][0]=1
for i in range(1,k+1):
  tmp=0
  for j in range(nn-1,-1,-1):
    tmp+=dp[i-1][(nn-1)-j]
    tmp%=mod
    dp[i][j]=coef[j]*tmp
    dp[i][j]%=mod
print(sum(dp[k])%mod)
### BUGGY CODE ###

from collections import deque
n=int(input())
A=[]
for i in range(n):
  A.append([int(i) for i in input().split()])
nn=n*(n-1)//2
F=[[0]*(n+1) for _ in range(n+1)]
cur=0
for i in range(1,n):
  for j in range(i+1,n+1):
    F[i][j]=cur
    F[j][i]=cur
    cur+=1
Edge=[[] for _ in range(nn)]
Deg=[0]*nn
for i in range(n):
  s=F[i+1][A[i][0]]
  for j in range(1,n-1):
    t=F[i+1][A[i][j]]
    Edge[s].append(t)
    Deg[t]+=1
    s=t
ans=0
S=[i for i in range(nn) if Deg[i]==0]
D=deque()
DD=deque(S)
while DD:
  D=DD
  DD=deque()
  while D:
    d=D.popleft()
    for g in Edge[d]:
      Deg[g]-=1
      if Deg[g]==0:
        DD.append(g)
        S.append(g)
  ans+=1
print(-1 if len(S)<nn else ans)

### FIXED CODE ###

from collections import deque
n=int(input())
A=[]
for i in range(n):
  A.append([int(i) for i in input().split()])
nn=n*(n-1)//2
F=[[0]*(n+1) for _ in range(n+1)]
cur=0
for i in range(1,n):
  for j in range(i+1,n+1):
    F[i][j]=cur
    F[j][i]=cur
    cur+=1
Edge=[[] for _ in range(nn)]
Deg=[0]*nn
for i in range(n):
  s=F[i+1][A[i][0]]
  for j in range(1,n-1):
    t=F[i+1][A[i][j]]
    Edge[s].append(t)
    Deg[t]+=1
    s=t
ans=0
S=[i for i in range(nn) if Deg[i]==0]
D=deque()
DD=deque(S)
while DD:
  D=DD
  DD=deque()
  while D:
    d=D.popleft()
    for g in Edge[d]:
      Deg[g]-=1
      if Deg[g]==0:
        DD.append(g)
        S.append(g)
  ans+=1
print(-1 if len(S)<nn else ans)
### BUGGY CODE ###

import collections
import sys
n = int(input())
d = list(map(int, input().split()))


if d[0]!=0:
    print(0)
    sys.exit(0)
    

m=[1]
p=1


for i in range(1,max(d)+1):
    if collections.Counter(d)[i]==0:
        print(0)
        sys.exit(0)
    elif d[i]==0:
        print(0)
        sys.exit(0)
    else:
        tmp = 1
        for j in range(collections.Counter(d)[i]):
            tmp = (tmp * collections.Counter(d)[i-1]%998244353)%998244353
            
        p = (p * tmp)%998244353
    

print(p)

### FIXED CODE ###

import collections
import sys

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

cnt = collections.Counter(d)

if d[0]!=0:
    print(0)
    sys.exit(0)

if cnt[0]!=1:
    print(0)
    sys.exit(0)    
    
p = 1

for i in range(1,max(d)+1):
    if cnt[i] == 0:
        print(0)
        sys.exit(0)  
    else:
        p = (p * pow(cnt[i-1], cnt[i], 998244353))%998244353

print(p)
### BUGGY CODE ###

N=int(input())
a=[int(i) for i in input().split()]
count=0
for j in range(N):
    for i in range(N-1):
        if(a[i]==j+1):
            count=count+1
    print(count)
    count=0


### FIXED CODE ###

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

d = {}

for i in range(N - 1):
    if A[i] in d:
        d[A[i]].append(i + 2)
    else:
        d[A[i]] = [i + 2]

for i in range(1, N + 1):
    if i in d:
        print(len(d[i]))
    else:
        print(0)
### BUGGY CODE ###

def mod_inverse(n, mod=10**9+7):
    return pow(n, mod-2, mod)


def combination(n, k, mod=10**9+7):
    numer = denom = 1
    for i in range(k):
        numer = (numer * (n-i)) % mod
        denom = (denom * (i+1)) % mod
    return (numer * mod_inverse(denom, mod)) % mod


mod = 10**9+7
n, k = map(int, input().split())

fact = [1] * (n+1)
fact_inv = [1] * (n+1)
for i in range(1, n+1):
    fact[i] = i * fact[i-1] % mod
    fact_inv[i] = mod_inverse(fact[i])

ans = combination(2*n-1, n)
for i in range(k+1, n):
    ans -= combination(n, i) * combination(n-1, i)
    ans %= mod
print(ans)


### FIXED CODE ###

def mod_inverse(n, mod=10**9+7):
    return pow(n, mod-2, mod)


def combination(n, k, mod=10**9+7):
    numer = denom = 1
    for i in range(k):
        numer = (numer * (n-i)) % mod
        denom = (denom * (i+1)) % mod
    return (numer * mod_inverse(denom, mod)) % mod


mod = 10**9+7
n, k = map(int, input().split())

fact = [1] * (n+1)
fact_inv = [1] * (n+1)
for i in range(1, n+1):
    fact[i] = i * fact[i-1] % mod
    fact_inv[i] = mod_inverse(fact[i])

ans = combination(2*n-1, n)
for i in range(k+1, n):
    ans -= (fact[n] * fact_inv[i] * fact_inv[n-i]) * (fact[n-1] * fact_inv[i] * fact_inv[n-1-i])
    # ans -= combination(n, i) * combination(n-1, i)
    ans %= mod
print(ans)
### BUGGY CODE ###

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

S_map = [1 if i=="." else 0 for i in S]
ans = []

for i in range(N+1):
    if(i == 0 or i == N or S[i-1] != S[i]):
        if(i != 0):
            left_white = sum(S_map[:i])
            left_black = i - left_white
        else:
            left_white = 0
            left_black = 0
        if(i != N):
            right_white = sum(S_map[i:])
            right_black = (N - i) - right_white
        else:
            right_white = 0
            right_black = 0
        ans.append(min(left_white+right_white, left_black+right_black, left_black+right_white))
print(min(ans))

### FIXED CODE ###

import numpy as np

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

S_map = [1 if i=="." else 0 for i in S]
cumsum = np.array(S_map).cumsum()
cumsum = np.insert(cumsum, 0, 0)
ans = []

for i in range(N+1):
    if(i == 0 or i == N or S[i-1] != S[i]):
        if(i != 0):
            left_white = cumsum[i]
            left_black = i - left_white
        else:
            left_white = 0
            left_black = 0
        if(i != N):
            right_white = cumsum[-1] - cumsum[i]
            right_black = (N - i) - right_white
        else:
            right_white = 0
            right_black = 0
        ans.append(min(left_white+right_white, left_black+right_black, left_black+right_white))
print(min(ans))
### BUGGY CODE ###

def knapsackBottomUp(wt,price,c,n,m):
    dp=[[float('inf') for x in range(m+1)] for y in range(n+1)]
    for l in range(n+1):
        dp[l][0]=0


    for i in range(1,n+1):
        wi=wt[i];vi=price[i]
        for V in range(1,m+1):
            if vi <= V:
                dp[i][V]=min(wi+dp[i-1][V-vi],dp[i-1][V])
            else:
                dp[i][V]=dp[i-1][V]

    res=0
    for i in range(m+1):
        if dp[n][i]<=c:
            res=i
    return res 
n,c=map(int,input().split())
wt=[]
price=[]
wt.append(0)
price.append(0)
for _ in range(n):
    w,v=map(int,input().split())
    wt.append(w)
    price.append(v)
max_val=sum(price)

print(knapsackBottomUp(wt,price,c,n,max_val))

### FIXED CODE ###

inf=10**10
def knapsackBottomUp(wt,price,c,n,m):
    dp=[[inf for x in range(m+1)] for y in range(n+1)]
    for l in range(n+1):
        dp[l][0]=0


    for i in range(1,n+1):
        wi=wt[i];vi=price[i]
        for V in range(1,m+1):
            if vi <= V:
                dp[i][V]=min(wi+dp[i-1][V-vi],dp[i-1][V])
            else:
                dp[i][V]=dp[i-1][V]

    res=0
    for i in range(m+1):
        if dp[n][i]<=c:
            res=i
    print(res)
n,c=map(int,input().split())
wt=[]
price=[]
wt.append(0)
price.append(0)
for _ in range(n):
    w,v=map(int,input().split())
    wt.append(w)
    price.append(v)
max_val=sum(price)
knapsackBottomUp(wt,price,c,n,max_val)
### BUGGY CODE ###

from sys import stdin


def main():
  n, k = map(int, input().split())
  a = [int(x) for x in stdin.readline().split()]
  l = []
  for i in range(0, n):
    for j in range(i+1, n):
      l.append(a[i]*a[j])
  l.sort()
  print(l[k-1])

if __name__ == '__main__':
  main()

### FIXED CODE ###

from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from functools import reduce
from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm(a, b):
  return a*b//gcd(a, b)


def main():
  n, k = map(int, input().split())
  A = np.array(input().split(), np.int64)
  
  A = np.sort(A)
  
  zero = A[A == 0]
  pos = A[A>0]
  neg = A[A<0]
  
  def F(x):
    cnt_tpl = 0
    #zero multipy ...
    if x>= 0:
      cnt_tpl += len(zero)*n
    #positive multipy ...
    cnt_tpl += np.searchsorted(A, x//pos, side='right').sum()
    cnt_tpl += (n - np.searchsorted(A, (-x-1)//(-neg), side='right')).sum()
    cnt_tpl -= np.count_nonzero(A*A<=x)
    assert cnt_tpl %2 ==0
    return cnt_tpl//2
  
  left = -10**18
  right = 10**18
  while left + 1 < right:
    mid = (left+right)//2
    if F(mid) >= k:
      right = mid
    else:
      left = mid
  print(right)
  
if __name__ == '__main__':
  main()
### BUGGY CODE ###

def dfs(i, V, E):
    for k in range(1, len(V)):
        if V[k] >= 0:
            continue
        for e in E[i]:
            if e[0] == k:
                if e[1] % 2:
                    V[k] = 1 - V[i]
                else:
                    V[k] = V[i]
                V = dfs(k, V, E)
    return V

n = int(input())
E = {}
for i in range(n - 1):
    ui, vi, wi = map(int, input().split())
    if ui in E.keys():
        E[ui].append([vi, wi])
    else:
        E[ui] = [[vi, wi]]
    if vi in E.keys():
        E[vi].append([ui, wi])
    else:
        E[vi] = [[ui, wi]]
V = [-1 for _ in range(n + 1)]
V[1] = 0
V = dfs(1, V, E)
for vi in V[1:]:
    print(vi)


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 5 + 1)

def dfs(i, V, E):
    for k in E[i].keys():
        if V[k] >= 0:
            continue
        if E[i][k] % 2:
            V[k] = 1 - V[i]
        else:
            V[k] = V[i]
        V = dfs(k, V, E)
    return V

n = int(input())
E = {}
for i in range(n - 1):
    ui, vi, wi = map(int, input().split())
    if ui in E.keys():
        E[ui][vi] = wi
    else:
        E[ui] = {vi: wi}
    if vi in E.keys():
        E[vi][ui] = wi
    else:
        E[vi] = {ui: wi}
V = [-1 for _ in range(n + 1)]
V[1] = 0
V = dfs(1, V, E)
for vi in V[1:]:
    print(vi)
### BUGGY CODE ###

H,W,D = map(int,input().split())
A = [list(map(int,input().split())) for i in range(H)]
Q = int(input())
S = [list(map(int,input().split())) for i in range(Q)]
P = [None]*(H*W)
for i in range(H):
    for j in range(W):
        P[A[i][j]-1] = [i,j]
for q in range(Q):
    mp = 0
    left = S[q][0]-1
    for d in range((S[q][1]-S[q][0])//D):
        mp += abs(P[left][0]-P[left+D][0])+abs(P[left][1]-P[left+D][1])
        left += D
    print(mp)

### FIXED CODE ###

H,W,D = map(int,input().split())
A = [list(map(int,input().split())) for i in range(H)]
Q = int(input())
S = [list(map(int,input().split())) for i in range(Q)]
P = [None]*(H*W+1)
for i in range(H):
    for j in range(W):
        P[A[i][j]] = [i,j]

Accum = [0]*(H*W+1)
accum = 0

for i in range(D+1,H*W+1):
    Accum[i] = Accum[i-D]+abs(P[i][0]-P[i-D][0])+abs(P[i][1]-P[i-D][1])

for s in S:
    print(Accum[s[1]]-Accum[s[0]])
### BUGGY CODE ###

from collections import deque
n, k = map(int, input().split())
a = list(map(int, input().split()))

prev = 1
for i in range(k):
    prev *= a[i]

a_old = deque(a)
for i in range(k, n):
    old = a_old.popleft()
    score = prev*a[i] / old
    if score <= prev:
        print('No')
    else:
        print('Yes')
    prev = score

### FIXED CODE ###

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

for i in range(n-k):
    if a[i+k] <= a[i]:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
dp=[1]+[0 for _ in range(n)]
mod=1000000007
for i in range(1,n+1):
    if i in a:
        dp[i]=0
    else:
        dp[i]=(dp[i-1]+dp[i-2])%mod
print(dp[-1])

### FIXED CODE ###

n,m=map(int,input().split())
a=[]
mod=1000000007
for _ in range(m):
    a.append(int(input()))
a=set(a)
ans=[1]+[0]*(n)
for i in range(1,n+1):
    if i in a:
        ans[i]=0
    else:
        ans[i]=(ans[i-1]+ans[i-2])%mod
print(ans[n])
### BUGGY CODE ###

N = int(input())

dic = {}
for n in range(1,N+1):
  dic[n] = int(input())
  
lis = []
now = 1
count = 0
flag = False
while True:
  count += 1
  if now in lis:
    break
  if dic[now] == 2:
    flag = True
    break
  lis.append(now)
  now = dic[now]
  
if flag:
  print(count)
else:
  print(-1)

### FIXED CODE ###

N = int(input())

dic = {}
for n in range(1,N+1):
  dic[n] = int(input())

now = 1
count = 0
flag = False
while True:
  if now==2:
    flag = True
    break
  if now not in dic:
    break
  now = dic.pop(now)
  #del dic[now]
  count += 1

if flag:
  print(count)
else:
  print(-1)
### BUGGY CODE ###

x = int(input())
a = int(x**(1/2))
max_ = 1
    
while a >= 1:
    i = 2
    while a**i < x:
        if max_ <= a**i:
            max_ = a**i
        i += 1
    a -=1
print(max_)

### FIXED CODE ###

x = int(input())
a = int(x**(1/2))
max_ = -1

i = 2

while i <= a:
    j = 2
    while i**j <= x:
        if max_ <= i**j:
            max_ = i**j
        j += 1
    i += 1

if max_ < 0:
    print(1)
else:
    print(max_)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    s=['Vacant','Male', 'Female']
    left=n+1
    sr=input("0")
    while right-left>1:
        mid=(left-right)//2
        x=input(str(mid))
        if x=="Vacant":
            print(str(mid))
            break
        if ((left-right)%2==0 and x!=sr) or (n2%2==1 and x==sr):
            left=mid
        else:
            right=mid
            sr=x
    print(str(right))


if __name__=='__main__':
    main()

### FIXED CODE ###

N=int(input())
l,r=0,N
print(0)
s=input()
ls=s
if s!='Vacant':
    for i in range(19):
        x=l+(r-l)//2
        print(x)
        s=input()
        if s=='Vacant':
            break
        elif (x-l)%2==0 and s==ls or (x-l)%2==1 and s!=ls:
            l=x
            ls=s
        else:
            r=x