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

def resolve():
    N, K = list(map(int, input().split()))
    XY = []
    X = []
    Y = []
    for _ in range(N):
        x, y = list(map(int, input().split()))
        XY.append((x, y))
        X.append(x)
        Y.append(y)
    
    X.sort()
    Y.sort()
    
    ans = float("inf")
    for i in range(N-1):
        for j in range(i+1, N):
            for k in range(N-1):
                for l in range(k+1, N):
                    cnt = 0
                    xmin, xmax, ymin, ymax = X[i], X[j], Y[k], Y[l]
                    for x, y in XY:
                        if xmin <= x <= xmax and ymin <= y <= ymax:
                            cnt += 1
                    if cnt >= K:
                        ans = min(ans, abs(xmax-xmin)*abs(ymax-ymin))
    print(ans)




if '__main__' == __name__:
    resolve()


### FIXED CODE ###

def resolve():
    N, K = list(map(int, input().split()))
    XY = []
    X = []
    Y = []
    for _ in range(N):
        x, y = list(map(int, input().split()))
        XY.append((x, y))
        X.append(x)
        Y.append(y)
    
    X.sort()
    Y.sort()
    
    ans = float("inf")
    for i in range(N-1):
        for j in range(i+1, N):
            for k in range(N-1):
                for l in range(k+1, N):
                    cnt = 0
                    xmin, xmax, ymin, ymax = X[i], X[j], Y[k], Y[l]
                    for x, y in XY:
                        if xmin <= x <= xmax and ymin <= y <= ymax:
                            cnt += 1
                    if cnt >= K:
                        ans = min(ans, abs(xmax-xmin)*abs(ymax-ymin))
    print(ans)




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

n=int(input())
s=[0]+[int(input())for i in range(n)]
p=[1]
k=0
while n:
    if s[p[k]]==2:
        print(k+1)
        break
    elif k==len(set(p)):
        print(-1)
        break
    else:
        p.append(s[p[k]])
        k+=1

### FIXED CODE ###

n=int(input())
s=[0]+[int(input())for i in range(n)]
t=s[1]
k=1
while n:
    if t==2:
        print(k)
        break
    elif t==0:
        print(-1)
        break
    else:
        a=s[t]
        s[t]=0
        t=a
        k+=1
### BUGGY CODE ###

import numpy as np
import itertools


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

vals = np.empty((0, 4), int)
for i in range(Q):
    vals = np.append(vals, np.array([list(map(int, input().split(" ")))]), axis=0)
    
maxv = 0
cand = list(itertools.combinations_with_replacement(range(1, M+1), N))
for c in cand:
    sumv = 0
    for v in vals:
        if (c[v[1]-1] - c[v[0]-1]) == v[2]:
            sumv += v[3]
    if maxv < sumv:
        maxv = sumv
print(maxv)

### FIXED CODE ###

import numpy as np
import itertools


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

vals = []
for i in range(Q):
    vals.append(list(map(int, input().split(" "))))
    
maxv = 0
cand = list(itertools.combinations_with_replacement(range(1, M+1), N))
for c in cand:
    sumv = 0
    for v in vals:
        if (c[v[1]-1] - c[v[0]-1]) == v[2]:
            sumv += v[3]
    if maxv < sumv:
        maxv = sumv
print(maxv)
### BUGGY CODE ###

