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

import copy, itertools

N, M, R = map(int, input().split())
r = [x-1 for x in list(map(int, input().split()))]

way_cost = [[float('inf')]*N for _ in range(N)]

for idx in range(N):
    way_cost[idx][idx] = 0

for _ in range(M):
    a, b, c = map(int, input().split())
    way_cost[a-1][b-1] = c
    way_cost[b-1][a-1] = c

# ワーシャルフロイド法で全ての街同士の最短距離を求める
shortest_path_cost = copy.deepcopy(way_cost)
for between_point in range(N):
    for start_point in range(N):
        for end_point in range(N):
            shortest_path_cost[start_point][end_point] \
            = min(shortest_path_cost[start_point][end_point], \
            shortest_path_cost[start_point][between_point]+shortest_path_cost[between_point][end_point])

# 巡回ルートを総当りで調べ、最小コストを出力する
route_list = list(itertools.permutations(r))
ans = float('inf')
for route in route_list:
    cost = 0
    for idx in range(R-1):
        cost += shortest_path_cost[route[idx]][route[idx+1]]
    ans = min(ans,cost)

print(ans)


### FIXED CODE ###

import copy, itertools
from scipy.sparse.csgraph import floyd_warshall

N, M, R = map(int, input().split())
r = [x-1 for x in list(map(int, input().split()))]

way_cost = [[float('inf')]*N for _ in range(N)]

for idx in range(N):
    way_cost[idx][idx] = 0

for _ in range(M):
    a, b, c = map(int, input().split())
    way_cost[a-1][b-1] = c
    way_cost[b-1][a-1] = c

# ワーシャルフロイド法で全ての街同士の最短距離を求める
shortest_path_cost = floyd_warshall(csgraph=way_cost, directed=False)

# 巡回ルートを総当りで調べ、最小コストを出力する
route_list = list(itertools.permutations(r))

ans = float('inf')
for route in route_list:
    cost = 0
    for idx in range(R-1):
        cost += shortest_path_cost[route[idx]][route[idx+1]]
    ans = min(ans,cost)

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

import sys
input = sys.stdin.readline
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for i in range(h):
   s.append(input().rstrip('\n'))

INF = 10 ** 10
d = [INF] * (h*w)

stack = deque([(ch-1, cw-1, 0)])

nex = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i, j) in [(-1,0),(1,0),(0,-1),(0,1),(0,0)]:
            continue
        else:
            nex.append((i,j))

while stack:
    curh, curw, cnt = stack.popleft()
    if d[curh * w + curw] <= cnt:
        continue
    else:
        d[curh * w + curw] = cnt
    for dh, dw in ((-1,0), (1,0), (0,1), (0,-1)):
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt:
            stack.appendleft((nh, nw, cnt))
    for dh, dw in nex:
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and  d[nh * w + nw] > cnt:
            stack.append((nh, nw, cnt+1))

# for item in d:
#     print(item)
gh -= 1
gw -= 1

if d[gh*w + gw] == INF:
    print(-1)
else:
    print(d[gh*w + gw])


### FIXED CODE ###

import sys
input = sys.stdin.readline

import heapq

INF = 10 ** 10

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    h = []
    heapq.heappush(h, (0, s))

    while h:
        # 使っていない頂点のうち、現時点で最も距離の近いものを選びvとする
        d, v = heapq.heappop(h)
        if dist[v] < d:
            continue
        # vから到達可能な頂点について、距離が短くなれば更新
        for end, cost in G[v]:
            if dist[end] > dist[v] + cost:
                dist[end] = dist[v] + cost
                heapq.heappush(h, (dist[end], end))
    return dist


H, W = map(int, input().split())
N = H * W
ch, cw = map(lambda x:int(x)-1, input().split())
gh, gw = map(lambda x:int(x)-1, input().split())

s = []
es = tuple([] for i in range(N))

for h in range(H):
   s.append(input().rstrip('\n'))

