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

def bitcount(N):  # 立ってるbitの数
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt

n, x = int(input()), input()

num = 0
for i, bit in enumerate(x[::-1]):
    num += int(bit) * pow(2, i)
lbit = bitcount(18)
cnt = x.count('1')

for i in range(n):
    ans = 0
    tmp = num ^ pow(2, n - (i + 1))
    ctmp = cnt - 2 * int(x[i]) + 1
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)


### FIXED CODE ###

def bitcount(N):  # 立ってるbitの数
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


n, x = int(input()), input()

num, cnt = int(x, 2), x.count('1')
lbit = bitcount(18)
for i in range(n):
    ans = 1
    if x[i] == '0':
        ctmp = cnt + 1
        tmp = num % ctmp + pow(2, n - (i + 1), ctmp)
    elif x[i] == '1':
        ctmp = cnt - 1
        if ctmp == 0:
            print(0)
            continue
        tmp = num % ctmp - pow(2, n - (i + 1), ctmp)
    tmp %= ctmp
    ctmp = lbit[tmp]
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)
### BUGGY CODE ###

from collections import defaultdict
N, M = map(int, input().split())
dic = defaultdict(list)
for i in range(N):
  A, B = map(int, input().split())
  dic[A] += [B]
key = list(dic.keys())
key.sort()
ans = 0
for i in range(1,M+1):
  m = 0
  K = 0
  for k in key:
    if k>i:
      break
    if dic[k] and m<max(dic[k]):
      m = max(dic[k])
      K = k
      #print(m,K, i, k, ans)
  if m==0:
    continue
  ans += m
  dic[K].remove(m)
print(ans)

### FIXED CODE ###

from heapq import heappop, heappush
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
X = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x: x[0])

hq = []
ans, j = 0, 0

for i in range(1, M + 1):  # M - i 日後にするバイトを考える
    while (j < N) and (X[j][0] <= i):
        heappush(hq, -X[j][1])  # 候補の追加
        j += 1
    if len(hq):
        ans += -heappop(hq)  # 候補があるとき、候補から最大値を取り出す

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

N = int(input())
ans = 0

for i in range(1,N):
    ans += i % (i+1)

print(ans)


### FIXED CODE ###