n, m = map(int, input().split())
if m%n==0:
    print(m//n)
else:
    index=1
    while index <m+1:
        if m%index==0:
            if index > n-1:
                print(m//index)
                break
        index+=1

### FIXED CODE ###

import math
import time
n, m = map(int, input().split())
flag=0
if m%n==0:
    print(m//n)

else:
    start = time.time()
    index=m//n
    while index >0:
        elapsedTime = time.time()-start
        if elapsedTime > 1:
            flag=1
            break
        elif m%index==0:
            print(index)
            break
        index-=1

    if flag==1:
        index = 1
        while index < m+1:
            if m % index == 0:
                if index > n-1:
                    print(m//index)
                    break
            index += 1
### BUGGY CODE ###

import sys
N,Y = map(int,input().split(" "))

man_max = Y//10000

go_max = Y // 5000

sen_max = Y // 1000

if man_max > N:
    man_max = N
if go_max > N:
    go_max = N
if sen_max > N:
    sen_max = N

for i in range(sen_max+1):
    for j in range(go_max+1):
        for k in range(man_max+1):
            if (10000*k + 5000*j + 1000*i == Y):
                if i+j+k == N:
                    print(str(k)+" "+str(j) + " " + str(i))
                    sys.exit()

print("-1 -1 -1")

### FIXED CODE ###

import sys
N,Y = map(int,input().split(" "))

man_max = Y//10000

go_max = Y // 5000

sen_max = Y // 1000


for i in range(N,-1,-1):
    for j in range (N-i+1):
        if 10000*i +5000*j +1000*(N-(i+j)) == Y: 
            print(str(i)+" "+str(j) + " " + str(N-(i+j)))
            sys.exit()
print("-1 -1 -1")
### BUGGY CODE ###

N = int(input())
btn = [int(input())-1 for _ in range(N)]
i = 0
li = [0]

while True:
    k = btn[i]
    #print(k, li)
    if k in li:
        print('-1')
        break
    else:
        if k != 1:
            li.append(k)
        else:
            print(len(li))
            break
    i = k

### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    btn = [int(input())-1 for _ in range(N)]
    i = 0
    li = [False]*N
    #print(btn)
    
    for _ in range(N):
        li[i] = True
        k = btn[i]
        
        #print(k, li)
        if li[k]:
            print('-1')
            break
        elif k == 1:
            print(sum(li))
            break
        
        i = k
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def floyd_warshall(dist):
    v = len(dist)
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])


N, M = map(int, input().split())
G = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    G[i][i] = 0
LRD = [None] * M
for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    G[L][R] = D
    LRD[i] = (L, R, D)
floyd_warshall(G)
for L, R, D in LRD:
    if G[L][R] != D or G[R][L] != float('inf'):
        print('No')
        exit()
print('Yes')


### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    G[L].append((R, D))
    G[R].append((L, -D))

visited = [False] * N
dist = [float('inf')] * N
for i in range(N):
    if not visited[i]:
        dist[i] = 0
        stack = [i]
        while stack:
            v = stack.pop()
            visited[v] = True
            for u, d in G[v]:
                if dist[u] == float('inf'):
                    dist[u] = dist[v] + d
                elif dist[u] != dist[v] + d:
                    print('No')
                    exit()
                if not visited[u]:
                    stack.append(u)
print('Yes')
### BUGGY CODE ###

def cal(truck_num, cargos):
    p = []
    
    for i in range(len(cargos) - truck_num + 1):
        if truck_num > 1:
            p.append(max(sum(cargos[:i + 1]), cal(truck_num - 1, cargos[i + 1:])))
        else:
            return sum(cargos)
    return min(p)

if __name__ == "__main__":
    line = input()
    truck_num = int(line.split(" ")[1])
    line_num = int(line.split(" ")[0])
    cargos = []
    for i in range(line_num):
        cargos.append(int(input()))
    print(cal(truck_num,cargos))

### FIXED CODE ###

#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_D
#??????????????????

def cal(truck_num, cargos):
    p = 0
    
    for i in range(len(cargos) - truck_num + 1):
        if not i == 0 and p < sum(cargos[:i + 1]):
            continue
        if truck_num > 1:
            r = max(sum(cargos[:i + 1]), cal(truck_num - 1, cargos[i + 1:]))
            if i == 0:
                p = r
            elif p > r:
                p = r
        else:
            return sum(cargos)
    return p

def check(truck_num, carogs, target_load):
    
    cur_truck = 1
    cur_weight = 0
    for weight in cargos:
        cur_weight += weight
        if cur_weight > target_load:
            cur_weight = weight
            cur_truck += 1
            if cur_truck > truck_num:
                return False
    return True

def solve(truck_num, cargs):

    max_load = sum(cargos)
    min_load = max(cargos)
    #print(min_load, max_load)
    while min_load < max_load:
        target_load = int((min_load + max_load)/2)
        if check(truck_num, cargos, target_load):
            max_load = target_load
        else:
            min_load = target_load + 1
        #print(min_load, max_load)
        
    return max_load

if __name__ == "__main__":
    line = input()
    truck_num = int(line.split(" ")[1])
    line_num = int(line.split(" ")[0])
    cargos = [int(input()) for i in range(line_num)]
    print(solve(truck_num,cargos))
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
lr = []
for i in range(Q):
    lr.append(list(map(int,input().split())))

cl = [0 for i in range(len(S))]

for i in range(1,len(S)):
    if S[i] == 'C' and S[i-1] == 'A':
        cl[i] = cl[i-1] + 1
    else:
        cl[i] = cl[i-1]


#print(cl) 
#print(S)

for l,r in lr:
    sub = cl[l-1:r]
    res = cl[r-1] - cl[l-1] 
    print(res)


### FIXED CODE ###

def main():
    N,Q = map(int,input().split())
    S = input()
    lr = []
    for i in range(Q):
        lr.append(list(map(int,input().split())))

    cl = [0 for _ in range(len(S))]

    for i in range(1,len(S)):
        if S[i] == 'C' and S[i-1] == 'A':
            cl[i] = cl[i-1] + 1
        else:
            cl[i] = cl[i-1]


    #print(cl) 
    #print(S)

    for l,r in lr:
        res = cl[r-1] - cl[l-1] 
        print(res)


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

N,Q = map(int, input().split())
S = input()
A = [0]*N
B = [0]*Q

for i in range(N-1):
    if S[i] == "A" and S[i+1] =="C":
        A[i+1] += 1

for i in range(Q):
    a, b = map(int, input().split())
    B[i] += sum(A[:b])-sum(A[:a])

for a in B:
    print(a)

### FIXED CODE ###

N,Q = map(int, input().split())
S = input()
A = [0]*N


for i in range(1, N):
    if S[i-1] == "A" and S[i] =="C":
        A[i] = A[i-1]+1
    else:
        A[i] = A[i-1]

for i in range(Q):
    a, b = map(int, input().split())
    print(A[b-1] - A[a-1])
### BUGGY CODE ###

from collections import defaultdict
from bisect import *
h, w, n = map(int, input().split())

d = defaultdict(list)
q = [list(map(int, input().split())) for i in range(n)]
q.sort()
ans = [0]*10
for i in range(n):
    a, b = q[i]
    d[a].append(b)

for a, b in q:
    for i in range(max(1, a-2), min(h-2, a)+1):
        for j in range(max(1, b-2), min(w-2, b)+1):
            count = 0
            for k in range(3):
                count += bisect_right(d[i+k], j+2) - bisect_left(d[i+k], j)
            ans[count] += 1


for i in range(1, 10):
    ans[i] //= i

ans[0] = (w-2)*(h-2) - sum(ans[1:])
for i in range(10):
    print(ans[i])


### FIXED CODE ###

from collections import defaultdict
from bisect import *
h, w, n = map(int, input().split())

d = defaultdict(list)
q = [list(map(int, input().split())) for i in range(n)]
q.sort()
ans = [0]*10
for i in range(n):
    a, b = q[i]
    d[a].append(b)

for a, b in q:
    for i in range(max(1, a-2), min(h-2, a)+1):
        for j in range(max(1, b-2), min(w-2, b)+1):
            count = 0
            for k in range(3):
                count += bisect_right(d[i+k], j+2) - bisect_left(d[i+k], j)
            ans[count] += 1


for i in range(1, 10):
    ans[i] //= i

ans[0] = (w-2)*(h-2) - sum(ans[1:])
for i in range(10):
    print(ans[i])
### BUGGY CODE ###

def main():
  import sys
  from heapq import heappush, heappop, heapify
  _int = int
  n = _int(input())
  a = [_int(e) for e in input().split()]
  b = [_int(e) for e in input().split()]
  result = 0
  hq = [(-b[i], i) for i in range(n) if b[i] != a[i]]
  heapify(hq)
  while len(hq) != 0:
    _, i = heappop(hq)
    if i == 0 or i == n - 1:
      j = b[(n + i - 1) % n] + b[(n + i + 1) % n]
    else:
      j = b[i - 1] + b[i + 1]
    if j > b[i]:
      print(-1)
      sys.exit() 
      k = (b[i] - a[i]) // j
      if k == 0:
        k = 1
      result += k
      b[i] -= j * k
    if a[i] > b[i]:
      print(-1)
      sys.exit()
    if a[i] != b[i]:
      heappush(hq, (-b[i], i))
  print(result)
main()

### FIXED CODE ###

def main():
  import sys
  _int = int
  n = _int(input())
  a = [_int(e) for e in input().split()]
  b = [_int(e) for e in input().split()]
  result = 0
  q = [i for i in range(n) if b[i] != a[i]]
  while len(q) != 0:
    nq = []
    c = 0
    for i in q:
      if i == 0 or i == n - 1:
        j = b[(n + i - 1) % n] + b[(n + i + 1) % n]
      else:
        j = b[i - 1] + b[i + 1]
      if j > b[i] - a[i]:
        nq.append(i)
        continue
      c += 1
      k = (b[i] - a[i]) // j
      result += k
      b[i] -= j * k
      if a[i] != b[i]:
        nq.append(i)
    if c == 0 and len(nq) != 0:
      print(-1)
      sys.exit()
    q = nq
  print(result)
main()
### BUGGY CODE ###

import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))