for h in range(H):
    for w in range(W):
        if s[h][w] != '.':
            continue
        a = h*W+w
        esappend = es[a].append
        for dh in (-2, -1, 0, 1, 2):
            for dw in (-2, -1, 0, 1, 2):
                if dh == 0 and dw == 0:
                    continue
                nh = h + dh
                nw = w + dw
                if 0 <= nh and nh < H and 0 <= nw and nw < W and s[nh][nw] == '.':
                    b = nh*W+nw
                    if (dh, dw) in [(-1,0),(1,0),(0,-1),(0,1)]:
                        esappend((b, 0))
                    else:
                        esappend((b, 1))

dist = dijkstra(N, es, ch*W+cw)
if dist[gh*W+gw] == INF:
    print(-1)
else:
    print(dist[gh*W+gw])
### BUGGY CODE ###

import numpy as np

N=int(input())
A=list(map(int, input().split()))
Q=int(input())
B,C=map(int, input().split())
rep=[i for i, x in enumerate(A) if x == B]
for i in range(len(rep)):
    A[rep[i]]=C
ans=np.cumsum(A)
print(ans[-1])

for _ in range(Q-1):
    B,C=map(int, input().split())
    rep=[i for i, x in enumerate(A) if x == B]
    for i in range(len(rep)):
        A[rep[i]]=C
    ans[-1]+=(C-B)*len(rep)
    print(ans[-1])

### FIXED CODE ###

mod=pow(10,5)+2
N=int(input())
num=[0]*mod
ans=0
A=list(map(int, input().split()))
for i in range(N):
    num[A[i]]+=1
    ans+=A[i]
Q=int(input())
for i in range(Q):
    B,C=map(int, input().split())
    cnt=num[B]
    num[C]+=num[B]
    num[B]=0
    ans+=(C-B)*cnt
    print(ans)
### BUGGY CODE ###

s=list(input())
count=0
for i in range(len(s)-2):
    if s[i:i+3]==['A','B','C']:
        count+=1
        s[i]='B'
        s[i+1]='C'
        s[i+2]='A'
        for j in range(1,len(s)):
            if i-j<0:
                break
            if s[i-j]=='A':
                count+=1
                s[i-j]='B'
                s[i-j+1]='C'
                s[i-j+2]='A'
                
            
            else:
                break
        
print(count)


        
    
        

        
    


### FIXED CODE ###

s=list(input())
count=0
count1=0
for i in range(len(s)-2):
    if s[i:i+3]==['A','B','C']:
        count+=1
        s[i]='B'
        s[i+1]='C'
        s[i+2]='A'

            
        for j in range(1,len(s)):
            if i-j<0:
                count+=count1
                break
            if s[i-j]=='A':
                count1+=1
            else:
                count+=count1
                break
            
    if s[i:i+3]==['A','A','A'] or s[i:i+3]==['A','A','B'] or s[i:i+3]==['C','A','A'] or s[i:i+3]==['C','A','B'] or s[i:i+3]==['B','C','A']:
        continue
    else:
        count1=0


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

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dfs(x):
        res = 1
        for y in v[x]:
            if d[y]:
                d[y] = 0
                res += dfs(y)
        t[x] = res
        return res

    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    t = [0]*n
    d = [1]*n
    d[0] = 0
    dfs(0)
    ans = 0
    p = pow(2,n-1,mod)
    for x in range(n):
        tx = t[x]
        if len(v[x]) < 2:
            continue
        s = p-1
        for y in v[x]:
            ty = t[y]
            if tx < ty:
                s -= pow(2,t[0]-tx,mod)-1
            else:
                s -= pow(2,ty,mod)-1
            s %= mod
        ans += s
        ans %= mod
    print(ans*pow(2,(mod-2)*n%(mod-1),mod)%mod)
    return

