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

n, q = map(int, input().split())
s = list(str(input()))
dp = [0] * n
for j in range(n-1):
  if s[j] == "A" and s[j+1] == "C":
      dp[j] = 0.4
      dp[j+1] = 0.6
for i in range(q):
  l, r = map(int, input().split())
  c = dp[l-1: r]
  if c[0] == 0.6:
    c[0] = 0
  if c[-1] == 0.4:
    c[-1] = 0
  print(int(sum(c)))

### FIXED CODE ###

n, q = map(int, input().split())
s = list(str(input()))
dp = [0] * n
for j in range(n-1):
  if s[j] == "A" and s[j+1] == "C":
    dp[j+1] = 1 + dp[j]
  else:
    dp[j + 1] = dp[j]
for i in range(q):
  l, r = map(int, input().split())
  print(dp[r-1] - dp[l-1])
### BUGGY CODE ###

#nord_aで使っている色の＋１
#初期入力
import sys
input = sys.stdin.readline
from collections import deque
N = int(input())
connection   ={i:set() for i in range(1,N+1)}
A            ={i:tuple() for i in range(1,N+1)}
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b) # つながりを逆向きも含めて入力
    connection[b].add(a) # 
    A[i]=a,b             #色を出力するため

#色の数(各頂点の最大値)
color_max =0
for i in connection.values():
    color_max =max(color_max, len(i) )

#各頂点に色を準備⇒辺の色決定
color_node ={i:deque() for i in range(1,N+1)} #頂点に使った色の管理,dequeで高速？
color_edge =[0]*(N-1)

for i in range(N-1):
    n_a,n_b = A[i] #i番目の辺とつながっている頂点
    if color_node[n_a] !=deque():
        color =color_node[n_a][-1] +1
    else:
        color =0
    while True:
        #color +=1
        q,color =divmod(color,color_max)
        if color not in color_node[n_a] and color not in color_node[n_b]: 
            color_edge[i] =color+1          #辺の色を出力用に決める。1～color_max
            color_node[n_a].append(color)    #前の頂点に使った色を追加
            color_node[n_b].append(color)    #先の頂点に使った色を追加
            break
        else:
            color +=1      
#出力
print(color_max)
print(*color_edge, sep="\n")

### FIXED CODE ###

"""
参考    yy4さん 2019-11-24 21:24:43
516 ms          PyPy3 (2.4.0)
"""
#def solve():
from collections import deque
import sys

input = sys.stdin.readline

n = int(input())

g = tuple(set() for _ in range(n))
for idx in range(n - 1):
    a, b = (int(x) - 1 for x in input().split())
    g[a].add((b, idx))
    g[b].add((a, idx))

q = deque()
q.append((0, -1, -1))

e = [-1] * n  # e[-1]は使わない
used = [False] * n
used[0] = True
while q:
    v, v_idx, prev_color = q.popleft()
    curr = 1 if prev_color != 1 else 2
    for u, u_idx in g[v]:
        if used[u]:
            continue
        used[u] = True
        e[u_idx] = curr
        q.append((u, u_idx, curr))
        curr += 1
        if curr == prev_color:
            curr += 1

ret = e[:-1]
#return len(set(ret)), ret

    
#l, ret = solve()
l=len(set(ret))
print(l)
print(*ret, sep='\n')
### BUGGY CODE ###

def abc158d_string_formation():
    s = input()
    q = int(input())
    flip = 0
    for _ in range(q):
        query = list(input().split())
        if query[0] == '1':
            flip = 1-flip
        elif query[1] == '1':
            if flip == 0:
                s = query[2]+s
            else:
                s = s+query[2]
        else:
            if flip == 0:
                s = s+query[2]
            else:
                s = query[2]+s
    if flip == 1:
        s = ''.join(reversed(s))
    print(s)
abc158d_string_formation()

### FIXED CODE ###