def imo(a):
    imos=[0]*(n+1)

    for i in range(n):
        imos[max(0,i-a[i])]+=1
        imos[min(n,i+a[i]+1)]-=1
    
    immo=[0]*(n+1)
    immo[0]=imos[0]
    for i in range(n):
        immo[i+1]=immo[i]+imos[i+1]

    return immo[:n]

for i in range(min(k,41)):
    a=imo(a)
    
print(*a)


### FIXED CODE ###

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

def imo(a):
    imos=[0]*(n+1)

    for i in range(n):
        imos[max(0,i-a[i])]+=1
        imos[min(n,i+a[i]+1)]-=1
    
    immo=[0]*(n+1)
    immo[0]=imos[0]
    for i in range(n):
        immo[i+1]=immo[i]+imos[i+1]

    return immo[:n]

for i in range(min(k,41)):
    a=imo(a)
    
print(*a)
### BUGGY CODE ###

s = input()
q = int(input())

query = [""]*q
f = [""]*q
c = [""]*q

for i in range(q):
    query[i] = input()
    if query[i]=="1":
        s = s[::-1]
    else:
        r = query[i].split()
        if r[1]=="1":
            s = r[2]+s
        else:
            s += r[2]

print(s)

### FIXED CODE ###

from collections import deque

s = deque(input())
q = int(input())

