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

import sys
readline = sys.stdin.readline

N = int(readline())
A = list(map(int,readline().split()))
DIV = 10 ** 9 + 7

# 各桁の1と0の数を数えて、((1の数) * (0の数)) * (2 ** i桁目(1桁目を0とする))を数える

K = max(A)
for i in range(len(A)):
  A[i] = bin(A[i])[2:][::-1]
  
j = 0
ans = 0
while K:
  one = 0
  for i in range(len(A)):
    if len(A[i]) > j:
      if A[i][j] == "1":
        one += 1
  ans += (one % DIV) * ((N - one) % DIV) * pow(2,j,DIV)
  ans %= DIV
  j += 1
  K >>= 1
  
print(ans)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
binA=[None]*n
for i in range(n):
  binA[i]=bin(A[i])[2:]
  
keta=[0]*60
for i in range(n):
  tar=binA[i]
  for j in range(len(tar)-1,-1,-1):
    if tar[j]=="1":
      keta[len(tar)-1-j]+=1

pair=[0]*60
for i in range(len(keta)):
  pair[i]=keta[i]*(len(A)-keta[i])
  
ans=0
mul=1
DIV=10**9+7
for i in range(len(pair)):
  ans+=pair[i]*mul
  ans%=DIV
  mul*=2
print(ans)
### BUGGY CODE ###

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))

    gcdnum = 1
    gcd = math.gcd

    for a in A:
        gcdnum = (gcdnum * a) // gcd(gcdnum, a)
    ans = 0
    for a in A:
        a = gcdnum // a
        a %= mod
        ans += a
    ans %= mod

    print(ans)




if __name__ == '__main__':
    solve()

### FIXED CODE ###

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))

    lcmnum = 1
    def gcd(a, b):
        if (a == 0):
            return b
        return gcd(b%a, a)

    def lcm(x, y):
        return (x * y) // gcd(x, y)
    for a in A:
        lcmnum = lcm(lcmnum, a)

    ans = 0
    for a in A:
        a = lcmnum // a
        ans += a
    ans %= mod

    print(ans)




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

x,y=map(int,input().split())
b=0
for n in range(x,y+1):
    b=b^n
print(b)

### FIXED CODE ###

x,y=map(int,input().split())
def xor(x):
    if x%2==1:
        return 0 if (x+1)/2 %2==0 else 1
    else:
        return (0 if (x+2)/2 %2==0 else 1)^(x+1)
print(xor(x-1)^xor(y))
### BUGGY CODE ###

def main():
    s = input()
    k = int(input())
    l = set()
    ls = len(s)
    clist = sorted(list(set(list(s))))
    for i in clist:
        x = []
        for j in range(ls):
            if i == s[j]:
                x.append(j)
        l.add(i)
        for j in range(len(x)):
            idx = x[j]
            xxx = s[idx]
            for t in range(idx+1,ls):
                xxx = xxx +s[t]
                l.add(xxx)
        if len(l) >= k:
            l = list(l)
            print(sorted(l)[k-1])
            break
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    s = input()
    k = int(input())
    l = set()
    ls = len(s)
    clist = sorted(list(set(list(s))))
    ladd = l.add
    for i in clist:
        x = []
        for j in range(ls):
            if i == s[j]:
                x.append(j)
        ladd(i)
        for j in range(len(x)):
            idx = x[j]
            xxx = s[idx]
            c = 0
            for t in range(idx+1,ls):
                xxx = xxx +s[t]
                ladd(xxx)
                c += 1
                if c > k:
                    break
        if len(l) >= k:
            l = list(l)
            print(sorted(l)[k-1])
            break
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

K, S = map(int, input().split())
count = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x + y + z == S:
                count += 1
print(count)

### FIXED CODE ###

K, S = map(int, input().split())
count = 0
for x in range(K+1):
    for y in range(K+1):
        if 0 <= S-x-y <= K:
            count += 1
print(count)
### BUGGY CODE ###