def abc158d_string_formation():
    from collections import deque
    s = deque(list(input()))
    q = int(input())
    flip = 0
    for _ in range(q):
        query = list(input().split())
        if query[0] == '1':
            flip = 1-flip
        elif query[1] == '1':
            if flip == 0:
                s.appendleft(query[2])
            else:
                s.append(query[2])
        else:
            if flip == 0:
                s.append(query[2])
            else:
                s.appendleft(query[2])
    if flip == 1:
        s = ''.join(reversed(s))
    else:
        s = ''.join(s)
    print(s)
abc158d_string_formation()
### BUGGY CODE ###

N,K = map(int, input().split())
p = list(map(int, input().split()))
temp = []
for i in range(N-K+1):
    temp.append(sum(p[i:i+K]))
iti = temp.index(max(temp))
ans = 0
for j in p[iti:iti+K]:
    ans += (j+1)/2
print(ans)

### FIXED CODE ###

N,K = map(int, input().split())
p = list(map(int, input().split()))
p = list(map(lambda x:(x+1)/2, p))
temp = []
p_sum=0
for i in range(N):
    p_sum+=p[i]
    temp.append(p_sum)
ans = []
for j in range(K,N):
    ans.append(temp[j]-temp[j-K])
if len(ans) != 0:
    print(max(ans))
else:
    print(p_sum)
### BUGGY CODE ###

A,B,Q = map(int,input().split())
INF = 10**18
s=[-INF]
t=[-INF]
for _ in range(A):
    s.append(int(input()))
for _ in range(B):
    t.append(int(input()))
# s.sort()
# t.sort()
s.append(INF)
t.append(INF)
def binSearch(value,upper,lower,array):
    ng = upper
    ok = lower
    while ng>ok+1:
        mid=(ok+ng)//2
        if(array[mid]<value):
            ok=mid
        else:
            ng=mid
    return(ok)

def solve(x):
    I = binSearch(x,A,-1,s)
    J = binSearch(x,B,-1,t)
    candidates=[]
    candidates.append(abs(x-s[I])+abs(s[I]-t[J]))
    candidates.append(abs(x-t[J])+abs(t[J]-s[I]))
    candidates.append(abs(x-s[I+1])+abs(s[I+1]-t[J]))
    candidates.append(abs(x-t[J])+abs(s[I+1]-t[J]))
    candidates.append(abs(x-s[I])+abs(s[I]-t[J+1]))
    candidates.append(abs(x-t[J+1])+abs(s[I]-t[J+1]))
    candidates.append(abs(x-s[I+1])+abs(s[I+1]-t[J+1]))
    candidates.append(abs(x-t[J+1])+abs(s[I+1]-t[J+1]))
    return(min(candidates))

for _ in range(Q):
    X = int(input())
    print(solve(X))

### FIXED CODE ###

import bisect
A,B,Q = map(int,input().split())
INF = 10**18
# s=[-INF]
# t=[-INF]
# for _ in range(A):
    # s.append(int(input()))
# for _ in range(B):
    # t.append(int(input()))
# s.sort()
# t.sort()
s = [int(input()) for _ in range(A)]
t = [int(input()) for _ in range(B)]
# s.append(INF)
# t.append(INF)

def solve(x):
    sr = bisect.bisect(s,x)
    tr = bisect.bisect(t,x)
    sRight = s[sr] if sr < A else s[sr-1]
    tRight = t[tr] if tr < B else t[tr-1]
    sLeft = s[sr-1] if sr>0 else s[sr] 
    tLeft = t[tr-1] if tr>0 else t[tr]
    # return(min(
    # print([[sr,sLeft,sRight],[tr,tLeft,tRight]])
    cand = [
        abs(x-sRight) + abs(sRight-tRight),
        abs(x-sRight) + abs(sRight-tLeft),
        abs(x-tRight) + abs(tRight-sRight),
        abs(x-tRight) + abs(tRight-sLeft),
        abs(x-sLeft) + abs(sLeft-tLeft),
        abs(x-sLeft) + abs(sLeft-tRight),
        abs(x-tLeft) + abs(tLeft-sRight),
        abs(x-tLeft) + abs(tLeft-sLeft),
    ]
    # print(cand)
    return(min(cand))