query = []
rev=1

for i in range(q):
    query.append(input().split())

for i in range(q):
    if query[i][0]=="1":
        rev*=-1
    else:
        if rev==1:
            if query[i][1]=="1":
                s.appendleft(query[i][2])
            else:
                s.append(query[i][2])
        else:
            if query[i][1]=="2":
                s.appendleft(query[i][2])
            else:
                s.append(query[i][2])

result="".join(list(s))
if rev==-1:
    result = result[::-1]
print(result)
### BUGGY CODE ###

from collections import deque
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
INF=10**7

queue = deque()

cost = [[INF]*w for _ in range(h)]
cost[ch-1][cw-1]=0

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
warp = []
for m in range(-2,3):
    for n in range(-2,3):
        if [m,n] not in [[0,0],[1,0],[-1,0],[0,1],[0,-1]]:
            warp += [[m,n]]

queue.append([ch-1,cw-1,0])

while queue:
    x,y,d = queue.popleft()
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d<cost[nx][ny]:
            cost[nx][ny]=d
            queue.appendleft([nx,ny,d])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")

    for dx,dy in warp:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d+1<cost[nx][ny]:            
            cost[nx][ny]=d+1
            queue.append([nx,ny,d+1])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")


if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)



### FIXED CODE ###

from collections import deque
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
INF=10**7

queue = deque()

cost = [[INF]*w for _ in range(h)]
cost[ch-1][cw-1]=0

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
warp = []
for m in range(-2,3):
    for n in range(-2,3):
        if [m,n] not in [[0,0],[1,0],[-1,0],[0,1],[0,-1]]:
            warp += [[m,n]]

queue.append([ch-1,cw-1,0])

while queue:
    x,y,d = queue.popleft()
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d<cost[nx][ny]:
            cost[nx][ny]=d
            queue.appendleft([nx,ny,d])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")

    for dx,dy in warp:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d+1<cost[nx][ny]:            
            cost[nx][ny]=d+1
            queue.append([nx,ny,d+1])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")


