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

from collections import deque

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

a = [int(x) for x in input().split()]

#ループを探す？

checked_list = [1]
que = deque([a[0]])


counter = 0
while True:
    counter += 1
    x = que.popleft()
    if counter == k:
        print(x)
        exit()
    if x in checked_list:
        startflg = checked_list.index(x)
        loop_length = counter - startflg
        loop_list = checked_list[startflg:counter]
        amari = (k-startflg) % loop_length
        print(loop_list[amari])
        exit()
    else:
        que.append(a[x-1])
        checked_list.append(x)



### FIXED CODE ###

from collections import deque
import sys

def main():
    input = sys.stdin.readline
    n,k = map(int,input().split())

    a = [int(x) for x in input().split()]

    #ループを探す？

    checked_dict = {1:0}
    que = deque([a[0]])

    counter = 0


    while True:
        counter += 1
        x = que.popleft()
        if counter == k:
            print(x)
            exit()
        if x in checked_dict:
            startflg = checked_dict[x]
            loop_length = counter - startflg

            inverse_dict = {v:k for k,v in checked_dict.items()}

            loop_list = [inverse_dict[i] for i in range(startflg,startflg+loop_length)]
            amari = (k-startflg) % loop_length
            print(loop_list[amari])
            exit()
        else:
            que.append(a[x-1])
            checked_dict[x] = counter

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

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

inf = 10 ** 9
dp = [([0] + [inf] * H) for _ in range(N + 1)]

for n in range(1, N + 1):
    a, b = map(int, input().split())
    for h in range(1, H + 1):
        tmp_min = dp[n - 1][h]
        i = 1
        while True:
            if h - i * a <= 0:
                tmp_min = min(tmp_min, dp[n - 1][0] + i * b)
                break
            tmp_min = min(tmp_min, dp[n - 1][h - i * a] + i * b)
            i += 1
        dp[n][h] = tmp_min

print(dp[N][H])


### FIXED CODE ###

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

inf = 10 ** 9
dp = [0] + [inf] * H

for h in range(1, H + 1):
    for n in range(1, N + 1):
        a, b = List[n - 1]
        ref = h - a
        if ref < 0: ref = 0
        dp[h] = min(dp[h], dp[ref] + b)
        

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

N,M = map(int, input().split())
A = []
for i in range(M):
    L, R = map(int, input().split())
    B = list(range(L,R+1))
    A.append(B)
S = set(A[0])
for i in range(M):
    S = set(S) & set(A[i])
print(len(S))
    

### FIXED CODE ###

N, M = map(int, input().split())
L = 0
R = 10**5 +2
for i in range(M):
    l,r = map(int, input().split())
    if L < l:
        L = l
    if R > r:
        R = r
ans = 0
for i in range(1,N+1):
    if L <= i <= R:
        ans += 1
        
print(ans)
### BUGGY CODE ###

n = int(input())