def main():
    MOD = 7 + 10**9
    S = tuple(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N)]
    if S[N-1] == '?':
        for m in range(10):
            dp[0][m] = 1
    else:
        tm = int(S[N-1])%13
        dp[0][tm] = 1
    s_1 = [1]
    for n in range(1,N):
        s_1.append((s_1[n-1] * 10)%13)
    for i in range(1,N):
        if S[-1-i] == '?':
            for j in range(13):
                for k in range(10):
                    dp[i][j] =(dp[i][j] + dp[i-1][(j-(k*s_1[i])%13)%13]) % MOD
        else:
            m = (int(S[N-1-i])*10**i) % 13
            for l in range(13):
                dp[i][l] = (dp[i][l] + dp[i-1][(l-m)%13]) % MOD
    print(dp[N-1][5]%MOD)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    MOD = 7 + 10**9
    S = tuple(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] += 1
    s=[1]
    for n in range(1,N):
        s.append((s[n-1]*10)%13)
    for i in range(N):
        for k in range(13):
            if S[-(i+1)] != '?':
                dp[i+1][(k+int(S[-(i+1)])*s[i])%13] += dp[i][k] 
                dp[i+1][(k+int(S[-(i+1)])*s[i])%13] %= MOD
            else:
                for l in range(10):
                    dp[i+1][(k+l*s[i])%13] += dp[i][k]
                    dp[i+1][(k+l*s[i])%13] %= MOD
    print(dp[-1][5])

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

ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import itertools

def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        cnt =0
        while n % b == 0:
            n //= b
            cnt +=1
        if cnt >=1:
            fct.append((b,cnt))
        b = b + 1
    if n > 1:
        fct.append((n,1))
    return fct
def solve():
    n = ni()
    A = lma()
    d=collections.Counter()
    for i in range(n):
        a = A[i]
        fct = factorize(a)
        for fc,cnt in fct:
            d[fc]+=1
            if d[fc]==n:
                break

    f1=True # pp or sp
    f2=True # sp or other
    for num,cnt in d.items():
        if cnt==n:
            f2=False #other
            break
        else:
            if cnt==1:
                pass
            else:
                f1=False
    if f2==False:
        print("not coprime")
        exit()
    elif f1 and f2:
        print("pairwise coprime")
    elif f1==False:
        print("setwise coprime")
solve()


### FIXED CODE ###

ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
gcd=math.gcd

def is_primes(n):
    primes = [1]*n
    primes[0] =0
    primes[1] =0
    for i in range(2,int(n**0.5)+2):
        if primes[i] ==1:
            for j in range(2*i,n,i):
                primes[j] = 0
    return primes
def factorize(n,primes):
    fct = [(1,1)]
    for b in primes:#primes ::sorted
        if b**2 > n:
            break
        cnt =0
        while n % b == 0:
            n //= b
            cnt +=1
        if cnt >=1:
            fct.append((b,cnt))
    if n > 1:
        fct.append((n,1))
    return fct

n =ni()
A = lma()
mx= 10**6+10
prms = is_primes(mx)
prms2=[i for i in range(mx) if prms[i]]
#print(prms2)
d=collections.Counter()
for a in A:
    fct = factorize(a,prms2)
    #print(fct)
    for fc,cnt in fct:
        if fc==1:continue
        d[fc]+=1

f1=True # pp or sp
f2=True # sp or not p
for num,cnt in d.items():
    if cnt==n:
        f2=False #numが全体で共通の約数になる not coprime
        break
    else:
        if cnt==1:## 素
            pass
        else:
            f1=False

if f2==False:
    print("not coprime")
elif f1:
    print("pairwise coprime")
else:
    print("setwise coprime")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

# coding: utf-8


def signed_area(p1, p2, p3):
    '''符号付き面積を計算 '''

    area = (((p2[0] - p1[0]) * (p3[1] - p1[1])) - ((p3[0] - p1[0]) * (p2[1] - p1[1]))) / 2
    return area