if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)
### BUGGY CODE ###

import math
import sys

n = int(input())
a = list(map(int, input().split()))
sumans = 1
for i in a:
    sumans *= i

INF = 1000000000000000000
if (sumans > INF):
    print(-1)
else:
    print(sumans)

### FIXED CODE ###

import math
import sys
import functools
import operator

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


ans = 1
INF = 1000000000000000000

if (0 in a):
    print(0)
    sys.exit()

for i in a:
    ans *= i
    if(ans > INF):
        print(-1)
        sys.exit()

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

[n,k] = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
ls = [0]
ex = [0]
mx = 1001
for i in range(1,mx):
    ls.append(i + ls[i-1])
for i in range(1,mx):
    ex.append(ls[i]/i)
a = []
for i in range(n):
    a.append(ex[p[i]])
#print(a)
ans = -1
ruiseki = []
for i in range(n-k+1):
    ruiseki.append(sum(a[i:i+k]))
print(max(ruiseki))


### FIXED CODE ###

[n,k] = [int(i) for i in input().split()]
p = [(int(i)+1)/2 for i in input().split()]
sm_l = [0]
#sm_r = [0]
for i in range(n):
	sm_l.append(sm_l[-1] + p[i])
	#sm_r.append(sm_r[-1] + p[-i-1])
ans = 0
for i in range(n-k+1):
	ans = max(ans,sm_l[i+k]-sm_l[i])
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
a = [int(i) for i in input().split()]
s = 1
for i in range(k): s *= a[i]
for i in range(k,n):
    tmp = s
    s *= a[i]
    s //= a[i-k]
    if tmp < s: ans = "Yes"
    else: ans = "No"
    print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
a = [int(i) for i in input().split()]
for i in range(k,n):
    if a[i-k] < a[i]: ans = "Yes"
    else: ans = "No"
    print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N=int(input())

i=0
print(i)
ss=input()
if ss == "Vacant":
    exit()