N = int(input())
N -= 1
print(N*(N+1)//2)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# !/usr/bin/env python
# vim: set fileencoding=utf-8 :

"""
#
# Author:   Noname
# URL:      https://github.com/pettan0818
# License:  MIT License
# Created:  2016-10-07
#

# Usage
#
"""
def read():
    """Read like as below.
    N A B
    t_1
    t_n
    """
    line_1 = input().split(" ")
    num_of_class = int(line_1[0])
    blocked_class = line_1[1:2]
    blocked_class = range(int(line_1[1]), int(line_1[2]))

    following_class = {int(input()) for _ in range(num_of_class)}

    return following_class, blocked_class


def check_available_class(following_class, blocked_class):
    """Check how many class you can attend.
    >>> check_available_class([4,3,6,9,1], [5,6,7,8])
    4
    >>> check_available_class([5,6,7,8,9], [4,5,6,7,8])
    1
    """
    return len(set(following_class).difference(blocked_class))


if __name__ == "__main__":
    f, b = read()
    print(check_available_class(f,b))


### FIXED CODE ###

# -*- coding: utf-8 -*-
# !/usr/bin/env python
# vim: set fileencoding=utf-8 :

"""
#
# Author:   Noname
# URL:      https://github.com/pettan0818
# License:  MIT License
# Created:  2016-10-07
#

# Usage
#
"""

def read():
    """Read like as below.
    N A B
    t_1
    t_n
    """
    line_1 = input().split(" ")
    num_of_class = int(line_1[0])
    blocked_class = line_1[1:2]
    blocked_class = range(int(line_1[1]), int(line_1[2]))

    following_class = {int(input()) for _ in range(num_of_class)}

    return following_class, blocked_class


def check_available_class(following_class, blocked_class):
    """Check how many class you can attend.
    >>> check_available_class([4,3,6,9,1], [5,6,7,8])
    4
    >>> check_available_class([5,6,7,8,9], [4,5,6,7,8])
    1
    """
    # return len(set(following_class).difference(blocked_class))
    attendable = [i for i in following_class if not i in blocked_class]
    return len(attendable)

if __name__ == "__main__":
    import doctest
    doctest.testmod()
    f, b = read()
    print(check_available_class(f,b))
### BUGGY CODE ###

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

ans = 0
for aix in range(N):
    for bix in range(aix + 1, N):
        for cix in range(bix + 1, N):
            if L[aix] < L[bix] + L[cix] and L[bix] < L[aix] + L[cix] and L[cix] < L[aix] + L[bix]:
                # print("ok:", aix,",", bix,",", cix)
                ans += 1

print(ans)


### FIXED CODE ###

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

import bisect

L.sort()
# print(L)

ans = 0
for i in range(0, N-1):
    for j in range(i+1, N-1):
        ix = bisect.bisect_left(L, L[i] + L[j])
        ans += max(0, ix - j - 1)

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

import sys
input = sys.stdin.readline
def dist(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,((x-x1)**2+(y-y1)**2)**0.5-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  from heapq import heappop,heappush
  todo=[[0,n]]
  mi=set(range(n+2))
  seen=[float('inf')]*(n+2)
  seen[n]=0
  while todo:
    _,v=heappop(todo)
    if v not in mi:continue
    mi.remove(v)
    for nv in mi:
      nd=dist(xyr,v,nv)
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
        heappush(todo,[seen[nv],nv])
  print(seen[n+1])
if __name__=='__main__':
  main()


### FIXED CODE ###

from heapq import heappop,heappush
from math import sqrt
def distf(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  inf=float('inf')
  dist=[[inf]*(n+2) for _ in range(n+2)]
  for i in range(n+2):
    dist[i][i]=0
  for i in range(n+1):
    for j in range(i+1,n+2):
      dist[i][j]=distf(xyr,i,j)
      dist[j][i]=dist[i][j]
  seen=[inf]*(n+2)
  seen[n]=0
  mi=set(range(n+2))
  while mi:
    d,v=inf,-1
    for j in mi:
      if d>seen[j]:
        d=seen[j]
        v=j
    mi.remove(v)
    for nv in mi:
      nd=dist[v][nv]
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
  print(seen[n+1])
if __name__=='__main__':
  main()
### BUGGY CODE ###

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

right=[]
left=[]
flag=0

for i in range(q):
    a = input()
    if int(a[0]) == 1:
        if flag == 0:
            flag=1
        else:
            flag=0
    else:
        if int(a[2]) == 1:
            if flag == 0:
                left.insert(0,a[4])
            else:
                right.append(a[4])
        elif int(a[2]) ==2:
            if flag ==0:
                right.append(a[4])
            else:
                left.insert(0,a[4])

right_result="".join(right)
left_result="".join(left)

if flag==0:
    print(str(left_result+s+right_result))
else:
    print(str(right_result[::-1]+s[::-1]+left_result[::-1]))

### FIXED CODE ###

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

right=[]
left=[]
flag=0

for i in range(q):
    a = input()
    if int(a[0]) == 1:
        if flag == 0:
            flag=1
        else:
            flag=0
    else:
        if int(a[2]) == 1:
            if flag == 0:
                left.append(a[4])
            else:
                right.append(a[4])
        elif int(a[2]) ==2:
            if flag ==0:
                right.append(a[4])
            else:
                left.append(a[4])

right_result="".join(right)
left_result="".join(left)

if flag==0:
    print(str(left_result[::-1]+s+right_result))
else:
    print(str(right_result[::-1]+s[::-1]+left_result))
### BUGGY CODE ###

#b
n,x =  [int(i) for i in input().split()]
a   =  [int(i) for i in input().split()]
a.extend(a)

min_cost = 10**10
for k in range(n):
    cost = x * k
    for i in range(k,k+n):
        mini = min(a[i-k:i+1])
        cost += mini
    min_cost = min(min_cost, cost)
print(min_cost)

### FIXED CODE ###

#b faster
#m_i(k) = min(m_i(k-1), a_(i-k))
# http://agc004.contest.atcoder.jp/data/agc/004/editorial.pdf
n,x =  [int(i) for i in input().split()]
a   =  [int(i) for i in input().split()]
m   =  a[::]
a.extend(a)

min_cost = sum(a)

for k in range(n):
    #cost = x * k
    for i in range(n,2*n):
        m[i-n] = min(m[i-n], a[i-k])
        #cost += mini
    min_cost = min(min_cost, x*k + sum(m))
print(min_cost)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)
def 解():
    iN,iK,iL = [int(_) for _ in input().split()]
    aD = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]
    a道 = aD[0:iK]
    a鉄道 = aD[iK:]

    d道 = {}
    d鉄道 = {}
    for i in range(1,iN+1):
        d道[i] = {i}
        d鉄道[i] ={i}

    for p,q in a道:
        d道[p].add(q)
        d道[q].add(p)
    for r,s in a鉄道:
        d鉄道[r].add(s)
        d鉄道[s].add(r)

    def fdfs(d,iS):
        dsVisited=set()
        def digRoute(iT):
            for i in d[iT] - dsVisited:
                dsVisited.add(i)
                digRoute(i)
        digRoute(iS)
        return dsVisited

    aRet = []
    for i in range(1,iN+1):
        aRet.append(str(len(fdfs(d道,i) & fdfs(d鉄道,i))))
    print( " ".join(aRet))
解()




exit()
aRet = []
for i in range(1,iN+1):
    if i in d道 and i in d鉄道 :
        aRet.append( str(len(d道[i] & d鉄道[i])))
    else:
        aRet.append( "0" )
print( " ".join(aRet))


### FIXED CODE ###

#Union-Find木の構築
import sys
def 解():
    iN,iK,iL = [int(_) for _ in input().split()]
    aD = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]

    def buildTree(a):
        aT = [0]*(iN+1)
        for p,q in a:
            rp = getRoot(aT,p)
            rq = getRoot(aT,q)
            thisRoot = max(rp,rq,q)
            aT[p] = thisRoot
            aT[q] = thisRoot
            aT[rp] = thisRoot #これで Union してるつもり
            aT[rq] = thisRoot
        return aT
    def getRoot(a,i): #find みんな小さい方に合わせるならデカい方に合わせてみよう
        if a[i] == i or a[i] == 0:
            if a[i] == 0 : a[i] = i
            return i
        elif i < a[i] :
            a[i] = getRoot(a,a[i])
            return a[i]
    #   else:
    #       print("! ",i,a[i])

    aT道 = buildTree(aD[0:iK])
    aT鉄道 = buildTree(aD[iK:])
    aRet = []
    dRet = {}
    for i in range(1,iN+1):
        # いやはやこんなもんもキーになるのか。
        Comb = (getRoot(aT道,i), getRoot(aT鉄道,i))
        aRet.append(Comb)
        if Comb in dRet:
            dRet[Comb] += 1
        else:
            dRet[Comb] = 1
    print(" ".join([str(dRet[_]) for _ in aRet]))

