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

inf = 0x101010
def floyd(P,m):
	for k in range(m):
		for i in range(m):
			for j in range(m):
				P[i][j]=min(P[i][j],P[i][k]+P[k][j])

while 1:
	n,m = map(int,raw_input().split())
	if n == 0: break
	C = [[inf]*n for i in range(m)]
	T = [[inf]*n for i in range(m)]
	for i in range(m):
		C[i][i] = 0
		T[i][i] = 0
	for i in range(n):
		a,b,c,t = map(int,raw_input().split())
		C[a-1][b-1] = C[b-1][a-1] = c
		T[a-1][b-1] = T[b-1][a-1] = t
	floyd(C,m);floyd(T,m)
	for i in range(input()):
		p,q,r = map(int,raw_input().split())
		print C[p-1][q-1] if r == 0 else T[p-1][q-1]

### FIXED CODE ###

inf = 0x10101010
def solve(A,strt):
	cost = [inf]*m
	visited = [False]*m
	cost[strt] = 0
	while 1:
		min = inf
		next = -1
		visited[strt] = True
		for i in range(m):
			if visited[i]: continue
			if A[strt][i]:
				d = cost[strt] + A[strt][i]
				if d < cost[i]:
					cost[i] = d
			if min > cost[i]:
				min = cost[i]
				next = i
		strt = next
		if next == -1: break
	return cost
    
while 1:
	n,m = map(int,raw_input().split())
	if n == 0: break
	T = [[0]*m for i in range(m)]
	C = [[0]*m for i in range(m)]
	for i in range(n):
		a,b,c,t = map(int,raw_input().split())
		T[a-1][b-1] = T[b-1][a-1] = t
		C[a-1][b-1] = C[b-1][a-1] = c
	TS = [solve(T,i) for i in range(m)]
	CS = [solve(C,i) for i in range(m)]
	for i in range(input()):
		a,b,q = map(int,raw_input().split())
		if q == 0:
			print CS[a-1][b-1]
		else:
			print TS[a-1][b-1]
### BUGGY CODE ###

n = int(input())
s = {}
for i in range(n):
  p = input()
  if p in s:
    s[p] += 1
  else:
    s[p] = 1

l = [kv[0] for kv in s.items() if kv[1] == max(s.values())]

l.sort()

for i in l:
  print(i)

### FIXED CODE ###

n = int(input())
s = {}
m = 1
for i in range(n):
  p = input()
  if p in s:
    s[p] += 1
    if m < s[p]:
      m = s[p]
  else:
    s[p] = 1

l = [kv[0] for kv in s.items() if kv[1] == m]

l.sort()

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

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

if(n != 1):
    sl = []
    c = 1
    if (s[0] == "1"):
        sl.append(0)
    for i in range(n):
        if (i != 0):
            if (s[i] == s[i-1]):
                c += 1
            else:
                sl.append(c)
                c = 1
    sl.append(c)
    cl = []
    c = 0
    for i in range(n):
        st = i-k
        ed = i + k+1
        if (st < 0):
            st = 0
        if (k % 2 == 1 and i % 2 == 0 or k % 2 == 0 and i % 2 == 1):  # kが奇数の時、0の箇所（すなわちiが偶数の箇所）を中心に反転
            if (c == 0):
                cl.append(sum(sl[st: ed]))
            else:
                t = cl[c - 1]
                t += sum(sl[ed - 3: ed-1])
                if (st > 0):
                    cst = st-2
                    if (cst < 0):
                        cst = 0
                    t -= sum(sl[cst: st])
                cl.append(t)
                c += 1

    print(max(cl))
else:
    print(1)

### FIXED CODE ###

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

sl = []
c = 1
if (s[0] == "1"):
    sl.append(0)
for i in range(n):
    if (i != 0):
        if (s[i] == s[i-1]):
            c += 1
        else:
            sl.append(c)
            c = 1
sl.append(c)