else:
    i=(N-1)//2
    count=4
    while True:
        print(i)
        s=input()
        if s=="Vacant":
            exit()
        elif ss==s:
            i+=max(N//count,2)
            count*=2
        else:
            i-=(N//count,2)
            count*=2

        


### FIXED CODE ###

# coding: utf-8
# Your code here!
N=int(input())

print(N-1)
if input()=="Vacant":
    exit()
print(0)
who=input()
if who=="Male":
    start=0
elif who=="Female":
    start=1
else:
    exit()

high=N-1
low=0
while True:
    mid=(high+low)//2
    print(mid)
    who=input()
    if who=="Male":
        temp=0
    elif who=="Female":
        temp=1
    else:
        exit()
    
    if (mid%2)^start==temp:
        low=mid
    else:
        high=mid
### BUGGY CODE ###

N=int(input())
A=[int(a) for a in input().split()]
ans=1
for i in range(len(A)):
    ans=ans*A[i]
if ans>10**18:
    print(-1)
    exit()
print(ans)


### FIXED CODE ###

N=int(input())
A=[int(a) for a in input().split()]
ans=1
if 0 in A:
    print(0)
    exit()
for i in range(N):
    ans=ans*A[i]
    if ans>10**18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

# coding: utf-8
import string

n = int(input())
a = list(map(int,input().split()))
res = 1
for i in range(n):
    res *= a[i]

if(res>pow(10,18)):
    print(-1)
else:
    print(res)


### FIXED CODE ###

# coding: utf-8
import string

n = int(input())
a = list(map(int,input().split()))
res = 1
for i in range(n):
    res *= a[i]
    if(res>pow(10,18)):
      	break

if(res<=pow(10,18)):
    print(res)
elif(0 in a):
    print(0)
else:
    print(-1)
### BUGGY CODE ###

from collections import deque,defaultdict
import sys
input = sys.stdin.readline
N,M=map(int,input().split())
mod =10**7
table=defaultdict(set)
visit=defaultdict(int)
for i in range(M):
    a,b,c=map(int,input().split())
    table[a].add(a+c*mod)
    table[b].add(b+c*mod)
    table[a+c*mod].add(a)
    table[b+c*mod].add(b)
    table[a+c*mod].add(b+c*mod)
    table[b+c*mod].add(a+c*mod)
    visit[a]=0
    visit[b]=0
    visit[b+c*mod]=0
    visit[a+c*mod]=0

H=deque()
H.append((1,0))
visit[1]=1
ans=mod
while H:
    #print(H)
    x,cost=H.popleft()
    visit[x] = 1
    if x==N:
        ans=min(ans,cost)
        break
    for y in table[x]:
        if visit[y]==1:
            continue
        if x<=10**5 and mod<=y:
            H.append((y,cost+1))
        else:
            H.appendleft((y,cost))
if ans==mod:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

from collections import deque,defaultdict
import sys
input = sys.stdin.readline
N,M=map(int,input().split())
mod =10**7
table=defaultdict(set)
visit=defaultdict(int)
for i in range(M):
    a,b,c=map(int,input().split())
    table[a].add(a+c*mod)
    table[b].add(b+c*mod)
    table[a+c*mod].add(a)
    table[b+c*mod].add(b)
    table[a+c*mod].add(b+c*mod)
    table[b+c*mod].add(a+c*mod)
    visit[a]=0
    visit[b]=0
    visit[b+c*mod]=0
    visit[a+c*mod]=0

H=deque()
H.append((1,0))
visit[1]=1
ans=mod
while H:
    #print(H)
    x,cost=H.popleft()
    visit[x] = 1
    if x==N:
        ans=min(ans,cost)
        break
    for y in table[x]:
        if visit[y]==1:
            continue
        if x<=10**5 and mod<=y:
            H.append((y,cost+1))
        else:
            H.appendleft((y,cost))
if ans==mod:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import heapq
N,M=map(int,input().split())
path=[[0 if i<=j else float("inf") for i in range(N)] for j in range(N)]
for _ in range(M):
  l,r,c=map(int,input().split())
  path[l-1][r-1]=c

dist=[float("inf")]*N
dist[0]=0
q=[[dist[i],i] for i in range(N)]
heapq.heapify(q)

while q:
  d,ind=heapq.heappop(q)
  if d<=dist[ind]:
    for i in range(N):
      if dist[i]>d+path[ind][i]:
        dist[i]=d+path[ind][i]
        heapq.heappush(q,[dist[i],i])

if dist[N-1]==float("inf"):
  print(-1)
else:
  print(dist[N-1])

### FIXED CODE ###

import heapq
N,M=map(int,input().split())
path=[[] for _ in range(N)]
for _ in range(M):
  l,r,c=map(int,input().split())
  path[l-1].append([r,c])
for i in range(1,N):
  path[i].append([i,0])

dist=[float("inf")]*N
dist[0]=0
q=[[dist[i],i] for i in range(N)]
heapq.heapify(q)

while q:
  d,ind=heapq.heappop(q)
  if d<=dist[ind]:
    for i in range(len(path[ind])):
      r,c=path[ind][i]
      if dist[r-1]>d+c:
        dist[r-1]=d+c
        heapq.heappush(q,[dist[r-1],r-1])

if dist[N-1]==float("inf"):
  print(-1)
else:
  print(dist[N-1])
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
	s = int(input())
	if s in a:
		a.remove(s)
	else:
		a.append(s)
print(len(a))

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
	s = int(input())
	a.append(s)
a.sort()
a.append(0)
length = 0
i = 0
while i < n:
	counter = 1
	count = 0
	for k in range(i+1,n+1):
		if a[i] != a[k] and counter%2 == 1:
			length += 1
			i = i+count+1
			break
		elif a[i] != a[k] and counter%2 == 0:
			i = i+count+1
			break
		elif a[i] == a[k]:
			counter += 1
			count += 1
print(length)
### BUGGY CODE ###

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


### FIXED CODE ###

from itertools import accumulate
from operator import add

N, Q = map(int, input().split())
S = input()
idx_list = [1 if S[i:i + 2] == 'AC' else 0 for i in range(len(S) - 1)]
idx_list_cumsum = [0] + list(accumulate(idx_list, add))

for _ in range(Q):
  l, r = map(int, input().split())
  print(idx_list_cumsum[r - 1] - idx_list_cumsum[l - 1])