for _ in range(Q):
    print(solve(int(input())))
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))

E = []
for i in P:
    E.append((i + 1)/2)

def S(i):
    S = 0
    for j in range(i):
        S += E[j]
    return S

expects = []
for j in range(N-K+1):
    expects.append(S(j+K) - S(j))

print(max(expects))

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))

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

S = [P[0]]
for i in range(1,N):
    S.append(P[i]+S[i-1])

S.insert(0,0)

b = max([S[i]-S[i-K] for i in range(K, N+1)])

print(b)
### BUGGY CODE ###

NumString = int(input())
String = input()

total_ans = 0
for i in range(NumString):
    for j in range(i, NumString):
        for k in range(j, NumString):
            if String[i] != String[j] and String[j] != String[k] and \
                String[i] != String[k] and j - i != k - j:
                total_ans += 1

print(total_ans)

### FIXED CODE ###

NumString = int(input())
String = input()

r_string_num, g_string_num, b_string_num = 0, 0, 0
for i_string in String:
    if i_string == 'R':
        r_string_num += 1
    elif i_string == 'G':
        g_string_num += 1
    else:
        b_string_num += 1
    
total_ans = r_string_num * g_string_num * b_string_num

exclude_num = 0
for i in range(NumString-2):
    for j in range(i+1, NumString-1):
        if (2*j - i) < NumString and String[i] != String[j] and \
            String[j] != String[2*j-i] and String[i] != String[2*j-i]:
            exclude_num += 1

total_ans -= exclude_num

print(total_ans)
### BUGGY CODE ###

def abc175_c_1():
    x, k, d = map(int, input().split())

    def solve(x, k, d):
        to_l_max = x - (k * d)
        to_r_max = x + (k * d)

        if to_l_max > 0:
            return to_l_max
        if to_r_max < 0:
            return - to_r_max

        current_x = x

        for i in range(k):
            current_x = min(abs(current_x + d), abs(current_x - d))
        return current_x

    ans = solve(x, k, d)
    print(ans)

if __name__ == '__main__':
    abc175_c_1()

### FIXED CODE ###