解()
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

A,B,C = read().decode().split()

A = list(A)
B = list(B)
C = list(C)

def can_match(x,y):
    return x == '?' or y == '?' or x == y

M = 2020

def solve(A,B,C,LA,LB,LC):
    B_from_A = [False] * (M+M+1)
    for i in range(M+M+1):
        B_from_A[i] = all(can_match(x,y) for x,y in zip(A[i:],B))
    C_from_A = [False] * (M+M+1)
    for i in range(M+M+1):
        C_from_A[i] = all(can_match(x,y) for x,y in zip(A[i:],C))
    C_from_B = [False] * (M+M+1)
    for i in range(M+M+1):
        C_from_B[i] = all(can_match(x,y) for x,y in zip(B[i:],C))
    for i in range(M):
        if not B_from_A[i]:
            continue
        for j in range(i,i+M):
            if not C_from_A[j]:
                continue
            if not C_from_B[j-i]:
                continue
            yield max(LA, LB+i, LC+j)

answer = 10 ** 9
for A,B,C in itertools.permutations([A,B,C]):
    LA = len(A)
    LB = len(B)
    LC = len(C)
    x = min(solve(A,B,C,LA,LB,LC))
    if answer > x:
        answer = x
print(answer)



### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

A,B,C = read().decode().split()

A = list(A)
B = list(B)
C = list(C)

def can_match(x,y):
    return x == '?' or y == '?' or x == y

M = 2020

