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

import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    S = input().rstrip()
    ac_idx = []
    for i in range(N-1):
        if S[i:i+2] == 'AC':
            ac_idx.append(i)
    for _ in range(Q):
        l, r = map(int, input().split())
        ans = 0
        for idx in ac_idx:
            if idx >= r-1:
                break
            elif idx >= l-1:
                ans += 1
        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    S = input().rstrip()
    ac_freq = [0]
    for i in range(0, N-1):
        if S[i:i+2] == 'AC':
            ac_freq.append(ac_freq[-1] + 1)
        else:
            ac_freq.append(ac_freq[-1])
    ac_freq.append(ac_freq[-1])
    for _ in range(Q):
        l, r = map(int, input().split())
        print(ac_freq[r-1] - ac_freq[l-1])


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

import math

N = int(input())
x_list = list(map(int, input().split()))
 
result = math.prod(x_list)
if result >1e18:
  print(-1)
else:
  print(result)



### FIXED CODE ###

import math
 
N = int(input())
x_list = list(map(int, input().split()))
 
result = 1
if 0 in x_list:
  print(0)
  exit()
for x in x_list:
  result *= x
  if result > 1e18:
    print(-1)
    exit()
print(result)
### BUGGY CODE ###

#coding:utf-8

n = int(input())
s = input()

count = 0
point = 0
letter_set = {'R','G','B'}

def last_point(c):
    num = None
    for index,letter in enumerate(s):
        if letter == c:
            num = index
    return index

r_num = last_point('R')
g_num = last_point('G')
b_num = last_point('B')

for i in range(point,n-2):
    si = s[i]
    for j in range(i+1,n-1):
        if s[j] != si:
            sj = s[j]
        else:
            continue
        for k in range(j+1,n):
            if s[k] != si and s[k] != sj:
                sk = s[k]
            else:
                continue
            
            num = 0
            l_set = letter_set.copy()
            l_set = l_set - {si} - {sj}
            
            if l_set == {'R'}:
                num = r_num
            elif l_set == {'G'}:
                num = g_num
            elif l_set == {'B'}:
                num = b_num

            if k > num:
                break
            
            if (j - i) != (k - j):
                count += 1

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

### FIXED CODE ###

#coding:utf-8

n = int(input())
s = input()

count = 0
r, g, b = 0, 0, 0

for i in s:
    if i == 'R':
        r += 1
    elif i == 'G':
        g += 1
    elif i == 'B':
        b += 1

count = r * g * b

for i in range(n-2):
    si = s[i]
    for j in range(i+1,n-1):
        sj = s[j]
        nk = 2 * j - i
        if not nk < n:
            break
        snk = s[nk]
        if {si, sj, snk} == {'R','G','B'}:
            count -= 1

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

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

count = n

shakutori = [0] 
for i in range(len(a)):
    shakutori.append(shakutori[i] + a[i])

for l in range(0, n):
    for r in range(l + 1,n):

        right = shakutori[r+1] - shakutori[l]

        left = functools.reduce(lambda x, y: x^y, a[l:r+1])


        if right == left:
            count += 1
print(count)







### FIXED CODE ###

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

count = 0

xor_temp = 0
sum_temp = 0

r = 0
for l in range(n):
    while r < n and xor_temp^a[r]  == sum_temp + a[r]:
        xor_temp ^= a[r]
        sum_temp += a[r]
        r += 1

    xor_temp ^= a[l]
    sum_temp -= a[l]
    count += r - l

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

n = int(input())
S = input()

countlist = []

for i in range(n):
  count1 = S[:i].count("W")
  count2 = S[i+1:].count("E")
  count_tem = count1+count2
  countlist.append(count_tem)
  
an = min(countlist)
print(an)

### FIXED CODE ###

n = int(input())
S = input()

l = [0]*n
wl = [0]*n
el = [0]*n

for i in range(n-1):
  if i == 0:
    wl[i+1] = S[i].count("W")
  else:
    wl[i+1] = S[i].count("W")+wl[i]

for i in reversed(range(1,n)):
  if i == n:
    el[i-1] = S[i].count("E")
  else:
    el[i-1] = S[i].count("E")+el[i]
    
for i in range(n):
  l[i] = wl[i] + el[i]
  
print(min(l))
### BUGGY CODE ###

import heapq
import sys
input = sys.stdin.buffer.readline