#Solve
if __name__ == "__main__":
    solve()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    q = deque([0])
    d = [0]*n
    d[0] = 1
    pre = [None]*n
    while q:
        x = q.popleft()
        nd = d[x]+1
        for y in v[x]:
            if not d[y]:
                d[y] = nd
                pre[y] = x
                q.append(y)
    V = list(range(1,n))
    V.sort(key = lambda x:-d[x])
    size = [1]*n
    for i in V:
        size[pre[i]] += size[i]
    inv = pow(2,mod-2,mod)
    ans = (1-pow(inv,n,mod)-n*inv)%mod
    p = [pow(inv,i,mod) for i in range(n)]
    for i in range(1,n):
        a = size[i]
        b = n-a
        ans += (p[a]-1)*(p[b]-1)%mod
        ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

p = int(input())


def div(a, b):
    n = len(a)
    m = len(b)
    res = [0] * (n - m + 1)
    tmp = pow(b[-1], p - 2, p)
    for i in range(n - m, -1, -1):
        t = a[i + m - 1] * tmp % p
        res[i] = t
        for j in range(m):
            a[i + j] = (a[i + j] - t * b[j]) % p
    return res


a = list(map(int, input().split()))
ans = [0] * p
f = [0] * (p + 1)
f[0] = 1
for i in range(p):
    for j in range(p, 0, -1):
        f[j] += f[j - 1]
        f[j - 1] = -f[j - 1] * i
        f[j] %= p
for i in range(p):
    if a[i] == 1:
        fm = div(f[:], [-i, 1])
        t = 1
        r = 0
        for v in fm:
            r += v * t
            t = t * i % p
        t = pow(r, p - 2, p)
        for j in range(len(fm)):
            ans[j] += fm[j] * t % p
for i in range(p):
    ans[i] %= p
print(' '.join(map(str, ans)))


### FIXED CODE ###

p = int(input())


def div(a, b):
    n = len(a)
    m = len(b)
    res = [0] * (n - m + 1)
    tmp = pow(b[-1], p - 2, p)
    for i in range(n - m, -1, -1):
        t = a[i + m - 1] * tmp % p
        res[i] = t
        for j in range(m):
            a[i + j] = (a[i + j] - t * b[j]) % p
    return res


a = list(map(int, input().split()))
ans = [0] * p
f = [0] * (p + 1)
f[0] = 1
for i in range(p):
    for j in range(p, 0, -1):
        f[j] += f[j - 1]
        f[j - 1] = -f[j - 1] * i
        f[j] %= p
for i in range(p):
    if a[i] == 1:
        fm = div(f[:], [-i, 1])
        t = 1
        r = 0
        for v in fm:
            r += v * t
            t = t * i % p
        t = pow(r, p - 2, p)
        for j in range(len(fm)):
            ans[j] += fm[j] * t
for i in range(p):
    ans[i] %= p
print(' '.join(map(str, ans)))
### BUGGY CODE ###

import bisect
N = int(input())
P_id = [0]*(N + 1)
for i, p in enumerate(map(int, input().split())):
    P_id[p] = i
    
A = [- 1, P_id[N], N] 

res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))

print(res)

### FIXED CODE ###

import bisect
import array
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = array.array('i', [- 1, P_id[N], N])


res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))

print(res)
### BUGGY CODE ###

from functools import lru_cache

numbers = input().split()
x = input().split()
y = input().split()
z = input().split()

k = int(numbers[3])


x.sort(reverse=True)
y.sort(reverse=True)
z.sort(reverse=True)

answer = []
for i in x:
    for j in y:
        for m in z:
            price = int(i)+int(j)+int(m)
            answer.append(price)

answer.sort(reverse=True)
del answer[k::]

for l in answer:
    print(l)


### FIXED CODE ###

numbers = input().split()
x = input().split()
y = input().split()
z = input().split()

k = int(numbers[3])

answer = []
for i in x:
    for j in y:
        price = int(i)+int(j)
        answer.append(price)
answer.sort(reverse=True)
del answer[k::]
f_ans = []
for m in answer:
    for n in z:
        price = m + int(n)
        f_ans.append(price)