def solve(A,B,C,LA,LB,LC):
    B_from_A = [True] * (M+1)
    for i in range(M+1):
        B_from_A[i] = all(can_match(x,y) for x,y in zip(A[i:],B))
    C_from_A = [True] * (M+M+1)
    for i in range(M+M+1):
        C_from_A[i] = all(can_match(x,y) for x,y in zip(A[i:],C))
    C_from_B = [True] * (M+1)
    for i in range(M+1):
        C_from_B[i] = all(can_match(x,y) for x,y in zip(B[i:],C))
    for i in range(M):
        if not B_from_A[i]:
            continue
        for j in range(M):
            if not C_from_B[j]:
                continue
            if not C_from_A[i+j]:
                continue
            yield max(LA, LB+i, LC+i+j)
            break

answer = 10 ** 9
for A,B,C in itertools.permutations([A,B,C]):
    LA = len(A)
    LB = len(B)
    LC = len(C)
    x = min(solve(A,B,C,LA,LB,LC))
    if answer > x:
        answer = x
print(answer)
### BUGGY CODE ###

import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline


# エラトステネスのふるい
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime_list = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime_list + data
        prime_list.append(p)
        data = [e for e in data if e % p != 0]


prime = get_sieve_of_eratosthenes(10 ** 5)
p = set(prime)
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    cnt = 0
    for i in prime[bisect_left(prime, l):bisect_right(prime, r)]:
        if (i + 1) // 2 in p:
            cnt += 1
    print(cnt)

### FIXED CODE ###

import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline


# エラトステネスのふるい
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime_list = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime_list + data
        prime_list.append(p)
        data = [e for e in data if e % p != 0]