def dijkstra(adj, start):
    # adj: [[to, cost] * vertices], 0th index must be empty
    dist = [float('inf')] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, [0, start])
    while q:
        min_dist, v_from = heapq.heappop(q)
        if v_from == 2:
            return dist
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for v_to, cost in v_tos:
            if min_dist + cost < dist[v_to]:
                dist[v_to] = min_dist + cost
                heapq.heappush(q, [dist[v_to], v_to])
    return dist


def main():
    xs, ys, xt, yt = map(int, input().split())
    N = int(input())
    br = [[xs, ys, 0], [xt, yt, 0]]
    for _ in range(N):
        br.append(list(map(int, input().split())))

    adj = [[] for _ in range(N+3)]
    for i in range(N+2):
        for j in range(i+1, N+2):
            dij = max(((br[i][0] - br[j][0])**2 + (br[i][1] - br[j][1])**2) ** (1/2) - (br[i][2] + br[j][2]), 0)
            adj[i+1].append([j+1, dij])
            adj[j+1].append([i+1, dij])

    print(dijkstra(adj, 1)[2])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import heapq
import sys
input = sys.stdin.buffer.readline


def dijkstra(adj, start):
    # adj: [[to, cost] * vertices], 0th index must be empty
    dist = [float('inf')] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        min_dist, v_from = heapq.heappop(q)
        # if v_from == 2:
        #    return dist
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for v_to, cost in v_tos:
            if min_dist + cost < dist[v_to]:
                dist[v_to] = min_dist + cost
                heapq.heappush(q, (dist[v_to], v_to))
    return dist


def main():
    xs, ys, xt, yt = map(int, input().split())
    N = int(input())
    br = [(xs, ys, 0), (xt, yt, 0)]
    for _ in range(N):
        br.append(tuple(map(int, input().split())))

    adj = [[] for _ in range(N+3)]
    for i in range(N+2):
        for j in range(i+1, N+2):
            dij = max(((br[i][0] - br[j][0])**2 + (br[i][1] - br[j][1])**2) ** (1/2) - (br[i][2] + br[j][2]), 0)
            adj[i+1].append([j+1, dij])
            adj[j+1].append([i+1, dij])

    print(dijkstra(adj, 1)[2])


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

import bisect
N, P = map(int, input().split())
if N == 1:
    print(P)
    exit()

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


div_list = make_divisors(P)
ans = 0
for i in range(10 ** 6 + 1):
    idx = bisect.bisect_left(div_list, i ** N)
    if i ** N == div_list[min(idx, len(div_list) - 1)]:
        ans = i
print(ans)

### FIXED CODE ###