def convex_hull(p_list):
    '''グラハムの凸包走査 '''

    p_sort = []
    for i in p_list:
        p_sort.append(i[0])

    # x座標が最小のものをリストの先頭に配置。
    min_index = p_sort.index(min(p_sort))
    min_p = p_list.pop(min_index)
    p_list.insert(0, min_p)

    # 座標最小の点と他の点との角度順にソート ソートアルゴリズムに選択の余地が有る。
    p_length = len(p_list)
    count = 0
    index = 0
    while True:
        count += 1
        index += 1

        area_sign = signed_area(p_list[0], p_list[index], p_list[index + 1])

        # 符号付き面積が負ならば点を入れ替え
        if area_sign < 0:
            p_list[index], p_list[index + 1] = p_list[index + 1], p_list[index]
            count = 0

        if count == p_length - 1:
            break

        if index == p_length - 2:
            index = 0

    # 凹部の点を削除する。
    index = -1
    count = 0
    while True:
        index += 1
        count += 1

        area_sign = signed_area(p_list[index], p_list[index + 1], p_list[index + 2])
        if area_sign < 0:
            del p_list[index + 1]
            count = 0

        if count == len(p_list):
            break

        if index >= len(p_list) - 3:
            index = -1
    return p_list

N = int(input())
p = []
ans = 0
for _ in range(N):
    x,y = map(int,input().split())
    p.append((x,y))
if N == 2:
    x0,y0 = p[0]
    x1,y1 = p[1]
    print(abs(x0-x1)+abs(y0-y1))
    exit()

p = convex_hull(p)
n = len(p)
for i in range(n):
    xi,yi = p[i]
    for j in range(i+1,n):
        xj,yj = p[j]
        tmp = abs(xi-xj)+abs(yi-yj)
        ans = max(tmp,ans)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

# coding: utf-8


def det(p, q):
    return p[0]*q[1] - p[1]*q[0]


def sub(p, q):
    return (p[0]-q[0], p[1]-q[1])


def get_convex_hull(points):
    # どの3点も直線上に並んでいないと仮定する。
    n = len(points)
    points.sort()
    size_convex_hull = 0
    ch = []
    for i in range(n):
        while size_convex_hull > 1:
            v_cur = sub(ch[-1], ch[-2])
            v_new = sub(points[i], ch[-2])
            if det(v_cur, v_new) > 0:
                break
            size_convex_hull -= 1
            ch.pop()
        ch.append(points[i])
        size_convex_hull += 1

    t = size_convex_hull
    for i in range(n-2, -1, -1):
        while size_convex_hull > t:
            v_cur = sub(ch[-1], ch[-2])
            v_new = sub(points[i], ch[-2])
            if det(v_cur, v_new) > 0:
                break
            size_convex_hull -= 1
            ch.pop()
        ch.append(points[i])
        size_convex_hull += 1

    return ch[:-1]

N = int(input())
p = []
ans = 0
for _ in range(N):
    x,y = map(int,input().split())
    p.append((x,y))
if N == 2:
    x0,y0 = p[0]
    x1,y1 = p[1]
    print(abs(x0-x1)+abs(y0-y1))
    exit()

p = get_convex_hull(p)
n = len(p)
for i in range(n):
    xi,yi = p[i]
    for j in range(i+1,n):
        xj,yj = p[j]
        tmp = abs(xi-xj)+abs(yi-yj)
        ans = max(tmp,ans)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
N, K=map(int, input().split())
h=list(map(int, input().split()))
dp = [10**5] * N
dp[0] = 0
for i in range(1, N):
    x = max(0, i-K)
    dp[i] = min([dp[j]+abs(h[j]-h[i]) for j in range(x, i)])
print(dp[-1])

### FIXED CODE ###

N, K=map(int, input().split())
h=list(map(int, input().split()))
dp = [10**5] * N
dp[0] = 0
for i in range(1, N):
    x = max(0, i-K)
    dp[i] = min([dp[j]+abs(h[j]-h[i]) for j in range(x, i)])
print(dp[-1])
### BUGGY CODE ###

count = int(input())
zenbu = []