def abc175_c_1():
    x, k, d = map(int, input().split())

    def solve(x, k, d):
        # Xを絶対値でプラスの値にし、0に近づける問題に置き換える
        x = abs(x)

        # (x // d)は0の手前まで移動するのに必要な回数。kの方が小さい場合はk回移動してしまえばよい
        if k < (x // d):
            return x - (k * d)
        # kのほうが大きい場合はそこから数回移動が必要
        else:
            # xからとりあえずx//d回は移動してOK
            current_x = x - d * (x // d)
            k = k - (x // d)

            # 結局ここが時間がかかるので終わらない。(10**15回とか探索しちゃう。)

            if (k % 2) == 0:
                # 残りの移動回数が偶数回なら移動を繰り返してその場所に戻ってくる
                return current_x
            else:
                # 奇数回の場合、偶数回移動を繰り返した後、もう一回だけ移動する。
                # return min(abs(current_x + d), abs(current_x - d))
                return abs(current_x - d)

    ans = solve(x, k, d)
    print(ans)

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

def main():
    n1 = int(input())
    if n1 > 100000:
        return 
    li1 = [int(x) for x in input().split()]
    n2 = int(input())
    if n2 > 50000:
        return 
    li2 = [int(x) for x in input().split()]
    count = 0

    for l in li2:
        if binary_search(li1, l):
            count += 1

    print(count)


def binary_search(li, x):
    if len(li) == 0:
        return False
    
    mid = len(li)//2
    
    k = li[mid]
    if k == x:
        return True
    elif k > x:
        li = li[:mid]
    else:
        li = li[mid+1:]
        
    return binary_search(li, x)

if __name__=='__main__':
    main()


### FIXED CODE ###

import array

def main():
    n1 = int(input())
    li1 = array.array('l', [int(x) for x in input().split()])
    n2 = int(input())
    li2 = array.array('l', [int(x) for x in input().split()])
    count = 0

    for l in li2:
        if binary_search(li1, l):
            count += 1

    print(count)


def binary_search(li, x):
    if len(li) == 0:
        return False
    
    mid = len(li)//2
    
    k = li[mid]
    if k == x:
        return True
    elif k > x:
        li = li[:mid]
    else:
        li = li[mid+1:]
        
    return binary_search(li, x)

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

n = int(input())
l = [i for i in range(1,n)]
print(n*(n-1)//2)

### FIXED CODE ###

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

s = input().replace("BC", "X")
indA = [i for i in range(len(s)) if s[i] == "A"]

ans = 0
for i in indA:
    while s[i] != "B" and s[i] != "C":
        ans += (s[i] == "X")
print(ans)


### FIXED CODE ###

s = input()
ans = 0
s = s.replace("BC", "D")
cnt = 0
for i in range(len(s)):
	if s[i] == "A":
		cnt += 1
	elif s[i] == "D":
		ans += cnt
	else:
		cnt = 0
print(ans)
### BUGGY CODE ###

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

Asum=0
for i in range(N):
    Asum+=A[i]*sum(A[0:i])

print(Asum%(10**9+7))

### FIXED CODE ###

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

AjtoN=sum(A)
Asum=0
for i in range(N):
    AjtoN-=A[i]
    Asum+=A[i]*AjtoN
    Asum=Asum%(10**9+7)

print(Asum)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
word = list(s)
li = [list(input().split()) for _ in range(q)]
memo = {}

def dfs(m):
    k = m
    if m in memo:
        return memo[m]
    for i in range(q):
        if word[m] == li[i][0]:
            if li[i][1] == 'R':
                m += 1
            else:
                m -= 1
        if m < 0:
            memo[k] = 'Left'
            return 'Left'
        elif m > n-1:
            memo[k] = 'Right'
            return  'Right'
    memo[k] = True
    return True

def left(a,b):
    m = int((a+b)/2)
    if a == m:
        return b
    if dfs(m) == 'Left':
        return left(m,b)
    else:
        return left(a,m)

def right(a,b):
    m = int((a+b)/2)
    if a == m:
        return a
    if dfs(m) == 'Right':
        return right(a,m)
    else:
        return right(m,b)

def main():
    if dfs(0) == 'Right':
        print(0)
    elif dfs(0) == 'Left':
        if dfs(n-1) == 'Right':
            print(right(0,n-1) - left(0,n-1) + 1)
        elif dfs(n-1) == 'Left':
            print(0)
        else:
            print(n - left(0,n-1))
    else:
        if dfs(b) == 'Right':
            print(right(0,n-1) + 1)
        elif dfs(b) == 'Left':
            print(0)
        else:
            print(n)

main()


### FIXED CODE ###

n,q = map(int,input().split())
s = input()
word = list(s)
li = [list(input().split()) for _ in range(q)]
memo = {}

def dfs(m):
    k = m
    if m in memo:
        return memo[m]
    for x in li:
        if word[m] == x[0]:
            if x[1] == 'R':
                m += 1
            else:
                m -= 1
        if m < 0:
            memo[k] = 'Left'
            return 'Left'
        elif m > n-1:
            memo[k] = 'Right'
            return  'Right'
    memo[k] = True
    return True

def left(a,b):
    m = int((a+b)/2)
    if a == m:
        return b
    elif dfs(m) == 'Left':
        return left(m,b)
    else:
        return left(a,m)

def right(a,b):
    m = int((a+b)/2)
    if a == m:
        return a
    elif dfs(m) == 'Right':
        return right(a,m)
    else:
        return right(m,b)

if dfs(0) == 'Right':
    print(0)
elif dfs(0) == 'Left':
    if dfs(n-1) == 'Right':
        print(right(0,n-1) - left(0,n-1) + 1)
    elif dfs(n-1) == 'Left':
        print(0)
    else:
        print(n - left(0,n-1))
else:
    if dfs(b) == 'Right':
        print(right(0,n-1) + 1)
    elif dfs(b) == 'Left':
        print(0)
    else:
        print(n)
### BUGGY CODE ###

N, X, Y = map(int, input().split())
count = [0] * (N-1)
for i in range(N):
    i += 1
    for j in range(N):
        j += 1
        if i < j:
            normal = j-i
            xtoy = abs(X-i) + 1 + abs(Y-j)
            ytox = abs(Y-i) + 1 + abs(X-j)
            minRoute = min([normal, xtoy, ytox])
            count[minRoute-1] += 1
for c in count:
    print(c)


### FIXED CODE ###

N, X, Y = map(int, input().split())
count = [0] * (N-1)
for i in range(N):
    i += 1
    for j in range(N-i):
        j += i + 1
        if i < j:
            normal = j-i
            xtoy = abs(X-i) + 1 + abs(Y-j)
            ytox = abs(Y-i) + 1 + abs(X-j)
            minRoute = min([normal, xtoy, ytox])
            count[minRoute-1] += 1
for c in count:
    print(c)
### BUGGY CODE ###

n,m = map(int,input().split())
arr = list(map(int,input().split()))

for i in range(m):
    arr[arr.index(max(arr))] //= 2
    
print(sum(arr))

### FIXED CODE ###

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

while m != 0 :
    arr.sort(reverse=True)
    j = arr[0] // 2
    for i in range(l):
            if arr[i] > j:
                if m != 0:
                    m -= 1
                else:
                    break
                arr[i] //= 2
            else:
                break
    if arr[0] == 0:
        break
            

print(sum(arr))
### BUGGY CODE ###

N = int(input())
def function (n):
    cnt = 0
    for x in range(1,n+1):
        for y in range(1,n+1):
            for z in range(1,n+1):
                if x**2 + y**2 +z**2 + x*y + y*z + z*x == n:
                    cnt += 1
    print(cnt)
for i in range(1,N+1):
    function(i)


### FIXED CODE ###

n = int(input())
ans = [0 for _ in range(10050)]
for i in range(1,105):
    for j in range(1,105):
        for k in range(1,105):
            v = i*i+j*j+k*k+i*j+j*k+k*i
            if v<10050:
                ans[v]+=1
for i in range(n):
    print(ans[i+1])
### BUGGY CODE ###

while 1:
  pass

### FIXED CODE ###


from collections import defaultdict

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#a,bの最小公倍数
def lcm(a, b):
    return a * b // gcd (a, b)

def main():
    data = list(input())

    if data[0] == data[1] or data[1] == data[2] or data[2] == data[3]:
        print('Bad')
    else:
        print('Good')


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

import sys
sys.setrecursionlimit(20000000)
N=int(input())

G = [[-1 for i in range(N)] for j in range(N)]
color = [0]*N

for i in range(N-1):
    e,f,g = list(map(int, input().split()))
    G[e-1][f-1]=g%2
    G[f-1][e-1]=g%2

def dfs(v,p,c):
    color[v]=c
    for i in range(N):
        if i==p:
            continue
        elif G[v][i] ==0 :
            dfs(i,v,c)
        elif G[v][i] ==1 :
            dfs(i,v,1-c)
        
dfs(0,-1,0)

for k in color:
    print(k)


### FIXED CODE ###

import sys
sys.setrecursionlimit(2000000)
input=sys.stdin.readline
import heapq

N=int(input())

G = [[] for j in range(N)]

color = [0]*N

for _ in range(N-1):
    e,f,g = list(map(int, input().split()))
    heapq.heappush(G[e-1], [f-1,g%2])
    heapq.heappush(G[f-1], [e-1,g%2])

def dfs(v,p,c):
    color[v]=c
    for k in range(len(G[v])):
        i,j = heapq.heappop(G[v])
        if i==p:
            continue
        elif j ==0 :
            dfs(i,v,c)
        elif j ==1 :
            dfs(i,v,1-c)
        
dfs(0,-1,0)

for k in color:
    print(k)
### BUGGY CODE ###

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

IN = list(list(map(int, input().split())) for _ in range(N))
sumw = 0
sumv = 0
for w, v in IN:
    sumw += w
    sumv += v

DP = dict()
DP[sumv] = sumw

def minv(i, v):
    if not DP.get(i):
        DP[i] = v
    else:
        if v < DP[i]:
            DP[i] = v

if sumw <= W:
    ans = sumv
else:
    ans = 0
    for w, v in IN:
        DPpre = DP.copy()
        for i in DPpre:
            answ = i - v
            minv(answ, DPpre[i]-w)
            if answ > ans:
                if DP[answ] <= W:
                    ans = answ
                    continue

print(ans)


### FIXED CODE ###

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

DP = [-1] * (W+1)
DP[W] = 0

def maxv(i, v):
    if i >= 0:
        if v > DP[i]:
            DP[i] = v

for w, v in (map(int, input().split()) for _ in range(N)):
    for i in range(1, W+1):
        if DP[i] >= 0:
            maxv(i-w, DP[i]+v)
            maxv(0, DP[i-w])

print(DP[0])
### BUGGY CODE ###

s = input()
print(sum(s[:i].count("B") for i in range(len(s)) if s[i]=="W"))


### FIXED CODE ###

c = b = 0
for s in input():
  c += b*(s=="W")
  b += s=="B"
print(c)
### BUGGY CODE ###

import sys
s = sys.stdin.readline().rstrip()
q = int(sys.stdin.readline().rstrip())

for _ in range(q):
    t = sys.stdin.readline().rstrip()
    if t == '1':
        s = s[::-1]
    else:
        t, f, c = t.split()
        if f == '1':
            s = c + s
        else:
            s = s + c

print(s)

### FIXED CODE ###

#TLE
from collections import deque
s = deque(input())
q = int(input())
num = 0
for _ in range(q):
    t = input()
    if t == '1':
        if num == 0:
            num = 1
        else:
            num = 0
    else:
        t, f, c = t.split()
        if num == 0:
            if f == '1':
                s.appendleft(c)
            else:
                s.append(c)
        else:
            if f == '2':
                s.appendleft(c)
            else:
                s.append(c)
s = ''.join(s)
if num == 1:
    s = s[::-1]
print(s)
### BUGGY CODE ###

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

S = list(input())
Q = int(input())

for i in range(Q):
    query = input()

    if query == '1':
        S.reverse()
    else:
        T, F, C = query.split()
        
        if F == '1':
            S.insert(0, C)
        else:
            S.append(C)

print(''.join(S))

### FIXED CODE ###

# -*- coding: utf-8 -*-
 
S = list(input())
Q = int(input())
is_forward = True
lia = []
lib = []
 
for i in range(Q):
    query = input()
 
    if query == '1':
        is_forward = not is_forward
    else:
        T, F, C = query.split()
        if is_forward:
            if F == '1':
                lia.append(C)
            else:
                lib.append(C)
        else:
            if F == '1':
                lib.append(C)
            else:
                lia.append(C)

if is_forward:
  lia.reverse()
  print(''.join(lia + S + lib))
else:
  S.reverse()
  lib.reverse()
  print(''.join(lib + S + lia))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

sets = list()
for i in range(M):
    x, y, z = list(map(int, input().split()))
    flag = True
    for s in sets:
        if x in s or y in s:
            if not flag:
                s |= _s
                s |= {x, y}
                sets.remove(_s)
                break
            s |= {x, y}
            flag = False
            _s = s
    else:
        if flag:
            sets.append({x, y})


# calc len
num = sum([len(m) - 1 for m in sets])
total = sum([len(m) for m in sets])
print((total-num) + N-total)


### FIXED CODE ###

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

N, M = list(map(int, input().split()))
node2set_id = defaultdict(int)
set_id2nodes = defaultdict(set)

# idxなどを振る
id_left = [i + 1 for i in range(M)]

for i in range(M):
    x, y, z = list(map(int, input().split()))

    # ともにIDが振られていないとき
    if node2set_id[x] + node2set_id[y] == 0:
        id = id_left.pop()
        # x,yが所属するグループIDを振る
        node2set_id[x] = id
        node2set_id[y] = id

        # グループIDに対するセットを追加
        set_id2nodes[id] |= {x, y}

    # どちらか一方にのみIDが振られているとき(片方が0になる)
    elif node2set_id[x] * node2set_id[y] == 0:
        id = node2set_id[x] + node2set_id[y]
        node2set_id[x] = id
        node2set_id[y] = id
        set_id2nodes[id] |= {x, y}

    # 両方振られているとき
    else:
        # 同じIDならそもそも考える必要がない
        if node2set_id[x] - node2set_id[y] == 0:
            continue

        # 異なるグループのときにはマージする
        id = node2set_id[x]
        prev_y = node2set_id[y]

        # yが所属するグループIDをすべてxのものに置き換える
        for y_idx in set_id2nodes[node2set_id[y]]:
            node2set_id[y_idx] = id
            set_id2nodes[id] |= {y_idx}

        del set_id2nodes[prev_y]


num = sum([len(m)-1 for m in set_id2nodes.values()])

print(N - num)
### BUGGY CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))

exv = list()

for a in p:
    exv.append((1+a)/2)

sm = list()
mx = 0
for a in range(N-K+1):
    mx = max(mx,sum(exv[a:a+K]))

print('{:.12f}'.format(mx))

### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))

from collections import deque

exv = list()

for a in p:
    exv.append((1+a)/2)

sm = 0
mx = 0

q = deque()

for a in range(N):
    sm += exv[a]
    q.appendleft(exv[a])
    if len(q) > K:
        sm -= q.pop()
    if len(q) == K:
        mx = max(mx,sm)

print('{:.12f}'.format(mx))
### BUGGY CODE ###

from collections import deque
import heapq

s = input()
s += " "

S = ""

for i in range(len(s)-1):
    if s[i] == "B" and s[i+1] == "C":
        S += "Z"

    elif i > 0 and s[i] == "C" and s[i-1] == "B":
        continue
    else:
        S += s[i]

#print (S)
la = []
ans = 0
for i in range(len(S)):

    if S[i] == "A":
        heapq.heappush(la,i)

    elif S[i] == "Z" and len(la) > 0:
        lastA = heapq.heappop(la)
        ans += i - lastA
        heapq.heappush(la,i)

    else:
        la = []

print (ans)


### FIXED CODE ###

from collections import deque
import heapq

s = input()
s += " "

S = ""

for i in range(len(s)-1):
    if s[i] == "B" and s[i+1] == "C":
        S += "Z"

    elif i > 0 and s[i] == "C" and s[i-1] == "B":
        continue
    else:
        S += s[i]

#print (S)
la = deque([])
ans = 0
for i in range(len(S)):

    if S[i] == "A":
        la.append(i)

    elif S[i] == "Z" and len(la) > 0:
        lastA = la.popleft()
        ans += i - lastA
        la.append(i)

    else:
        la = deque([])

print (ans)