def solve(N, P):
    prime_list = []
    for i in range(2, int(P ** (1 / 2)) + 1):
        cnt = 0
        while P % i == 0:
            cnt += 1
            P //= i
        if cnt:
            prime_list.append([i, cnt])
    if P != 1:
        prime_list.append([P, 1])

    ans = 1
    for prime, cnt in prime_list:
        if cnt >= N:
            ans *= prime ** (cnt // N)
    return ans

if __name__ == '__main__':
    n, p = map(int, input().split())
    print(solve(n, p))
### BUGGY CODE ###

import math
N,K=map(int,input().split())
A=list(map(int,input().split()))
def check(x):
  if x==0:
    return 0
  else:
    t=0
    for i in range(N):
      t+=math.ceil(A[i]/x)-1
    if t<=K:
      return 10
    else:
      return 0
low=0
high=max(A)
sig=(low+high)//2
tf=0
if K==0:
  tf=1
  ans=high
while tf==0:
  if check(sig)==10:
    if check(sig-1)==0:
      ans=sig
      break
    else:
      high=sig-1
      sig=(low+sig)//2
  else:
    low=sig+1
    sig=(high+sig)//2
print(ans)


### FIXED CODE ###

import math
N,K=map(int,input().split())
A=list(map(int,input().split()))
def check(x):
  if x==0:
    return 0
  else:
    t=0
    for i in range(N):
      t+=math.ceil(A[i]/x)-1
    if t<=K:
      return 10
    else:
      return 0
low=0
high=max(A)
sig=(low+high)//2
tf=0
if K==0:
  tf=1
  ans=high
while tf==0:
  if check(sig)==10:
    if check(sig-1)==0:
      ans=sig
      break
    else:
      high=sig-1
      sig=(low+high)//2
  else:
    low=sig+1
    sig=(high+low)//2
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
gates = [list(map(int, input().split())) for _ in range(m)]

res = 0
for i in range(n):
    flag = False
    for j in range(m):
        if gates[j][0]-1 <= i < gates[j][1]:
            flag = True
        else:
            flag = False
            break
    
    if flag == True:
        res += 1

print(res)

### FIXED CODE ###

n, m = map(int, input().split())
L, R = [], []
for _ in range(m):
    l,r = map(int, input().split())
    L.append(l)
    R.append(r)


res = min(R) - max(L) + 1
if res < 0:
    print(0)
else:
    print(res)
### BUGGY CODE ###

from itertools import permutations
N, M, R = map(int, input().split())
r = [x - 1 for x in map(int, input().split())]
dist = [[float('inf')] * (N) for _ in range(N)]
for i in range(N): dist[i][i] = 0
for _ in range(M):
    A, B, C = map(int, input().split())
    dist[A - 1][B - 1] = dist[B - 1][A - 1] = C
# Warshall–Floyd algorithm
for k in range(N):
    for i in range(N):
        for j in range(N):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
ans = float('inf')
for p in permutations(r, R):
    ans = min(ans, sum(dist[u][v] for u, v in zip(p, p[1:])))
print(ans)

### FIXED CODE ###

from itertools import permutations
import sys
def main():
    N, M, R = map(int, input().split())
    rs = [x - 1 for x in map(int, input().split())]
    # グラフを作る
    dist = [[float('inf')] * (N) for _ in range(N)]
    for e in sys.stdin:
        A, B, C = map(int, e.split())
        dist[A - 1][B - 1] = dist[B - 1][A - 1] = C
    # ワーシャルフロイドで全頂点間距離算出
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    # 組み合わせ全探索
    ans = float('inf')
    for p in permutations(rs):
        tmp = 0
        for u, v in zip(p, p[1:]):
            tmp += dist[u][v]
            if tmp > ans:
                break
        else:
            ans = tmp
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
p = list(map(float,input().split()))

dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for j in range(n):
        dp[i+1][j+1] += dp[i][j]*p[i]
        dp[i+1][j] += dp[i][j]*(1-p[i])
res = 0
for j in range((n+1)//2,n+1):
    res += dp[n][j]
print(res)

    

### FIXED CODE ###

n = int(input())
p = list(map(float,input().split()))

dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for j in range(n):
        dp[i+1][j+1] += dp[i][j]*p[i]
        dp[i+1][j] += dp[i][j]*(1-p[i])
res = 0
for j in range((n+1)//2,n+1):
    res += dp[n][j]
print(res)
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
t = [list(input()) for _ in range(h)]
d = deque([(Ch, Cw)])
d2 = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = range(-2, 3)

while True:
  # 移動A
  while len(d) != 0:
    Th, Tw = d.popleft()
    d2.append((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  # 移動B
  ans += 1
  while len(d2) != 0:
    Th, Tw = d2.popleft()
    for i in b :
      for j in b :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
          visited[Th][Tw] = 1
  if len(d) == 0:
    print('-1')
    exit()


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()
### BUGGY CODE ###

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

arr = [[0 for j in range(N)] for i in range(N)]
A_tmp = 0

for i in range(N):
    if S[i] == "A":
        A_tmp = 1
    elif A_tmp == 1 and S[i] == "C":
        for j in range(i, N):
            arr[i-1][j] = 1
        A_tmp = 0
    else:
        A_tmp = 0

for i in range(N-1,-1,-1):
    for j in range(len(S)):
        if i < j:
            arr[i][j] = arr[i+1][j] + arr[i][j]







ans_arr = []
for i in range(Q):
    l, r = map(int, input().split())
    
    ans_arr.append(arr[l-1][r-1])

for i in range(Q):
    print(ans_arr[i])

### FIXED CODE ###

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

arr = [0 for j in range(N)]
A_tmp = 0
S_tmp = 0

for i in range(N):
    if S[i] == "A":
        A_tmp = 1
        arr[i] = S_tmp
    elif A_tmp == 1 and S[i] == "C":
        S_tmp += 1
        arr[i] = S_tmp
        A_tmp = 0
    else:
        arr[i] = S_tmp
        A_tmp = 0

ans_arr = []
for i in range(Q):
    l, r = map(int, input().split())
    
    ans_arr.append(arr[r-1]-arr[l-1])

for i in range(Q):
    print(ans_arr[i])
### BUGGY CODE ###

def solve():
    import sys
    input = sys.stdin.readline

    N, M, Q = map(int, input().split())
    Sss = [input().rstrip() for _ in range(N)]

    numVertexss = [[0]*(M+1)] + [[0] + list(map(int, Ss)) for Ss in Sss]
    numEdgeVss = [[0]*(M+1) for _ in range(N+1)]
    numEdgeHss = [[0]*(M+1) for _ in range(N+1)]
    for i in range(1, N):
        for j in range(1, M+1):
            if numVertexss[i][j] and numVertexss[i+1][j]:
                numEdgeVss[i][j] = 1
    for i in range(1, N+1):
        for j in range(1, M):
            if numVertexss[i][j] and numVertexss[i][j+1]:
                numEdgeHss[i][j] = 1

    def getAccAss(Ass):
        for x in range(1, N+1):
            for y in range(M+1):
                Ass[x][y] += Ass[x-1][y]
        for x in range(N+1):
            for y in range(1, M+1):
                Ass[x][y] += Ass[x][y-1]
    def getRangeSum2D(accAss, xFr, xTo, yFr, yTo):
        return accAss[xTo+1][yTo+1] - accAss[xTo+1][yFr] - accAss[xFr][yTo+1] + accAss[xFr][yFr]

    getAccAss(numVertexss)
    getAccAss(numEdgeVss)
    getAccAss(numEdgeHss)

    anss = []
    for _ in range(Q):
        x1, y1, x2, y2 = map(int, input().split())
        x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1
        ans = getRangeSum2D(numVertexss, x1, x2, y1, y2)
        ans -= getRangeSum2D(numEdgeVss, x1, x2-1, y1, y2)
        ans -= getRangeSum2D(numEdgeHss, x1, x2, y1, y2-1)
        anss.append(ans)

    print('\n'.join(map(str, anss)))


solve()


### FIXED CODE ###

def solve():
    import sys
    input = sys.stdin.readline

    N, M, Q = map(int, input().split())
    Sss = [input().rstrip() for _ in range(N)]

    numVertexss = [[0]*(M+1)] + [[0] + list(map(int, Ss)) for Ss in Sss]
    numEdgeVss = [[0]*(M+1) for _ in range(N+1)]
    numEdgeHss = [[0]*(M+1) for _ in range(N+1)]
    for i in range(1, N):
        for j in range(1, M+1):
            if numVertexss[i][j] and numVertexss[i+1][j]:
                numEdgeVss[i][j] = 1
    for i in range(1, N+1):
        for j in range(1, M):
            if numVertexss[i][j] and numVertexss[i][j+1]:
                numEdgeHss[i][j] = 1

    def getAccAss(Ass):
        for x in range(1, N+1):
            for y in range(M+1):
                Ass[x][y] += Ass[x-1][y]
        for x in range(N+1):
            for y in range(1, M+1):
                Ass[x][y] += Ass[x][y-1]
    def getRangeSum2D(accAss, xFr, xTo, yFr, yTo):
        return accAss[xTo+1][yTo+1] - accAss[xTo+1][yFr] - accAss[xFr][yTo+1] + accAss[xFr][yFr]

    getAccAss(numVertexss)
    getAccAss(numEdgeVss)
    getAccAss(numEdgeHss)

    anss = []
    for _ in range(Q):
        x1, y1, x2, y2 = map(int, input().split())
        x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1
        ans = getRangeSum2D(numVertexss, x1, x2, y1, y2)
        ans -= getRangeSum2D(numEdgeVss, x1, x2-1, y1, y2)
        ans -= getRangeSum2D(numEdgeHss, x1, x2, y1, y2-1)
        anss.append(ans)

    print('\n'.join(map(str, anss)))


solve()
### BUGGY CODE ###

N, K, Q = map(int, input().split())
a = [int(input()) for _ in range(Q)]

count = []
for i in range(N):
    count.append(K)

for i in range(Q):
    for j in range(N):
        if j+1 != a[i]:
            count[j] = count[j] - 1
for i in range(N):
    if count[i] <= 0:
        print('No')
    else:
        print('Yes')


### FIXED CODE ###

N, K, Q = map(int, input().split())
a = [int(input()) for _ in range(Q)]

count = []
for i in range(N):
    count.append(K-Q)

for i in range(Q):
    count[a[i]-1] += 1
for i in range(N):
    if count[i] <= 0:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

def main():
    H, W, D = map(int, input().split())
    A = tuple(tuple(map(int, input().split())) for _ in [0] * H)
    Q = int(input())
    LR = tuple(tuple(map(int, input().split())) for _ in [0] * Q)

    grid = dict()
    for i, a in enumerate(A):
        for j, b in enumerate(a):
            grid[b] = (i, j)

    for l, r in LR:
        power = 0
        while 1:
            if l == r:
                break
            else:
                i, j = grid[l]
                x, y = grid[l+D]
                power += abs(x - i) + abs(y - j)
                l += D
        print(power)

main()


### FIXED CODE ###

def main():
    H, W, D = map(int, input().split())
    A = tuple(tuple(map(int, input().split())) for _ in [0] * H)
    Q = int(input())
    LR = tuple(tuple(map(int, input().split())) for _ in [0] * Q)

    grid = dict()
    for i, a in enumerate(A):
        for j, b in enumerate(a):
            grid[b] = (i + 1, j + 1)

    l = H * W
    dist = [0] * (l + 1)
    for i in range(l, 0, -1):
        if i + D <= l:
            dist[i] = abs(grid[i][0] - grid[i+D][0]) + abs(grid[i][1] - grid[i+D][1]) + dist[i+D]
        else:
            dist[i] = 0

    for l, r in LR:
        print(dist[l] - dist[r])

main()
### BUGGY CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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


class Node:
    def __init__(self, index):
        self.index = index
        self.point = 0

    def updatePoints(self, point):
        self.point += point


nodes = [Node(i) for i in range(1, n + 1)]


edges = defaultdict(list)
for _ in range(n-1):
    a, b = map(int, input().split())
    edges[a].append(b)


def selectNode(p):
    selected = [p]
    ls = edges[p]
    selected += ls

    while True:
        if ls == []:
            break
        for x in ls:
            ls = edges[x]
            selected += ls
    return selected

for _ in range(q):
    p, x = map(int, input().split())
    node_index_list = selectNode(p)
    for idx, node in enumerate(nodes):
        if idx + 1 in node_index_list:
            node.updatePoints(x)

print(*(node.point for node in nodes))


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, q = map(int, input().split())

graph = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a].append(b)
    graph[b].append(a)

values = [0]*n
for _ in range(q):
    p, x = map(int, input().split())
    values[p-1] += x

def dfs(v1, parent, add):
    values[v1] += add
    for v2 in graph[v1]:
        if v2 == parent:
            continue
        dfs(v2, v1, values[v1])

dfs(0, 0, 0)
print(*values)
### BUGGY CODE ###

import bisect

n,c,k = list(map(int, input().split()))
t = []
for i in range(n):
	t.append(int(input()))
t.sort()

ans = 0
while len(t)>0:
	pi = t[0]
	mens = bisect.bisect_right(t,pi+k)
	bus = mens//c
	if bus!=0:
		ans+=bus
		t = t[bus*c:]
	else:
		ans+=1
		t = t[mens:]
print(ans)

### FIXED CODE ###

import bisect

n,c,k = list(map(int, input().split()))
t = []
for i in range(n):
	t.append(int(input()))
t.sort()

ans = 0
remain = c-1
if c==1:
	print(n)
	exit()
time = t[0]
for i in range(1,len(t)):
	if time+k<t[i]:
		time = t[i]
		remain = c
		ans+=1
	if remain==0:
		remain=c
		time = t[i]
		ans+=1
	remain-=1

print(ans+1)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n = I()
edge = [[] for _ in range(n)]
for v in range(1,n):
    u = I()-1
    edge[u].append(v)

dp = [inf]*n
def dfs(s):
    if edge[s] == []:
        dp[s] = 0
        return 0
    tmp = []
    for v in edge[s]:
        tmp.append(dfs(v))
    tmp.sort(reverse=True)
    m = max(list((i+1+j) for i,j in enumerate(tmp)))
    dp[s] = m
    return m

dfs(0)
print(dp[0])

### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n = I()
edge = [[] for _ in range(n)]
for v in range(1,n):
    u = I()-1
    edge[u].append(v)

dp = [None]*n
def dfs(s):
    if dp[s] != None:
        return dp[s]
    if edge[s] == []:
        dp[s] = 0
        return 0
    tmp = []
    for v in edge[s]:
        tmp.append(dfs(v))
    tmp.sort(reverse=True)
    m = 0
    for i,j in enumerate(tmp):
        m = max(m,(i+1)+j)
    dp[s] = m
    return m

dfs(0)
print(dp[0])