f_ans.sort(reverse=True)
del f_ans[k::]

for l in f_ans:
    print(l)
### BUGGY CODE ###

N = int(input())
a_list = [int(input()) for _ in range(N)]

button_history = [1]
while True:
    next_button = a_list[button_history[-1] - 1]
    if next_button == 2:
        print(len(button_history))
        break
    elif next_button in button_history:
        print(-1)
        break
    else:
        button_history.append(next_button)


### FIXED CODE ###

N = int(input())
a_list = [int(input()) for _ in range(N)]

button_history = [1]
current_button = 1
num_manipulation = -1

for i in range(1, N + 1):
    current_button = a_list[current_button - 1]
    if current_button == 2:
        num_manipulation = i
        break

print(num_manipulation)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
B=[0]*N
for i in range(N):
  B[A[i]-1]=i+1

ans=''
for i in range(N-1):
  ans = ans + str(B[i])+' '
ans = ans + str(B[N-1])
print(ans)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
B=[0]*N
for i in range(N):
  B[A[i]-1]=i+1
print(*B)
### BUGGY CODE ###

H, W = map(int, input().split())
maze = []
for i in range(H):
    maze.append(list(input()))
    
from collections import deque
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
# 最大の地点を
def dfs(sx, sy, gx, gy):
    que = deque()
    # 各点までの最長距離の配列
    d = [[-1 for _ in range(W)] for _ in range(H)]
    que.append([sx, sy])
    d[sx][sy] = 0
    
    while(len(que) != 0):
        front = que.popleft()
        if (front[0] == gx and front[1] == gy):
            break
        for i in range(4):
            nx = front[0] + dx[i]
            ny = front[1] + dy[i]
            if (0 <= nx and nx < H and 0 <= ny and ny < W):
                if maze[nx][ny] != "#" and d[nx][ny] == -1:
                    que.append([nx, ny])
                    d[nx][ny] = d[front[0]][front[1]] + 1
                else:
                    continue
            else:
                continue
    return d[gx][gy]

import itertools

ans = []
l1 = [(s1, s2) for s1 in range(H) for s2 in range(W)]
p = itertools.product(l1, l1)

for v in p:
    if maze[v[0][0]][v[0][1]] == "#" or maze[v[1][0]][v[1][1]] == "#":
        continue
    ans.append(dfs(v[0][0], v[0][1], v[1][0], v[1][1]))
print(max(ans))

### FIXED CODE ###

H, W = map(int, input().split())
maze = []
for i in range(H):
    maze.append(list(input()))
    
from collections import deque
import numpy as np
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
# 最大の地点を
def dfs(sx, sy):
    que = deque()
    # 各点までの最長距離の配列
    d = [[-1 for _ in range(W)] for _ in range(H)]
    que.append([sx, sy])
    d[sx][sy] = 0
    
    while(len(que) != 0):
        front = que.popleft()
        for i in range(4):
            nx = front[0] + dx[i]
            ny = front[1] + dy[i]
            if (0 <= nx and nx < H and 0 <= ny and ny < W):
                if maze[nx][ny] != "#" and d[nx][ny] == -1:
                    que.append([nx, ny])
                    d[nx][ny] = d[front[0]][front[1]] + 1
                else:
                    continue
            else:
                continue
    return np.max(d)

import itertools

ans = []
l1 = [(s1, s2) for s1 in range(H) for s2 in range(W)]


for v in l1:
    if maze[v[0]][v[1]] == "#":
        continue
    ans.append(dfs(v[0], v[1]))
print(max(ans))
### BUGGY CODE ###

import bisect
import itertools
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
count = 0
#for i in range(n):
  #for s in range(bisect.bisect_right(b, a[i]),n):
    #count += n-bisect.bisect_right(c, b[s])
for i in itertools.product(a, b, c):
  if i[0] < i[1] < i[2]:
    count += 1
print(count)

### FIXED CODE ###

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