def mysort(lol) :
    l = len(lol)
    if l == 1 :
        return lol
    else :
        return merge(mysort(lol[:l//2]), mysort(lol[l//2:]))

def merge(lol1, lol2) :
    ans = []
    l1, l2 = lol1, lol2
    while l1 != [] and l2 != [] :
        if l1[0][1] > l2[0][1] :
            ans.append(l2.pop(0))
        else :
            ans.append(l1.pop(0))
    else :
        if l1 != [] :
            ans += l1
        else :
            ans += l2
    return ans

ablist = [list(map(int, input().split())) for _ in range(n)]
ablist = mysort(ablist)
wa = 0
for i in ablist :
    wa += i[0]
    if wa > i[1] :
        print("No")
        break
else :
    print("Yes")

### FIXED CODE ###

from operator import itemgetter

n = int(input())

ablist = [list(map(int, input().split())) for _ in range(n)]
ablist = sorted(ablist, key=itemgetter(1))

wa = 0
for i in ablist :
    wa += i[0]
    if wa > i[1] :
        print("No")
        break
else :
    print("Yes")
### BUGGY CODE ###

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

for _ in range(k):
    new=[0]*n
    for i in range(n):
        for j in range(a[i]):
            if 0<=i-(j+1)<n:
                new[i-(j+1)]+=1
            if 0<=i+(j+1)<n:
                new[i+(j+1)]+=1
    a=[i+1 for i in new]
    if all([i==n for i in a]):
        break
print(*a)

### FIXED CODE ###

n,k=map(int, input().split())
a=list(map(int, input().split()))
from itertools import accumulate
for _ in range(k):
    new=[0]*n
    for i in range(n):
        j=a[i]
        l=max(0,i-j)
        r=min(n-1,i+j)
        new[l]+=1
        if r+1<n:
            new[r+1]-=1
    new=list(accumulate(new))
    a=new
    if all([i==n for i in a]):
        break
print(*a)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
flags = [False for i in range(n)]
nums = [0 for i in range(n)]
day = 0
flag = True
while False in flags:
    if flag == False:
        break
    match = set()
    for i in range(n):
        if nums[i] == n - 1:
            continue
        num = a[i][nums[i]] - 1
        if nums[num] == n - 1:
            flag = False
            break
        if a[num][nums[num]] - 1 == i:
            if i not in match and num not in match:
                match.add(i)
                match.add(num)
                nums[i] += 1
                nums[num] += 1
                if nums[i] == n - 1:
                    flags[i] = True
                if nums[num] == n - 1:
                    flags[num] = True
    if not match:
        flag = False
        break
    day += 1
if flag == True:
    print(day)
else:
    print(-1)

### FIXED CODE ###

import sys, collections
input = sys.stdin.readline

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
nums = [0 for i in range(n)]
day = 0
match = 0
flag = True
queue = collections.deque([])
temp = set()
for i in range(1, n + 1):
    i2 = a[i - 1][0]
    if a[i2 - 1][0] == i:
        if i not in temp:
            queue.append([i, i2])
            temp.add(i)
            temp.add(i2)
if not queue:
    flag = False
while queue:
    temp = []
    while queue:
        test = queue.popleft()
        match += 1
        num1, num2 = test[0], test[1]
        nums[num1 - 1] += 1
        nums[num2 - 1] += 1
        temp.append(num1)
        temp.append(num2)
    flag2 = False
    temp2 = set()
    for i in temp:
        if nums[i - 1] <= n - 2:
            new_num = a[i - 1][nums[i - 1]]
            if nums[new_num - 1] <= n - 2 and a[new_num - 1][nums[new_num - 1]] == i:
                if i not in temp2:
                    queue.append([i, new_num])
                    flag2 = True
                    temp2.add(i)
                    temp2.add(new_num)
    if flag2 == False and match < n * (n - 1) // 2:
        flag = False
        break
    day += 1

if flag == True:
    print(day)
else:
    print(-1)
### BUGGY CODE ###

from math import floor


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

    sm_mx = sum(x)

    dp = [[[0] * (sm_mx + 1) for i in range(n + 1)] for j in range(n + 1)]

    dp[0][0][0] = 1

    for i, e in enumerate(x, 1):
        for j in range(n + 1):
            for sm in range(sm_mx + 1):
                if sm < e:
                    dp[i][j][sm] = dp[i-1][j][sm]
                elif j >= 1 and sm >= e:
                    dp[i][j][sm] = dp[i-1][j][sm] + dp[i-1][j-1][sm-e]

    ans = 0
    i_mx = min(floor(sm_mx / a), n)
    for i in range(1, i_mx + 1):
        ans += dp[n][i][i*a]

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


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

    sm_mx = sum(x)

    dp = [[[0] * (sm_mx + 1) for _ in range(n + 1)] for _ in range(n + 1)]

    dp[0][0][0] = 1

    for i, e in enumerate(x, 1):
        for j in range(n + 1):
            for sm in range(sum(x[:i]) + 1):
                if sm < e:
                    dp[i][j][sm] = dp[i-1][j][sm]
                elif j >= 1 and sm >= e:
                    dp[i][j][sm] = dp[i-1][j][sm] + dp[i-1][j-1][sm-e]

    ans = 0
    for i in range(1, n + 1):
        if i > sm_mx / a:
            break
        ans += dp[n][i][i*a]

    print(ans)


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

n = int(input())
a = [int(input()) for _ in range(n)]
a_ = sorted(a)
a_max = a_[-1]
a_second = a_[-2]
 
if a.count(max(a)) >= 2:
    for _ in range(n):
        print(a_max)
else:
    for _ in range(n):
        if a[_] == max(a):
            print(a_second)
        else:
            print(a_max)

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
a_ = sorted(a)
a_max = a_[-1]
a_second = a_[-2]
 
if a.count(a_max) >= 2:
    for _ in range(n):
        print(a_max)
else:
    for _ in range(n):
        if a[_] == a_max:
            print(a_second)
        else:
            print(a_max)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
 
N, u, v = map(int, input().split())
 
u -= 1
v -= 1
 
graph = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
 
lst = []
def calcDist(cur, par, dst):
    global lst
    lst[cur] = dst
    for neighbour in graph[cur]:
        if neighbour == par: continue
        calcDist(neighbour, cur, dst + 1)
        
uDist = [None for i in range(N)]
vDist = [None for i in range(N)]
lst = uDist
calcDist(u, -1, 0)
lst = vDist
calcDist(v, -1, 0)
 
best = 0
 
for node in range(N):
    if uDist[node] < vDist[node]: best = max(best, vDist[node] - 1)
print(best)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
 
N, u, v = map(int, input().split())
 
u -= 1
v -= 1
 
graph = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
 
lst = []
def calcDist(cur, par, dst):
    global lst
    lst[cur] = dst
    for neighbour in graph[cur]:
        if neighbour == par: continue
        calcDist(neighbour, cur, dst + 1)
        
uDist = [None for i in range(N)]
vDist = [None for i in range(N)]
lst = uDist
calcDist(u, -1, 0)
lst = vDist
calcDist(v, -1, 0)
 
best = 0
 
for node in range(N):
    if uDist[node] < vDist[node]: best = max(best, vDist[node] - 1)
print(best)
### BUGGY CODE ###

n = input()
A = sorted(map(int, raw_input().split()), reverse=True)

x = 0
y = 0

def is_lose(x, y):
    return x >= n or y >= A[x]
    
while not is_lose(x+1, y+1):
    x += 1
    y += 1

x_ = x
count_x = 0
while not is_lose(x_+1, y):
    x_ += 1
    count_x += 1
    
y_ = y
count_y = 0
while not is_lose(x, y_+1):
    y_ += 1
    count_y += 1

if (count_x%2 == 0) and (count_y%2 == 0):
    print "Second"
else:
    print "First"

### FIXED CODE ###

n = input()
A = sorted(map(int, raw_input().split()), reverse=True)

x = 0
y = 0

def is_lose(x, y):
    return x >= n or y >= A[x]
    
while not is_lose(x+1, y+1):
    x += 1
    y += 1

x_ = x
count_x = 0
while not is_lose(x_+1, y):
    x_ += 1
    count_x += 1
    
count_y = A[x] - 1 - y

if (count_x%2 == 0) and (count_y%2 == 0):
    print "Second"
else:
    print "First"
### BUGGY CODE ###

N=int(input())

i=0
sortedSet=[]

while i<N:
  temp=input()
  tempSet=[]
  j=0
  while j<len(temp):
    tempSet.append(temp[j])
    j=j+1
  tempSet.sort()
  #print(tempSet)
  sortedSet.append(tempSet)
  i=i+1

result=0
i=0
while i<N:
  j=i+1
  while j<N:
    if sortedSet[i]==sortedSet[j]:
      result=result+1
      #print(i,j)
    j=j+1
  i=i+1

print(result)

### FIXED CODE ###

N=int(input())
 
i=0
sortedSet={}
while i<N:
  temp=''.join(sorted(input()))
  
  if temp in sortedSet:
    sortedSet[temp]=sortedSet[temp]+1
  else:
    sortedSet[temp]=1
  i=i+1

  
result=0
for v in sortedSet.values():
  result=int(result+v*(v-1)/2)
 
print(result)
### BUGGY CODE ###

#dj 16D8101012J ito jun
import sys
def search(a,b):
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            elif prerow[j] < row[j-1]+1:
                row[j] = row[j-1]
            else:
                row[j] = prerow[j]
    return array[-1][-1]

n = int(input())
strs = [list(i) for i in sys.stdin.read().splitlines()]
result = [search(strs[i*2], strs[i*2+1]) for i in range(n)]
print(*result, sep="\n")



### FIXED CODE ###

#dj 16D8101012J ito jun
import sys
def search(a,b):
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            elif prerow[j] < row[j-1]:
                row[j] = row[j-1]
            else:
                row[j] = prerow[j]
    return array[-1][-1]

n = int(input())
strs = [list(i) for i in sys.stdin.read().splitlines()]
result = [search(strs[i*2], strs[i*2+1]) for i in range(n)]
print(*result, sep="\n")
### BUGGY CODE ###

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

A = []
for _ in range(M):
    A.append(int(input()))

step = [0 for _ in range(N+1)]

step[0] = 1
if 1 not in A:
    step[1] = 1

if len(A) != 0 and A[0] == 1:
    A = A[1:]

for i in range(2, N+1):
    if len(A) != 0 and i == A[0]:
        A = A[1:]
    else:
        step[i] = step[i-1] + step[i-2]


print(step[N] % (10**9+7))


### FIXED CODE ###

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

A = []
for _ in range(M):
    A.append(int(input()))

step = [0 for _ in range(N+1)]

ptr = 0

step[0] = 1
step[1] = 1
if ptr < M and A[ptr] == 1:
    step[1] = 0
    ptr += 1

for i in range(2, N+1):
    if ptr < M and i == A[ptr]:
        ptr += 1
    else:
        step[i] = step[i-1] + step[i-2]


print(step[N] % (10**9+7))
### BUGGY CODE ###

x = [int(i) for i in input().split()]

ans = 0

rmax = x[3]/x[0]
for i in range(int(rmax)+1):
    gmax = (x[3] -x[0]*i)/x[1]
    for j in range(int(gmax)+1):
        bmax = (x[3] - x[0]*i - x[1]*j)/x[2]
        for k in range(int(bmax)+1):
            if (x[0]*i + x[1]*j + x[2]*k ) == x[3]:
                ans = ans + 1

print(ans)

### FIXED CODE ###

x = [int(i) for i in input().split()]

ans = 0

rmax = x[3]/x[0]
for i in range(int(rmax)+1):
    gmax = (x[3] -x[0]*i)/x[1]
    for j in range(int(gmax)+1):
        if (x[3]-x[0]*i - x[1]*j)%x[2] == 0:
                ans = ans + 1

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

n, m = map(int, input().split())
info = [list(map(int, input().split())) for _ in range(m)]
info = sorted(info, key=lambda x: x[0])

q = []
for r in info:
	if r[0] == 1:
		q.append(r[1])
		continue

	elif (r[0] in q) and r[1] == n:
		print("POSSIBLE")
		break
else:
	print("IMPOSSIBLE")

### FIXED CODE ###

n, m = map(int, input().split())
side1 = set()
side2 = set()

for i in range(m):
	a, b = map(int, input().split())

	if a == 1:
		side1.add(b)
	
	elif b == n:
		side2.add(a)

print(("" if side1 & side2 else "IM") + "POSSIBLE")
### BUGGY CODE ###

s = input()
n = len(s) 
ls = [0]*(n+1)

for i in range(1,n+1):
  ls[i] = int(s[n-i:]) % 2019

ans = 0
for i in range(1,n+1):
  for j in range(i):
    ans += ((ls[i]-ls[j])%2019 == 0)
print(ans)
       
      
 

### FIXED CODE ###



s = input()
n = len(s) 

rs = [1]*n
for i in range(1,n):
  rs[i] = rs[i-1]*10 %2019
  
ls = [0]*2019
ls[0]+=1

r = 0
for i in range(n-1,-1,-1):
  r += int(s[i]) * (rs[n-i-1])
  r %= 2019
  ls[r] += 1

ans = 0
for a in ls:
  ans += a*(a-1)//2
print(ans)
### BUGGY CODE ###

# dpD - Knapsack 1 (01 knapsack problem)
import sys
input = sys.stdin.readline

def knapsack(W: int, weight: "Array[int]", value: "Array[int]") -> int:
    # dp[i] := optimum value of Weight i
    dp = [0] * (W + 1)
    for w, v in zip(weight, value):
        for cur_w in range(W, w - 1, -1):
            dp[cur_w] = max(dp[cur_w], dp[cur_w - w] + v)
    return dp[-1]


def main():
    N, W = tuple(map(int, input().split()))
    A = tuple(tuple(map(int, input().split())) for _ in range(N))
    weight, value = zip(*A)
    ans = knapsack(W, weight, value)
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

# EduDPD - Knapsack 1
import sys
input = sys.stdin.readline

n, w = list(map(int, input().rstrip().split()))
arr = [tuple(map(int, input().rstrip().split())) for _ in range(n)]
dp = [0] * (w + 1)
for i in range(n):
    for j in range(w, arr[i][0] - 1, -1):
        dp[j] = max(dp[j], dp[j - arr[i][0]] + arr[i][1])
print(max(dp))
### BUGGY CODE ###

s = input()
l_s = []
for i in range(len(s)):
    l_s.append(s[i])

b = True
if len(l_s) == 1:
    print(0)
    exit()

while len(l_s) > 0 and b == True:
    for i in range(len(l_s) - 1):
        if l_s[i] != l_s[i+1]:
            del l_s[i:i+2]
            break
        if i == len(l_s) - 2:
            b = False

ans = len(s) - len(l_s)
print(ans)

### FIXED CODE ###

from collections import Counter
s = input()
c = Counter(s)
print(min(c['1'], c['0'])*2)
### BUGGY CODE ###

import heapq

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

root1 = []
for i in range(n):
    root1.append({})
root2 = []
for i in range(n):
    root2.append({})
   
for i in range(m):
    u, v, a, b = map(int, input().split())
    root1[u - 1][v] = a
    root1[v - 1][u] = a
    root2[u - 1][v] = b
    root2[v - 1][u] = b

def min_cost(root, start): # 経路の端点を１つ指定して任意の点への最小コストを計算
    S = [[0, start]]
    heapq.heapify(S)
    D = [float("inf")] * n
    D[start - 1] = 0
    while len(S) > 0:
        cost, site = heapq.heappop(S)
        """
        if D[site - 1] > cost:
            D[site - 1] = cost
        for site2, cost2 in root[site - 1].items():
            if D[site2 - 1] > cost + cost2:
                heapq.heappush(S, [cost + cost2, site2])
        """
        if D[site - 1] < cost:
            continue
        for site2, cost2 in root[site - 1].items():
            if D[site2 - 1] > cost + cost2:
                D[site2 - 1] = cost + cost2
                heapq.heappush(S, [cost + cost2, site2])
    return D

jpy = min_cost(root1, s) # 円で両替地点まで移動する最小コスト
snuke = min_cost(root2, t) # 両替地点からスヌークで移動する最小コスト
cost = [jpy[i] + snuke[i] for i in range(n)] # 両替地点についてループ

for i in range(n):
    print(10 ** 15 - min(cost[i:]))


### FIXED CODE ###

import heapq

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

root1 = []
for i in range(n):
    root1.append({})
root2 = []
for i in range(n):
    root2.append({})
   
for i in range(m):
    u, v, a, b = map(int, input().split())
    root1[u - 1][v] = a
    root1[v - 1][u] = a
    root2[u - 1][v] = b
    root2[v - 1][u] = b

def min_cost(root, start): # 経路の端点を１つ指定して任意の点への最小コストを計算
    S = [[0, start]]
    heapq.heapify(S)
    D = [float("inf")] * n
    D[start - 1] = 0
    while len(S) > 0:
        cost, site = heapq.heappop(S)
        if D[site - 1] < cost:
            continue
        for site2, cost2 in root[site - 1].items():
            if D[site2 - 1] > cost + cost2:
                D[site2 - 1] = cost + cost2
                heapq.heappush(S, [cost + cost2, site2])
    return D

jpy = min_cost(root1, s) # 円で両替地点まで移動する最小コスト
snuke = min_cost(root2, t) # 両替地点からスヌークで移動する最小コスト
cost = [jpy[i] + snuke[i] for i in range(n)] # 両替地点についてループ

minimum_cost = []
temp_min = cost[n - 1]
for i in reversed(range(n)):
    temp_min = min(temp_min, cost[i])
    minimum_cost.append(temp_min)

for i in reversed(range(n)):
    print(10 ** 15 - minimum_cost[i])
### BUGGY CODE ###

import sys
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
V = [None]*N
E = []
for n in range(N):
	V[n] = list(map(int,inputs().split()))
	V[n][0] -= V[n][2]
	V[n][1] -= V[n][2]
	E.append([V[n][0],1,V[n][2]])
	E.append([V[n][1],-1,V[n][2]])
D = [int(inputs()) for p in [0]*Q]
E.sort(key = lambda x:x[0])
mini = 1000000001
kouho = [1000000001]
q = 0
d = D[0]
flag = False
for e in E:
	cont = False
	mini = 1000000001
	while(e[0] > d):
		if cont == True:
			if mini < 1000000001:
				print(mini)
			else:
				print(-1)
		else:
			mini = min(kouho)
			if mini < 1000000001:
				print(mini)
			else:
				print(-1)
		cont = True
		if q < Q-1:
			q = q + 1
			d = D[q]
		else:
			flag = True
			q = q + 1
			break
	if flag == True:
		break
	if  e[1] == 1:
		kouho.append(e[2])
	elif e[1] == -1:
		kouho.remove(e[2])
for t in [None]*(Q-q):
	print(-1)

### FIXED CODE ###

import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				print(mini-(mini//1000000001)*1000000002)
			else:
				mini = min(kouho)
				print(mini-(mini//1000000001)*1000000002)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			if mini == e[2]:
				cont = False
	for t in [None]*(Q-q):
		print(-1)
main()
### BUGGY CODE ###

def printt(x):
  print(x,flush=True)
  i=input()
  if i=="Vacant":exit()
  if i=="Male":return 0
  return 1
n=int(input())
ng=0
ok=n
f=printt(0)
while ng+1!=ok:
  mid=(ok+ng)//2
  if (printt(mid)==f)^((ng+mid)%2==0):ok=mid
  else:ng=mid

### FIXED CODE ###

n=int(input())
def out(i):
  print(i,flush=True)
  s=input()
  if s=="Male":return 0
  elif s=="Female":return 1
  else:exit()
f=out(0)
ng=0
ok=n
while ng+1!=ok:
  mid=(ng+ok)//2
  if (mid+f)%2==out(mid)%2:ng=mid
  else:ok=mid
### BUGGY CODE ###

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

### FIXED CODE ###

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

S = input()

cnt = 0
for i in range(len(S)):
    for j in range(i+1,len(S)+1):
        if int(S[i:j])%2019 == 0:
            cnt += 1

print(cnt)

### FIXED CODE ###

from itertools import accumulate,chain
from collections import Counter

MOD = 2019

S = input()

memo = [None]*len(S)
x = 1
for i,c in enumerate(reversed(S)):
    memo[i] = x*int(c)%MOD
    x = (10*x)%MOD

acc = tuple(chain((0,), accumulate(memo, lambda x,y: (x+y)%MOD)))

print(sum(c*(c-1)//2 for c in Counter(acc).values()))
### BUGGY CODE ###

import itertools   # accumulate, compress, permutations(nPr), combinations(nCr)
# import bisect      # bisect_left(insert位置), bisect_right(slice用)
# import math        # factorical（階乗) # hypot(距離)
# import heapq
# from fractions import gcd # Python3.5以前 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
from math import gcd # Python3.6以降
# --------------------------------------------------------------

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

cnt = 0

for i in itertools.combinations(bo,3):
    if i[0]<i[1]+i[2] and i[1]<i[2]+i[0] and i[2]<i[0]+i[1]:
        cnt += 1

print(cnt)

### FIXED CODE ###

import itertools   # accumulate, compress, permutations(nPr), combinations(nCr)
import bisect      # bisect_left(insert位置), bisect_right(slice用)
# import math        # factorical（階乗) # hypot(距離)
# import heapq
# from fractions import gcd # Python3.5以前 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # Python3.6以降
# --------------------------------------------------------------

n  = int(input())
bo = list(map(int,input().split()))
 
cnt = 0
bo.sort()
 
for a in range(n-1):
    for b in range(a+1,n):
        cnt += bisect.bisect_left(bo, bo[a]+bo[b]) - (b+1)

print(cnt)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
ans = 0

for i in range(n - k + 1):
    e = 0
    for pi in p[i:i + k]:
        e += sum(range(1, pi + 1)) / pi
    ans = max(e, ans)
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
ans = 0
e = [sum(range(1, pi + 1)) / pi for pi in p]

tmp = 0
for i in range(n):
    tmp += e[i]
    if i >= k:
        tmp -= e[i - k]
    ans = max(ans, tmp)

print(ans)