for x in range(count):
    kosuu = 0
    keihin = str(input())
    flg = False
    
    for y in range(len(zenbu)):
        
        if zenbu[y] == keihin:
            flg = True
        
    if flg == False:
        zenbu.append(keihin)

print(len(zenbu))
        




### FIXED CODE ###

count = int(input())
zenbu = set()
 
for x in range(count):
    keihin = input()
    zenbu.add(keihin)
print(len(zenbu))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import collections

if True:
    n = int(input())
    an= list(map(int, input().split()))

else:
   # n=5
   # an=[1,1,2,1,2]
    n=8
    an=[1,2,1,4,2,1,4,1]

ans = 0
c = collections.Counter(an)
datas = c.most_common()
ans = 0

for k in range(0,n):
    # an2.sort()
    # print(an2)
    ans=0
    for data in datas:
        if data[0] == an[k]:
            if data[1] > 1:
                ans += (data[1]-1) * (data[1]-2)/2
        else:
            ans += data[1] * (data[1]-1)/2
    print(int(ans))



### FIXED CODE ###

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

datas = [0] * (n+1)
for a in an:
    datas[a] += 1

ans = 0
for i in range(1,n+1):
    if datas[i] > 1:
        ans += datas[i] * (datas[i]-1)/2
ans = int(ans)

for k in range(0,n):
    if datas[an[k]] > 1:
        print(int(ans - datas[an[k]] * (datas[an[k]]-1)/2 + (datas[an[k]]-1) * (datas[an[k]]-2)/2))
    else:
        print(ans)
### BUGGY CODE ###

N = int(input())
array = []

for _ in range(N):
    A = int(input())
    if A in array:
        array.remove(A)
    else:
        array.append(A)

print(len(array))

### FIXED CODE ###

N = int(input())
maps = {}

for _ in range(N):
    A = int(input())
    if A in maps:
        maps.pop(A)
    else:
        maps[A] = 1

print(len(maps))
### BUGGY CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from heapq import heappush, heappop
import sys
def main(H, W, K, x1, y1, x2, y2, C):
    time = [[[10**12] * 4 for __ in range(W)] for _ in range(H)]
    dr = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = []
    for i in range(4):
        heappush(q, (0, x1, y1, i))
        time[x1][y1][i] = 0
    while q:
        t, i, j, d = heappop(q)
        timeij = time[i][j]
        if timeij[d] != t: continue
        nt = (t + K - 1) // K * K
        for nd in range(4):
            if nd == d: continue
            if timeij[nd] > nt:
                heappush(q, (nt, i, j, nd))
                timeij[nd] = nt
        ni, nj = i + dr[d][0], j + dr[d][1]
        if not (0 <= ni < H and 0 <= nj < W): continue
        if C[ni][nj] == '@': continue
        timeninj = time[ni][nj]
        if timeninj[d] > t + 1:
            heappush(q, (t + 1, ni, nj, d))
            timeninj[d] = t + 1
    ans = min(time[x2][y2][i] for i in range(4))
    if ans == 10**12:
        print(-1)
    else:
        print((ans + K - 1) // K)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)


### FIXED CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = collections.deque([(x1, y1)])
    dist[x1][y1] = 0
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] == d + 1: continue
                if dist[ni][nj] < d + 1: break
                dist[ni][nj] = d + 1
                q.append((ni, nj))
    ans = dist[x2][y2]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)
### BUGGY CODE ###

from collections import deque

h, w = map(int,input().split())
hw = [input() for i in range(h)]
#for i in range(h):
#    hw.append(input())

# used = [True]*h*w
isBlack = [[None]*w for i in range(h)]

queue = deque([])
for i in range(h):
    for j in range(w):
        if hw[i][j] == '#':
            queue.append([i, j, 0])# h, w, step count
            isBlack[i][j] = True