prime = get_sieve_of_eratosthenes(10 ** 5)
p = set(prime)
prime = [i for i in prime if (i + 1) // 2 in p]
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(bisect_right(prime, r) - bisect_left(prime, l))
### BUGGY CODE ###

from copy import deepcopy
import sys
input=sys.stdin.readline

def f(n,W):
    wv = [list(map(int, input().split())) for _ in range(n)]
    dp = [0] + [-1] * W
    dp[0] = 0
    for w, v in wv:
        ndp = deepcopy(dp)
        for i, (dpi, dpj) in enumerate(zip(dp, dp[w:])):
            if dpi == -1: continue
            nv = dpi + v
            if nv > dpj:
                ndp[i + w] = nv
        dp = ndp
    print(max(dp))

n, W = map(int, input().split())
f(n,W)


### FIXED CODE ###

import sys
input=sys.stdin.readline

n, cap = map(int, input().split())
val =[0]*(cap+1)
def nap(n,cap):
    for _ in range(n):
        w, v = map(int, input().split())
        for wk in range(cap,w-1,-1):
            nv=val[wk-w]+v
            if val[wk]<nv:
                val[wk]=nv
    return max(val)
print(nap(n,cap))
### BUGGY CODE ###

N,Q = (int(i) for i in input().split())
S = input()
flag = False

for i in range(Q):
  x,y = (int(i)-1 for i in input().split())
  cnt = 0
  for j in S[x:y+1]:
    if j == 'A':
      flag = True
    elif j == 'C' and flag:
      cnt += 1
      flag = False
    else:
      flag = False
  print(cnt)

### FIXED CODE ###

N,Q = (int(i) for i in input().split())
S = input()
acl = [0 for i in range(N+1)]

for j in range(N):
  acl[j+1] = acl[j] +(1 if S[j:j+2] == 'AC' else 0)
      
for k in range(Q):
  x,y = (int(i)-1 for i in input().split())
  print(acl[y]-acl[x])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
n = int(input())
a = list(map(int,input().split()))
ans = 0
mod = (10**9 +7)
for j in range(61):# 2**j 桁に対して1なものの数を求める
    num_one = 0
    for i in range(len(a)):
        if a[i] & 2**j: 
            num_one += 1
    #print(j,num_one)
    ans += 2**j * (n-num_one)*(num_one) % mod
    #print(ans)
print(ans%mod)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
n = int(input())
a = list(map(int,input().split()))
ans = 0
mod = (10**9 +7)
for j in range(61):# 2**j 桁に対して1なものの数を求める
    num_one = 0
    for i in range(len(a)):
        if a[i] & 2**j: 
            num_one += 1
    #print(j,num_one)
    ans += (2**j % mod) * (n-num_one)*(num_one) % mod
    #print(ans)
print(ans%mod)
### BUGGY CODE ###

import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * 0.985 : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

import math

N = int(input())

r = 0
for u in range(1, 10):
    for l in range(1, u + 1):
        r1 = 0
        r2 = 0
        for i in range(1, N + 1):
            x = int(i / (10 ** int(math.log10(i))))
            if i % 10 == l and x == u:
                r1 += 1
            if i % 10 == u and x == l:
                r2 += 1
        r += r1 * r2
        if u != l:
            r += r1 * r2
print(r)



### FIXED CODE ###

import math
from collections import defaultdict

N = int(input())

rr = defaultdict(lambda: 0)
for i in range(1, N + 1):
    x = int(i / (10 ** int(math.log10(i))))
    y = i % 10
    rr[(x, y)] += 1

r = 0
for u in range(1, 10):
    for l in range(1, 10):
        r += rr[(u, l)] * rr[(l, u)]
print(r)
### BUGGY CODE ###

from sys import stdin

a = int(stdin.readline().rstrip())

for x in range(1,1000000001):
    if x % 2 == 0  and x % a == 0 :
        print(x)
        break;


### FIXED CODE ###

from sys import stdin

a = int(stdin.readline().rstrip())
if a % 2 == 0:
    print(a)
else:
    x = a * 2
    print(x)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
keiro = [1]
flag = True
now = 1
start = 0
loopN = 0
loop_list = []
not_loop = False
while flag:
    now = A[now - 1]
    if now in keiro:
        flag = False
        start = keiro.index(now)
        loop_list = keiro[start:]
        loopN = len(loop_list)
    else:
        keiro.append(now)
    if len(keiro) > K:
        flag = False
        not_loop = True
if not_loop:
    print(keiro[K])
elif K - start >= 0:
    print(loop_list[(K - start) % loopN])
else:
    print(keiro[K])



### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
keiro = [1]
keiro_set = {1}
flag = True
now = 1
start = 0
loopN = 0
loop_list = []
not_loop = False
for i in range(N):
    now = A[now - 1]
    if now in keiro_set:
        start = keiro.index(now)
        loop_list = keiro[start:]
        loopN = len(loop_list)
        break
    else:
        keiro.append(now)
        keiro_set.add(now)
    if i + 2 > K:
        not_loop = True
        break
if not_loop:
    print(keiro[K])
elif K - start >= 0:
    print(loop_list[(K - start) % loopN])
else:
    print(keiro[K])
### BUGGY CODE ###

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

import networkx as nx

edges = []
for _ in range(M):
    i,j=map(int, input().split())
    edges.append([i-1,j-1])
G = nx.Graph()
G.add_nodes_from(range(N))
G.add_edges_from(edges)
sg = nx.connected_components(G)
connected = sorted(sg, key=len)
print(len(connected[-1]))


### FIXED CODE ###

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

class UnionFind():
    def __init__(self, n):
        self.n = n # ノード数
        self.parents = [-1]*n # 各ノードごとのparent

    def find(self, x):
        # 自身が根であれば
        if self.parents[x]<0:
            return x
        # そうでなければ、再帰的に繰り返し、自身の根を探索
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        # それぞれの根
        x = self.find(x)
        y = self.find(y)

        # 根が同一であれば
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x,y = y,x
        self.parents[x]+=self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

uf = UnionFind(N)
for _ in range(M):
    i, j = map(int, input().split())
    i-=1
    j-=1
    uf.union(i,j)

max_size = 0
for i in range(N):
    if uf.parents[i]<0:
        size = uf.size(i)
        if max_size<size:
            max_size = size
print(max_size)
### BUGGY CODE ###

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

exp = [(1+i)/2 for i in p]

t = []
for i in range(len(p)-k+1):
    t.append(sum(p[i:i+k]))
ind = t.index(max(t))

max_pair = exp[ind:ind+k]

print(sum(max_pair))

### FIXED CODE ###

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

exp = [(1+i)/2 for i in p]

s = []
sums = 0
for i in exp:
    sums += i
    s.append(sums)

exps = [s[k-1]]
for i in range(k,len(p)):
    exps.append(s[i] - s[i-k])
print(max(exps))