ruisekiwa = [0]
sums = []
ans = 0
w = 2*k+1

if (w > len(sl)):
    print(n)
    exit()
for i in range(len(sl)):
    ruisekiwa.append(ruisekiwa[i] + sl[i])
# print(sl)
# print(ruisekiwa)
for i in range(len(sl)):
    if(k % 2 == 1 and i % 2 == 0 or k % 2 == 0 and i % 2 == 1):
        left = i-k
        if (left < 0):
            left = 0
        right = i + k+1
        if (right >= len(ruisekiwa)):
            right = len(ruisekiwa)-1
        # print(ruisekiwa[right], "-", ruisekiwa[left],
        #      "=", ruisekiwa[right]-ruisekiwa[left])
        ans = max(ans, ruisekiwa[right]-ruisekiwa[left])
print(ans)
### BUGGY CODE ###

S=str(input())
Q=int(input())

Query=[]
for i in range(Q):
    Query.append(list(input().split()))
#print(Query)

check=1
for j in range(Q):
    if len(Query[j])==1:
        check*=-1      
        #print(S)
    else:
        if Query[j][1]=='1':
            if check==1:
                S=Query[j][2]+S
            else:
                S+=Query[j][2]
            #print(S)
        else:
            if check==1:
                S+=Query[j][2]
            else:
                S=Query[j][2]+S
            #print(S)

if check==1:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

S=str(input())
Q=int(input())

Query=[]
for i in range(Q):
    Query.append(list(input().split()))

N=len(S)//2
S_left_reverse=S[:N+1][::-1]
S_right=S[N+1:]
#print(S_left_reverse,S_right)


check=1
for j in range(Q):
    if len(Query[j])==1:
        check*=-1
        #print(S_left_reverse,S_right)
    else:
        if Query[j][1]=='1':
            if check==1:
                S_left_reverse+=Query[j][2]
                #print(S_left_reverse,S_right)
            else:
                S_right+=Query[j][2]
                #print(S_left_reverse,S_right)
        else:
            if check==1:
                S_right+=Query[j][2]
                #print(S_left_reverse,S_right)
            else:
                S_left_reverse+=Query[j][2]
                #print(S_left_reverse,S_right)


ans=S_left_reverse[::-1]+S_right
if check==1:
    print(ans)
else:
    print(ans[::-1])
### BUGGY CODE ###


from scipy.misc import comb


N, M = map(int,input().split())
pairs = []
for i in range(M):
    Ai, Bi = map(int,input().split())
    pairs.append([Ai,Bi])
connections = []
ans = [int(comb(N,2,exact=True))]
for Ai, Bi in pairs[::-1]:
    # connect_flg = False
    ind = []
    for i,connection in enumerate(connections):
        if Ai in connection and Bi in connection:
            ind = [0]
            continue
        elif Ai in connection:
            connections[i].append(Bi)
            # connect_flg = True
            ind.append(i)
        elif Bi in connection:
            connections[i].append(Ai)
            # connect_flg = True
            ind.append(i)
    # ２つをつなぐものは、一つにまとめる
    if len(ind) == 2:
        connections[ind[0]].extend(connections[ind[1]])
        connections[ind[0]] = list(set(connections[ind[0]]))
        connections.remove(connections[ind[1]])            
    elif len(ind) == 0:
        connections.append([Ai,Bi])
    # 不便度の計算
    cnt = int(comb(N,2,exact=True))
    # print(connections,cnt)
    for connection in connections:
        cnt -= int(comb(len(connection),2,exact=True))
    ans.append(cnt)
for a in ans[::-1][1:]:
    print(a)

### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [-1 for i in range(n+1)]
        self.size = [1 for i in range(n+1)]
    # 検索
    def find(self, x):
        path = []
        curr = x
        # 親ノードの手前で止まる(どの根に紐づくかの情報を持ちながら)
        while self.par[curr] != -1:
            # 自分自身じゃない場合は、上にさかのぼって検索(再帰的に)
            path.append(curr)
            curr = self.par[curr]
        for p in path:
            self.par[p] = curr
        return curr

    # 結合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        self.par[y] = x
        self.size[x] += self.size[y]
        self.size[y] = 1

    # 判定
    def judge(self,x,y):
        return self.find(x) == self.find(y)

N, M = map(int,input().split())
pairs = [tuple(map(int,input().split())) for _ in range(M)]
uf = UnionFind(N)
p = N*(N-1)//2
ans = [p]
for a,b in reversed(pairs[1:]):
    if not uf.judge(a,b):
        size_a = uf.size[uf.find(a)]
        size_b = uf.size[uf.find(b)]
        uf.union(a,b)
        size_a_update = uf.size[uf.find(a)]
        p = p + size_a*(size_a-1)//2 + size_b*(size_b-1)//2 - size_a_update*(size_a_update-1)//2

    ans.append(p)
for a in reversed(ans):
    print(a)
### BUGGY CODE ###

import queue

class VInfo(object):
    def __init__(self,x,y,d,color):
        self.color=color
        self.d=d
        self.x=x
        self.y=y
    def turnColor(self):
        if self.color==".":return "#"
        else:return "."

h,w=map(int,input().split())
a=[[str(i) for i in input()] for j in range(h)]
sx,sy=0,0
gx,gy=w-1,h-1
cw=0
mapA=[]
m=100000000000000
for my in range(h):
    l=[]
    for mx in range(w):
        l.append(m)
    mapA.append(l)