res = 0
while len(queue) > 0:
    ph, pw, pcnt = queue.popleft()
    if ph > 0 and not isBlack[ph-1][pw]:
        queue.append([ph-1, pw, pcnt+1])
        isBlack[ph-1][pw] = True
    if ph < h-1 and not isBlack[ph+1][pw]:
        queue.append([ph+1, pw, pcnt+1])
        isBlack[ph+1][pw] = True
    if pw > 0 and not isBlack[ph][pw-1]:
        queue.append([ph, pw-1, pcnt+1])
        isBlack[ph][pw-1] = True
    if pw < w-1 and not isBlack[ph][pw+1]:
        queue.append([ph, pw+1, pcnt+1])
        isBlack[ph][pw+1] = True
    #print(queue)
    res = pcnt
print(res)


### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())

field = [] # 白黒情報を持つリスト
mark = [] # 操作回数を保持するリスト
INF = 10**6

for i in range(h):
    field.append(list(input()))
    mark.append([0 for i in range(w)])

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

queue = deque()
for i in range(h):
    for j in range(w):
        if field[i][j] == "#":
            queue.append([i, j])

while len(queue) > 0:
    y, x = queue.popleft()
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= ny < h and 0 <= nx < w:
            if field[ny][nx] == ".":
                mark[ny][nx] = mark[y][x] + 1
                queue.append([ny, nx])
                field[ny][nx] = "#"

ans=0

for i in mark:
    ans = max(ans, max(i))

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

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

g = []
t = sum(a)
s = []

for j in range(100001):
    h = a.count(j)
    g.append(h)

for i in range(q):
    b,c = map(int,input().split())
    if g[b] != 0:
        t = t + c*g[b] - b*g[b]
        g[c] = g[c] + g[b]
        g[b] = 0
        s.append(t)
    else:
        s.append(t)

for m in range(q):
    print(s[m])


### FIXED CODE ###

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

g = [0]*(10**5+1)
t = sum(a)
s = []

for aj in a:
    g[aj]+=1

for i in range(q):
    b,c = map(int,input().split())
    if g[b] != 0:
        t = t + c*g[b] - b*g[b]
        g[c] = g[c] + g[b]
        g[b] = 0
        s.append(t)
    else:
        s.append(t)

for m in range(q):
    print(s[m])
### BUGGY CODE ###

from sys import stdin
H, N = [int(_) for _ in stdin.readline().rstrip().split()]
A = []
B = []

def chmin(a, b):
    if a > b:
        return b
    return a

for i in range(N):
    a, b = [int(_) for _ in stdin.readline().rstrip().split()]
    A.append(a)
    B.append(b)
dp = [float('inf')] * (H + 1)
dp[0] = 0
for i in range(N):
    for j in range(H+1):
        dp[min(j+A[i], H)] = chmin(dp[min(j+A[i], H)], dp[j]+B[i])
print(dp[H])

### FIXED CODE ###

from sys import stdin
H, N = [int(_) for _ in stdin.readline().rstrip().split()]
A = []
B = []

def chmin(a, b):
    if a > b:
        return b
    return a

for i in range(N):
    a, b = [int(_) for _ in stdin.readline().rstrip().split()]
    A.append(a)
    B.append(b)
dp = [float('inf')] * (H + 1)
dp[0] = 0
for i in range(N):
    for j in range(H+1):
        dp[min(j+A[i], H)] = chmin(dp[min(j+A[i], H)], dp[j]+B[i])
print(dp[H])
### BUGGY CODE ###

# 解説AC
MOD = 10**9 + 7