import bisect
ans=0
for i in b:
    q=bisect.bisect_left(a,i)
    s=bisect.bisect_right(c,i)
    ans=ans+q*(n-s)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
readline = sys.stdin.readline #文字列入力のときは注意

n,q = [int(i) for i in readline().split()]
p = []
x = []
arr = [[] for i in range(n)]
ans = [0 for i in range(n)]
omosa = [0 for i in range(n)]

for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    arr[a-1].append(b-1)
    arr[b-1].append(a-1)
for i in range(q):
    tmpp,tmpx = [int(i) for i in readline().split()]
#    p.append(tmpp-1)
#    x.append(tmpx)
    omosa[tmpp-1] += tmpx

#for i in range(q):
#    omosa[p[i]] +=x[i]

def dfs(start, oya, weight): #weightは自分より上のノードの重さの和
    ans[start] = weight + omosa[start]
    for child in arr[start]:
        if child != oya:
            dfs(child, start, ans[start])
 
dfs(0,-1,0)
print(*ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
readline = sys.stdin.readline #文字列入力のときは注意

n,q = [int(i) for i in readline().split()]
p = []
x = []
arr = [[] for i in range(n)]
ans = [0 for i in range(n)]
omosa = [0 for i in range(n)]

for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    arr[a-1].append(b-1)
    arr[b-1].append(a-1)
for i in range(q):
    tmpp,tmpx = [int(i) for i in readline().split()]
#    p.append(tmpp-1)
#    x.append(tmpx)
    omosa[tmpp-1] += tmpx

#for i in range(q):
#    omosa[p[i]] +=x[i]

def dfs(start, oya, weight): #weightは自分より上のノードの重さの和
    ans[start] = weight + omosa[start]
    for child in arr[start]:
        if child != oya:
            dfs(child, start, ans[start])
 
dfs(0,-1,0)
print(*ans)
### BUGGY CODE ###

N=int(input())
A=[int(input()) for _ in range(N)]
B=sorted(A)[:N-1]
m=max(A)
for i in range(N):
    if  A[i]==m:
        print(max(B))
    else:
        print(m)

### FIXED CODE ###

N=int(input())
A=[int(input()) for _ in range(N)]
B=sorted(A)[:N-1]
m=max(A)
n=A.index(max(A))
for i in range(N):
    if  i!=n:
        print(m)
    else:
        print(max(B))
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

import copy

S = list(input())
N = len(S)
masu= [1] * N

old = [1] * N
loop = 0
while True:
    new = [0] * N
    for i, children in enumerate(masu):
        if S[i] == "L":
            next_i = i - 1
        else:
            next_i = i + 1
        new[next_i] += children
    if new == old:
        if loop % 2 == 0:
            last = masu 
        else:
            last = new
        break
    loop += 1
    old = copy.copy(masu)
    masu = copy.copy(new)

# これ知らなかった
print(*last)

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

S = list(input())
N = len(S)

masu = []
char = ""
for i, s in enumerate(S):
    if char == "":
        char += s
        continue
    if char[-1] == s:
        char += s
        continue
    if char[-1] != s:
        masu.append(len(char))
        char = s
        continue
if char:
    masu.append(len(char))

import math

ans = []
for l, r in zip(*[iter(masu)]*2):
    n = len(ans)
    pos_l = n + l
    pos_r = pos_l + 1
    l_num = math.ceil(l / 2) + r // 2
    r_num = l // 2 + math.ceil(r / 2)
    for _ in range(l-1):
        ans.append(0)
    ans.append(l_num)
    ans.append(r_num)
    for _ in range(r-1):
        ans.append(0)

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

num = int(input())
wr = str(input())


r_num = wr.count("R")
i_counts = [r_num]
rw_count = r_num
wr_count = 0
for i in range(num):
  if wr[i] == "W":
    wr_count += 1
  else:
    rw_count -= 1
  i_count = max(wr_count, rw_count)
  i_counts.append(i_count)

  ans = min(i_counts)

print(ans)

### FIXED CODE ###

num = int(input())
wr = str(input())

r_num = wr.count("R")
i_counts = [r_num]
rw_count = r_num
wr_count = 0
for i in range(num):
  if wr[i] == "W":
    wr_count += 1
  else:
    rw_count -= 1
  i_count = max(wr_count, rw_count)
  i_counts.append(i_count)

ans = min(i_counts)

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

import numpy as np

N, C, K = map(int, input().split(" "))
T = np.sort([int(input()) for _ in range(N)])

i = 0
j = C
bus = 0
while i < N:
    bus += 1
    lst = T[i:j]
    i += len(lst[lst - lst[0] <= K])
    j = i + C
print(bus)

### FIXED CODE ###

N, C, K = map(int, input().split(" "))
T = sorted([int(input()) for _ in range(N)])

bus = 0
i = 0
while i < N:
    bus += 1
    start = i
    while i < N and T[i] - T[start] <= K and i - start < C:
        i += 1
print(bus)
### BUGGY CODE ###

import math
a,b,n = map(int,input().split())
max = 0
for x in range(1,n+1):
    m = math.floor(a*x/b) - a * math.floor(x/b)
    if max < m:
        max = m
        
print(max)

### FIXED CODE ###

import math
def f(A,B,x):
    return math.floor(A*x/B) - A*math.floor(x/B)

A,B,N = map(int,input().split())
x = min(N,B-1)
print(f(A,B,x))
### BUGGY CODE ###

N =int(input())
s = sorted((sorted(input()) for i in range(N)))
cnt = 0
for i in range(N):
    cnt+=(s[i+1:]).count(s[i])
print(cnt)

### FIXED CODE ###

import collections

N =int(input())
s = ["".join(sorted(input())) for _ in range(N)]
c = collections.Counter(s)
cnt = 0
ans =0
for i in set(s):
    cnt = c[i]
    ans += cnt*(cnt-1)//2
print(ans)
### BUGGY CODE ###

import math
N = int(input())

for i in range(1, N + 1):
  max_num = math.ceil(math.sqrt(i)) + 1
  count = 0
  for x in range(1, max_num):
    for y in range(1, max_num):
      for z in range(1, max_num):
        val = x * x + y * y + z * z + x * y + y * z + z * x
        if val == i:
          count += 1
        if val > i:
          break
  print(count)

### FIXED CODE ###

N = int(input())

ans = [0] * 10001
for x in range(1, 100):
  for y in range(1, 100):
    for z in range(1, 100):
      val = x * x + y * y + z * z + x * y + y * z + z * x
      if val < len(ans):
        ans[val] += 1

for i in range(1, N + 1):
  print(ans[i])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

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

A=[X]
s=N
for i in range(1,N):
    a=A[i-1]**2%M
    if a in A:
        s=A.index(a)
        break
    else:
        A.append(a)

if len(A)==N:
    ans=sum(A)
else:
    ans=0
    l=len(A)-s

    ans+=sum(A[:s])
    S=sum(A[s:])
    T=(N-s)//l
    ans+=T*S
    K=N-s-l*T
    for i in range(K):
        ans+=A[i+s]


print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

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

A=[0]*10**5
A[0]=X
D=dict()
#A=[X]
s=N
for i in range(1,N):
    a=A[i-1]**2%M
    if a in D:
        s=A.index(a)
        break
    else:
        #A.append(a)
        A[i]=a
        D[a]=0

if s==N:
    ans=sum(A)
else:
    A=A[:i]
    Z=[0]*(len(A)+1)
    for i in range(1,len(A)+1):
        Z[i]=Z[i-1]+A[i-1]  

    ans=0
    l=len(A)-s
    #ans+=sum(A[:s])
    ans+=Z[s]
    #S=sum(A[s:])
    S=Z[len(A)]-Z[s]
    T=(N-s)//l
    ans+=T*S
    K=N-s-l*T
    #ans+=sum(A[s:(s+K)])
    ans+=Z[s+K]-Z[s]


print(ans)