q=queue.Queue()
if a[0][0]==".":q.put(VInfo(0,0,0,"."))
else:q.put(VInfo(0,0,1,"#"))
l=[]
while not q.empty():
    now=q.get()
    if now.x==gx and now.y==gy:
        if now.color=="#":l.append((mapA[gy][gx]+2)//2)
        else:l.append((mapA[gy][gx]+1)//2)

    if now.y+1<h and a[now.y+1][now.x]==now.color and mapA[now.y+1][now.x]>now.d:
            mapA[now.y+1][now.x]=now.d
            q.put(VInfo(now.x,now.y+1,now.d,now.color))
    if now.y+1<h and a[now.y+1][now.x]!=now.color and mapA[now.y+1][now.x]>now.d:
            mapA[now.y+1][now.x]=now.d
            q.put(VInfo(now.x,now.y+1,now.d+1,now.turnColor()))
    if now.x+1<w and a[now.y][now.x+1]==now.color and mapA[now.y][now.x+1]>now.d:
            mapA[now.y][now.x+1]=now.d
            q.put(VInfo(now.x+1,now.y,now.d,now.color))
    if now.x+1<w and a[now.y][now.x+1]!=now.color and mapA[now.y][now.x+1]>now.d:
            mapA[now.y][now.x+1]=now.d
            q.put(VInfo(now.x+1,now.y,now.d+1,now.turnColor()))
print(min(l))

### FIXED CODE ###

import queue

class VInfo(object):
    def __init__(self,x,y,d,color):
        self.color=color
        self.d=d
        self.x=x
        self.y=y
    def turnColor(self):
        if self.color==".":return "#"
        else:return "."

h,w=map(int,input().split())
a=[[str(i) for i in input()] for j in range(h)]
sx,sy=0,0
gx,gy=w-1,h-1
cw=0
mapA=[]
m=100000000000000
for my in range(h):
    l=[]
    for mx in range(w):
        l.append(m)
    mapA.append(l)

q=queue.Queue()
if a[0][0]==".":q.put(VInfo(0,0,0,"."))
else:q.put(VInfo(0,0,1,"#"))
l=[]
while not q.empty():
    now=q.get()
    if now.x==gx and now.y==gy:
        if now.color=="#":l.append((mapA[gy][gx]+2)//2)
        else:l.append((mapA[gy][gx]+1)//2)

    if now.y+1<h and a[now.y+1][now.x]==now.color and mapA[now.y+1][now.x]>now.d:
            mapA[now.y+1][now.x]=now.d
            q.put(VInfo(now.x,now.y+1,now.d,now.color))
    if now.y+1<h and a[now.y+1][now.x]!=now.color and mapA[now.y+1][now.x]>now.d:
            mapA[now.y+1][now.x]=now.d
            q.put(VInfo(now.x,now.y+1,now.d+1,now.turnColor()))
    if now.x+1<w and a[now.y][now.x+1]==now.color and mapA[now.y][now.x+1]>now.d:
            mapA[now.y][now.x+1]=now.d
            q.put(VInfo(now.x+1,now.y,now.d,now.color))
    if now.x+1<w and a[now.y][now.x+1]!=now.color and mapA[now.y][now.x+1]>now.d:
            mapA[now.y][now.x+1]=now.d
            q.put(VInfo(now.x+1,now.y,now.d+1,now.turnColor()))
print(min(l))
### BUGGY CODE ###

def calc(ran, count, cans, X):
  for n in ran:
    if n == 0:
      while cans[n+1] + cans[n] > X:
        cans[n] -= 1
        count += 1  
      continue
    if n + 1 == N:
      while cans[n-1] + cans[n] > X:
        cans[n] -= 1
        count += 1  
      continue
    while cans[n-1] + cans[n] > X or cans[n+1] + cans[n] > X:
      cans[n] -= 1
      count += 1
  return count, cans

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

count = 0

# odd_range = range(1, N, 2)
# even_range = range(0, N, 2)
# count, cans = calc(odd_range, count, cans, X)
# count, cans = calc(even_range, count, cans, X)

# even_count = count
# print(min(odd_count, even_count))

for i in range(0, N-1):
  while cans[i] + cans[i+1] > X:
    cans[i+1] -= 1
    count += 1
print(count)

### FIXED CODE ###

# def calc(ran, count, cans, X):
#   for n in ran:
#     if n == 0:
#       while cans[n+1] + cans[n] > X:
#         cans[n] -= 1
#         count += 1  
#       continue
#     if n + 1 == N:
#       while cans[n-1] + cans[n] > X:
#         cans[n] -= 1
#         count += 1  
#       continue
#     while cans[n-1] + cans[n] > X or cans[n+1] + cans[n] > X:
#       cans[n] -= 1
#       count += 1
#   return count, cans

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

# count = 0

# # odd_range = range(1, N, 2)
# # even_range = range(0, N, 2)
# # count, cans = calc(odd_range, count, cans, X)
# # count, cans = calc(even_range, count, cans, X)

# # even_count = count
# # print(min(odd_count, even_count))

# for i in range(0, N-1):
#   if cans[i] + cans[i+1] > X:
#     cans[i+1] -= X - cans[i]
#     count += 1
# print(count)
n, x = map(int, input().split())
l = list(map(int, input().split()))
 
y = 0
if l[0] > x:
    w = l[0] - x
    y += w
    l[0] -= w
 
for i in range(n-1):
    if l[i] + l[i+1] > x:
        z = l[i+1] + l[i] - x
        y += z
        l[i+1] -= z
 
print(y)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))

kosu = [0] * N

for i in range(N):
    kosu[i] = (A.count(i+1))

tempSum = 0
for i in range(N):
    tempSum += kosu[i] * (kosu[i] - 1) // 2

def C(N):
    if N <= 0:
        return 0
    else:
        return N*(N-1)//2


for i in range(N):
    print(tempSum - C(kosu[A[i]-1]) + C(kosu[A[i]-1] - 1))




### FIXED CODE ###

from collections import Counter
n = int(input())
A = list(map(int, input().split()))

cnt = Counter(A)

ans = 0
for v in cnt.values():
    ans += v * (v - 1) // 2

for k in A:
    # n*(n-1)//2 - (n-1)*(n-2)//2 = n - 1
    print(ans - (cnt[k] - 1))
### BUGGY CODE ###

n = int(input())
R = []
for _ in range(n):
    R.append(int(input()))

maxv = R[1] - R[0]
for i in range(1, n):
    for j in range(0, i):
        maxv = max(R[i] - R[j], maxv)
print(maxv)

### FIXED CODE ###

n = int(input())
R = []
for _ in range(n):
    R.append(int(input()))

maxv = R[1] - R[0]
minv = R[0]
for j in range(1, n):
    maxv = max(R[j] - minv, maxv)
    minv = min(R[j],minv)
print(maxv)
### BUGGY CODE ###

X = int(input())
result = []
i = X
while i >= X:
    for j in range (2, i):
        if (i % j) == 0:
            break
    else:
            result.append(i)
    i += 1
print (min(result))

### FIXED CODE ###

X = int(input())
result = []
for i in range(X,X*2):
    for j in range (2,i):
        if (i % j) == 0:
            break
    else:
            result.append(i)
            a = i
            break
print (a)
### BUGGY CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
import numpy as np
def main():
    n = int(input())
    s = np.array(list(read().rstrip()))

    r = np.sum(s == 'R')
    g = np.sum(s == 'G')
    b = np.sum(s == 'B')

    def f(s):
        ret = 0
        for i1 in range(n):
            for i2 in range(i1 + 1, n):
                i3 = i2 * 2 - i1
                if i3 <= n - 1:
                    if s[i1] != s[i2] and s[i1] != s[i3] and s[i2] != s[i3]:
                        ret += 1
        return ret
    
    res = r * g * b - f(s)
    print(res)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    s = list(input())
    sr = [0] * n
    sg = [0] * n
    sb = [0] * n
    for i1 in range(n):
        ts = s[i1]
        if ts == 'R':
            sr[i1] = 1
        elif ts == 'G':
            sg[i1] = 1
        else:
            sb[i1] = 1
    if n <= 3:
        print(0)
        exit()
    r = 0
    for ia in range(0,n-3):
        ta = s[ia]
        if ta == 'R':
            r += sum(sg[ia+1:]) * sum(sb[ia+1:])
        elif ta == 'G':
            r += sum(sr[ia+1:]) * sum(sb[ia+1:])
        else:
            r += sum(sg[ia + 1:]) * sum(sr[ia + 1:])
        for ib in range((n - ia)//2+1):
            if ia + ib * 2 < n:
                if ta != s[ia + ib] and ta != s[ia + ib + ib] and s[ia+ib]!= s[ia + ib + ib]:
                    r -= 1
    print(r)

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

n = int(input())
a = list(map(int, input().split()))
b = []
c = ''

for i in range(n):
    b.append(a[i])
    b.reverse()
for j in b:
    c += str(j) + ' '
print(c)

### FIXED CODE ###

n = int(input())
a = list(input().split())
result = list(reversed(a))[::2]

if n % 2 == 0:
    result += a[::2]
else:
    result += a[1::2]

print(*result)
### BUGGY CODE ###

N = int(input())
S = []
for _ in range(N):
    S.append(input())

S_set = set(S)
S_dict = {}
ans = []
for s in S_set:
    S_dict[s] = S.count(s)
S_dict = sorted(S_dict.items(), key=lambda x:x[1])
max = S_dict[-1][1]
while S_dict[-1][1] == max:
    ans.append(S_dict[-1][0])
    S_dict.pop(-1)
    if len(S_dict) == 0:
        break
ans.sort()

for s in ans:
    print(s)


### FIXED CODE ###

import collections

N = int(input())
S = []
for _ in range(N):
    S.append(input())

c = collections.Counter(S)
max = c.most_common()[0][1]
ans = [i[0] for i in c.items() if i[1] == max]
ans.sort()

for s in ans:
    print(s)
### BUGGY CODE ###

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

n = a[0]
k = a[1]

c = []

for i in range(k-1, n):
    p = 1
    for j in reversed(range(k)):
        p *= b[i - j]
    c.append(p)
        
for l in range(1, n - k + 1):
    if c[l] > c[l - 1]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

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

n = a[0]
k = a[1]

c = []
bfr = 0
aft = 0
for i in range(k-1, n):
    if i != k-1:
        if b[i - k] < b[i]:
            c.append("Yes")
        else:
            c.append("No")
    
            
s_n = '\n'.join(c)
print(s_n)
### BUGGY CODE ###

N, M = input().split()
pS = [input().split() for i in range(int(M))]
ans = {}
ac = 0
wa = 0
for i in pS:
    if i[0] not in ans.keys():
        ans[i[0]] = [0, 0] 
        """
        if i[1] == "AC":
            ans[i[0]][0] += 1
            ac += 1
        elif i[1] == "WA":
            ans[i[0]][1] += 1
        """
    if i[1] == "AC":
        if ans[i[0]][0] == 0:
                ans[i[0]][0] += 1
                ac += 1
                wa += ans[i[0]][1]
    elif i[1] == "WA":
        if ans[i[0]][0] == 0:
            ans[i[0]][1] += 1

"""
for i in ans.values():
    ac += i[0]
    if i[0] >= 1:
        wa += i[1]
"""
print(ac, wa)

### FIXED CODE ###

from sys import stdin
def main(pS):
    ans = {}
    ac = 0
    wa = 0
    for i in pS:
        if i[0] not in ans.keys():
            ans[i[0]] = [0, 0] 
        if i[1] == "AC":
            if ans[i[0]][0] == 0:
                    ans[i[0]][0] += 1
                    ac += 1
                    wa += ans[i[0]][1]
        elif i[1] == "WA":
            if ans[i[0]][0] == 0:
                ans[i[0]][1] += 1
    return [ac, wa]

"""
for i in ans.values():
    ac += i[0]
    if i[0] >= 1:
        wa += i[1]
"""
if __name__ == "__main__":
    N, M = input().split()
    pS = [stdin.readline().rstrip().split() for _ in range(int(M))]
    ac, wa = main(pS)
    print(ac, wa)
### BUGGY CODE ###

A,B,C,D = map(int,input().split())
#print(A,B,C,D)
adivc = A//C
if A%C != 0:
    adivc = A//C + 1
bdivc = B//C
listc=[]
for i in range(adivc,bdivc+1):
    listc.append(str(C*i))
setc = set(listc)
#print(setc)

adivd = A//D
if A%D != 0:
    adivd = A//D + 1
bdivd = B//D
listd=[]
for i in range(adivd,bdivd+1):
    listd.append(str(D*i))
setd = set(listd)
#print(setd)

setcd = setc | setd
#print(setcd)
#print(len(setcd))

print(B-A+1-len(setcd))

### FIXED CODE ###

from fractions import gcd

A,B,C,D = map(int,input().split())

adivc = A//C
if A%C != 0:
    adivc = A//C + 1
bdivc = B//C
countC = bdivc - adivc + 1

adivd = A//D
if A%D != 0:
    adivd = A//D + 1
bdivd = B//D
countD = bdivd - adivd + 1

lcm = (int)(C * D / gcd(C, D))
adivlcm = A // lcm
if A%lcm != 0:
    adivlcm = A // lcm + 1
bdivlcm = B // lcm
countlcm = bdivlcm - adivlcm + 1

print(B-A+1-(countC+countD-countlcm))
### BUGGY CODE ###


DEBUG = False
N = int(input())

# if N == 1:
#     print(1)
#     exit()

divisors = []

tmp = N
for i in range(2, N):#int(N**0.5)+1):
    while tmp % i == 0:
        tmp //= i
        divisors.append(i)
if tmp != 1:
    divisors.append(tmp)

if DEBUG:
    print(divisors)

A = 1
B = 1
while divisors:
    x = divisors.pop()
    if A > B:
        B *= x
    else:
        A *= x

if DEBUG:
    print("A: {}, B: {}".format(A, B))

print(max(len(str(A)), len(str(B))))


### FIXED CODE ###

N = int(input())

for i in range(int(N**0.5)+1, 0, -1):
    div, mod = divmod(N, i)
    if not mod:
        print(len(str(max(div, N//div))))
        exit()
### BUGGY CODE ###

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

max = max(l) * 2

ans = 0

for i in range(n):
    j = i + 1

    while(j < n and j <= i+max):

        if abs(j- i) == l[i]+l[j]:
            ans = ans + 1
            #print(abs(j-i),l[i]+l[j],i,j)
        j = j + 1
print(ans)

### FIXED CODE ###

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

a=[]
b={}
ans=0

for i in range(n):
    a.append(i+l[i])
    b[i-l[i]] = b.get(i-l[i],0) + 1

for av in a:
    ans = ans + b.get(av,0)

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

import sys
import math

dic={}

def isprime(num):
    for y in range(3, int(x**0.5)+1,2):
        if num%y==0:
            dic[num]=0
            return 0
    dic[num]=1
    return 1

for l in sys.stdin:
  n=int(l)
  count= 1 if n >= 2 else 0
  for x in range(3,n+1,2):
      count+=dic.get(x, isprime(x))
  print count

### FIXED CODE ###

import math
import sys

lst=[0 for _ in xrange(999999+1)]

def is_prime(num):
  if num%2==0:
      return 0
  for x in range(3, int(num**0.5)+1,2):
    if num % x==0:
        return 0
  return 1

lst[1]=0
lst[2]=1
for idx in range(3, len(lst)):
  lst[idx] = is_prime(idx) + lst[idx-1]

for line in sys.stdin:
  print lst[int(line)]
### BUGGY CODE ###

N,M=map(int,input().split())
dic={i+1:[] for i in range(N)}
PY=[]
len_=0
for i in range(M):
    flag=0
    p,y=map(int,input().split())
    len_=len(dic[p])
    if len_==0:
        dic[p]=[y]
    else:
        for j in range(len_):
            if dic[p][j]>y:
                dic[p].insert(j,y)
                flag=1
                break
        if flag==0:
            dic[p].append(y)
    PY.append([p,y])

p,y='',''
ans=[]
for py in PY:
    p=str(py[0])
    y=str(py[1])
    born=dic[int(p)].index(int(y))+1
    print('0'*(6-len(p))+p+'0'*(6-len(str(born)))+str(born))



### FIXED CODE ###

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

D={}
for py in PY:
    try:
        if D[py[0]]=='':
            pass
    except:
        D[py[0]]=[py[1]]
        continue
    D[py[0]].append(py[1])

for k in D.keys():
    D[k].sort()

def binary_tree(lst,key):
    left=0
    right=len(lst)-1
    while left<=right:
        mid=(left+right)//2
        if lst[mid]==key:
            return mid+1
        elif lst[mid]<key:
            left=mid+1
        else:
            right=mid-1
    return -1

for py in PY:
    l=D[py[0]]
    ans=str(py[0]).zfill(6)
    ans+=str(binary_tree(l,py[1])).zfill(6)
    print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
c = list(map(int, input().split()))
d = [(sum(range(1, c[i] + 1)) / c[i]) for i in range(a)]
e = [sum(d[i:b + i]) for i in range(a - b + 1)]
print(max(e))

### FIXED CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
c = list(map(int, input().split()))
d = [(i + 1) / 2 for i in c]
e = sum(d[:b])
f = e
for i in range(a - b):
	f -= d[i]
	f += d[i + b]
	if f > e:
		e = f
print(e)