def main():
    S = [s for s in input()[::-1]]
    N = len(S)
    dp = [[0]*13 for i in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        for j in range(13):
            if S[i] != "?":
                a = int(S[i])
                ne = ((a*pow(10, i, 13))+j) % 13
                dp[i+1][ne] += dp[i][j]
                dp[i+1][ne] %= MOD
            else:
                for k in range(10):
                    ne = ((k*pow(10, i, 13))+j) % 13
                    dp[i+1][ne] += dp[i][j]
                    dp[i+1][ne] %= MOD
    print(dp[N][5] % MOD)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# 解説AC
MOD = 10**9 + 7


def main():
    S = [s for s in input()[::-1]]
    N = len(S)
    dp = [[0]*13 for i in range(N+1)]
    dp[0][0] = 1
    d = 1
    for i in range(N):
        for j in range(13):
            if S[i] != "?":
                a = int(S[i])
                ne = ((a*d)+j) % 13
                dp[i+1][ne] += dp[i][j]
                dp[i+1][ne] %= MOD
            else:
                for k in range(10):
                    ne = ((k*d)+j) % 13
                    dp[i+1][ne] += dp[i][j]
                    dp[i+1][ne] %= MOD
        d *= 10
        d %= 13
    print(dp[N][5] % MOD)


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

# -*- coding: utf-8 -*-
"""
Contents   : AtCoder Regular Contest 095 c問題
Author     : Kitaura Hiromi
LastUpdate : 20180414
Since      : 20180414
"""

N = int(input())
X = list(map(int, input().split(" ")))

sorted_X = sorted(X)
for i in range(N):
    j = sorted_X.index(X[i])
    if j < N//2:
        print(sorted_X[N//2])
    else:
        print(sorted_X[N//2-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Contents   : AtCoder Regular Contest 095 c問題
Author     : Kitaura Hiromi
LastUpdate : 20180414
Since      : 20180414
"""
import random
import copy

N = int(input())
X = list(map(int, input().split(" ")))
sorted_X = sorted(X)
med1 = sorted_X[N//2-1]
med2 = sorted_X[N//2]
for i in range(N):
    if X[i] <= med1:
        print(med2)
    else:
        print(med1)
### BUGGY CODE ###

import numpy as np
n, k = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))


tel = np.zeros((63, n), dtype=np.int)
tel[0] = a
for i in range(62):
    for j in range(n):
        tel[i + 1][j] = tel[i][tel[i][j]]

now = 0
for i in range(62, -1, -1):
    if k >> i & 1:
        now = tel[i][now]
print(now + 1)


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))

table = [[0] * n for _ in [0] * 64]
table[0] = a

for i in range(61):
    for j in range(n):
        table[i + 1][j] = table[i][table[i][j]]

ans = 0
for i in range(61, -1, -1):
    if k >> i & 1:
        ans = table[i][ans]
print(ans + 1)
### BUGGY CODE ###

n, k = map(int, input().split(" "))
p = list(map(int, input().split(" ")))
e = []
s = [0]
sj = []

for x in p:
    e.append((1 + x) / 2)

for x in range(n):
    s.append(sum(e[:x + 1]))

for x in range(k, n + 1):
    sj.append(s[x] - s[x - k])
    
print(max(sj))


### FIXED CODE ###

n, k = map(int, input().split(" "))
p = list(map(int, input().split(" ")))
e = []
s = [0]
sj = []

for x in p:
    e.append((1 + x) / 2)

for x in range(n):
    s.append(s[x] + e[x])

for x in range(k, n + 1):
    sj.append(s[x] - s[x - k])
    
print(max(sj))
### BUGGY CODE ###

import sys,math
def prime(m):
  N=range(1,m+2,2)
  r=int(m**.5)
  h=len(N)
  N[0]=0
  for i in range(h):
    x=N[i]
    if x>r:break
    if x and i+x<h:N[i+x:h:x]=[0]*((h-1-i-x)/x+1)
  N[0]=2
  return filter(None,N)
A=map(int,sys.stdin)
n=max(A)+1
B=[0]*n
for e in prime(n):
  for i in range(e,n):B[i]+=1
for e in A:print B[e]

### FIXED CODE ###

import sys,math
def prime(m):
  N=range(1,m+2,2)
  r=int(m**.5)
  h=len(N)
  N[0]=0
  for i in range(h):
    x=N[i]
    if x>r:break
    if x and i+x<h:N[i+x:h:x]=[0]*((h-1-i-x)/x+1)
  N[0]=2
  return filter(None,N)
A=map(int,sys.stdin)
n=max(A)
B=[0]*(n+1)
i=0
c=0
for e in prime(n):
  while e>i:
    B[i]=c
    i+=1
  c+=1
  if i==n+1:break
else:
  for i in range(i,n+1):B[i]=c
for e in A:print B[e]