Harryxun/stf_run huggingface dataset:
n, k = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * (n + 1)
for i in range(n):
    S[i+1] = S[i] + A[i]

f = lambda n: (S[n] - n) % k
C = [0] * k
ans = 0
for i in range(n):
    C[f(i)] += 1
    j = i - k + 1
    if 0 <= j:
        C[f(j)] -= 1
    ans += C[f(i+1)]
print(ans)

### FIXED CODE ###

from collections import defaultdict

n, k = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * (n + 1)
for i in range(n):
    S[i+1] = S[i] + A[i]

f = lambda n: (S[n] - n) % k
C = defaultdict(int)
ans = 0
for i in range(n):
    C[f(i)] += 1
    j = i - k + 1
    if 0 <= j:
        C[f(j)] -= 1
    ans += C[f(i+1)]
print(ans)
import math

N=int(input())

ans=999999999999
for i in range(1,math.sqrt(N)+1):
  if N % i == 0:
    ans = min(ans,i + N//i - 2)
print(ans)

### FIXED CODE ###

import math

N=int(input())

ans=999999999999
for i in range(1,int(math.sqrt(N))+1):
  if N % i == 0:
    ans = min(ans,i + N//i - 2)
print(ans)
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from collections import *
import math
from bisect import *
import functools
INF = float('inf')
mod = 10**9+7

class BIT:
    def __init__(self, N):
        self.N = N
        self.bit = [0 for _ in range(N+1)]
    def add(self, x, a):
        while x <= self.N:
            self.bit[x] += a
            x += x & -x
    def sum(self, x):
        ret = 0
        while x != 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

N, K = map(int, input().split())
A = [int(x) for x in input().split()]
bit = BIT(N+1)
cnt = 0
for a in A:
    cnt += bit.sum(N)-bit.sum(a)
    bit.add(a, 1)
X = 0
for a in A:
    X += bit.sum(a-1)
print((cnt*K+X*(K-1)*K//2)%mod)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from collections import *
import math
from bisect import *
import functools
INF = float('inf')
mod = 10**9+7

class BIT:
    def __init__(self, N):
        self.N = N
        self.bit = [0 for _ in range(N+1)]
    def add(self, x, a):
        while x <= self.N:
            self.bit[x] += a
            x += x & -x
    def sum(self, x):
        ret = 0
        while x != 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

N, K = map(int, input().split())
A = [int(x) for x in input().split()]
bit = BIT(2001)
cnt = 0
for a in A:
    cnt += bit.sum(2000)-bit.sum(a)
    bit.add(a, 1)
X = 0
for a in A:
    X += bit.sum(a-1)
print((cnt*K+X*(K-1)*K//2)%mod)
N = int(input())
a = list(map(int, input().split()))
gray = 0
brown = 0
green = 0
sky = 0
blue = 0
yellow = 0
orange = 0
red = 0
god = 0
for i in range(N):
    if a[i] < 400:
        gray = 1
    elif a[i] < 800:
        brown = 1
    elif a[i] < 1200:
        green = 1
    elif a[i] < 1600:
        sky = 1
    elif a[i] < 2000:
        blue = 1
    elif a[i] < 2400:
        yellow = 1
    elif a[i] < 2800:
        orange = 1
    elif a[i] < 3200:
        red = 1
    else:
        god+=1
zako = gray + brown + green + sky + blue + yellow + orange + red
if god > 0 and zako =0:
    color_max = god
    color_min = 1
elif god > 0 and zako != 0:
    color_max = zako + god
    color_min = zako
else:
    color_max = zako
    color_min = zako
print(color_min, color_max)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
gray = 0
brown = 0
green = 0
sky = 0
blue = 0
yellow = 0
orange = 0
red = 0
god = 0
for i in range(N):
    if a[i] < 400:
        gray = 1
    elif a[i] < 800:
        brown = 1
    elif a[i] < 1200:
        green = 1
    elif a[i] < 1600:
        sky = 1
    elif a[i] < 2000:
        blue = 1
    elif a[i] < 2400:
        yellow = 1
    elif a[i] < 2800:
        orange = 1
    elif a[i] < 3200:
        red = 1
    else:
        god+=1
zako = gray + brown + green + sky + blue + yellow + orange + red
if god > 0 and zako == 0:
    color_max = god
    color_min = 1
elif god > 0 and zako != 0:
    color_max = zako + god
    color_min = zako
else:
    color_max = zako
    color_min = zako
print(color_min, color_max)
sum = 0
while 1:
   x = raw_input()
   sum = sum + 1
   if x == "0":
      break
   print 'Case %s: %s' %(i, x)

### FIXED CODE ###

sum = 0
while 1:
   x = raw_input()
   sum = sum + 1
   if x == '0':
      break
   print 'Case %s: %s' %(sum, x)
N,M=map(int,input().split())
L=[]
S=[]
for i in range(N):
    x = input()
    l=[y for y in x]
    L.append(l)
for i in range(M):
    x = input()
    s=[y for y in x]
    S.append(s)
flag = 0
sum = 0
for i in range(N):
    for j in range(N):
        for k in range(M):
            for l in range(M):
                if i+k < N and j+l < N:
                    if L[i+k][j+l] == S[k][l]:
                        sum += 1
                        if sum == M * M:
                            flag = 1
                    else:
                        sum = 0
if flag == 0:
    print("No")
else:
    print("Yes")
remote@deb465:~/pyt

### FIXED CODE ###

table=[2,3,4,5,6,7,8,9,10,11,12,13,1]
a,b=map(int,input().split())
if a == b :
    print("Draw")
elif table.index(a) < table.index(b):
    print("Bob")
elif table.index(a) > table.index(b):
    print("Alice")
A,V = map(int,input().split())
B,W = map(int,input().split())
T = int(input())

for t in range(T):
  A += V
  B += W
  if A >= B:
    print("YES")
    exit()
  
print("NO")

### FIXED CODE ###

S = input()

print(S[:3])
import fractions
def func(x, y):
  tmp=fractions.gcd(x, y)
  return x*y//tmp

N, M=map(int, input().split())
a=list(map(int, input().split()))
b=[a[i]//2 for i in range(N)]

p=func(b[0], b[1])
for i in range(2, N):
  p=func(p, b[i])
  
if M-p<0:
  print(0)
else:
  print((M-p)//(2*p)+1)

### FIXED CODE ###

import fractions
def func(x, y):
  tmp=fractions.gcd(x, y)
  return x*y//tmp

N, M=map(int, input().split())
if N==1:
  a=int(input())
  c=a//2
  if c>M:
    print(0)
  else:
    print(int((M/c-1)/2)+1)
  exit()

a=list(map(int, input().split()))
b=[a[i]//2 for i in range(N)]

def f(x):
  out=0
  while x%2==0:
    out+=1
    x//=2
  return out

c=func(b[0], b[1])
for i in range(2, N):
  c=func(c, b[i])
  
p=[f(a[i]) for i in range(N)]
p.sort()
for i in range(N-1):
  if p[i]!=p[i+1]:
    print(0)
    exit()
    
if c>M:
  print(0)
else:
  print(int((M/c-1)/2)+1)
import sys
n = int(input())
d = list(map(int, input().split()))
m = {}
ans = 1

if d[0] != 0:
    print(0)
    sys.exit()

for i in range(n):
    num = d[i]
    if num in m:
        m[num] += 1
    else:
        m[num] = 1

#print(m)
#print(max(m))

#for i in range(1, max(m)+1):
for i in range(0, max(m)):
    if i not in m:
        print(0)
        sys.exit()
    prevCnt = m[i]
    curCnt = m[i+1]
    # prevCnt = m[i] % 998244353
    #curCnt = m[i+1] % 998244353
    # ans *= prevCnt ** curCnt
    ans *= (prevCnt ** curCnt) % 998244353

print(ans % 998244353)







### FIXED CODE ###

import sys
n = int(input())
d = list(map(int, input().split()))
m = {}
ans = 1

if d[0] != 0:
    print(0)
    sys.exit()

if d.count(0) > 1:
    print(0)
    sys.exit()

for i in range(n):
    num = d[i]
    if num in m:
        m[num] += 1
    else:
        m[num] = 1

# if len(m) < n:
#     print(0)
#     sys.exit()

#print(m)
#print(max(m))
maxV = max(m.keys())

#for i in range(1, max(m)+1):
#for i in range(0, max(m)):
for i in range(0, maxV):
    if i not in m or i + 1 not in m:
        print(0)
        sys.exit()
    prevCnt = m[i]
    curCnt = m[i+1]
    # prevCnt = m[i] % 998244353
    #curCnt = m[i+1] % 998244353
    ans *= prevCnt ** curCnt
    #ans *= (prevCnt ** curCnt) % 998244353

print(ans % 998244353)
n, k = map(int, input().split())
sushi = []
for i in range(n):
    tmp = list(map(int, input().split()))
    sushi.append(tmp)
eaten = set() # 食べた種類を記憶(集合型)
chohuku = [] # 同じ種類で二回以上食べた寿司のスコアを記録
scores = [] # Sのスコアのリスト

sushi.sort(key=lambda x:x[1])
sushi.reverse() # sushiをおいしさの降順にソート

tmp = 0 # Sのおいしさの合計を保持
for i in range(k): # sushiを美味しい順にk個食べる
    if sushi[i][0] in eaten: # 同じ種類の寿司を食べていた場合
        chohuku.append(sushi[i][1])
    else:
        eaten.add(sushi[i][0]) # 食べた寿司の種類を記憶
    tmp += sushi[i][1] # 食べた寿司のおいしさをtmpに追加
chohuku.sort()
scores.append(tmp+len(eaten)**2) # 今のSのスコアを記憶
print(chohuku)

for i in range(k,n):
    if not sushi[i][0] in eaten:
        tmp -= chohuku.pop()
        eaten.add(sushi[i][0])
        tmp += sushi[i][1]
        scores.append(tmp+len(eaten)**2)
        
print(max(scores))

### FIXED CODE ###

n, k = map(int, input().split())
sushi = []
for i in range(n):
    tmp = list(map(int, input().split()))
    sushi.append(tmp)
eaten = set() # 食べた種類を記憶(集合型)
chohuku = [] # 同じ種類で二回以上食べた寿司のスコアを記録
scores = [] # Sのスコアのリスト

sushi.sort(key=lambda x:x[1])
sushi.reverse() # sushiをおいしさの降順にソート

tmp = 0 # Sのおいしさの合計を保持
for i in range(k): # sushiを美味しい順にk個食べる
    if sushi[i][0] in eaten: # 同じ種類の寿司を食べていた場合
        chohuku.append(sushi[i][1])
    else:
        eaten.add(sushi[i][0]) # 食べた寿司の種類を記憶
    tmp += sushi[i][1] # 食べた寿司のおいしさをtmpに追加
chohuku.sort()
scores.append(tmp+len(eaten)**2) # 今のSのスコアを記憶

for i in range(k,n):
    if not sushi[i][0] in eaten and chohuku != []:
        tmp -= chohuku.pop(0)
        eaten.add(sushi[i][0])
        tmp += sushi[i][1]
        scores.append(tmp+len(eaten)**2)
        
print(max(scores))
from collections import defaultdict

n = int(input())
As  = list(map(int, input().split()))
if n == 1:
    print(0)
    exit()

Ss = sorted(As)
primes = set()
cnt = 0
d = defaultdict(int)
As = [False] * 10**6
for s in Ss:
    d[s] += 1
    if d[s] == 2:
        As[s] = True
# print(Ss)
for s in set(Ss):
    if As[s]: continue
    else:
        cnt += 1
        ind = 1
        while s * ind < 10**6:
            As[s*ind] = True
            ind += 1
print(cnt)

### FIXED CODE ###

from collections import defaultdict

n = int(input())
As  = list(map(int, input().split()))
if n == 1:
    print(1)
    exit()

Ss = sorted(As)
cnt = 0
d = defaultdict(int)
As = [False] * (10**6+10)

for s in Ss:
    d[s] += 1

for s in Ss:
    if As[s]:continue
    else:
        if d[s] == 1:
            cnt += 1
        ind = 1
        while s * ind <= 10**6:
            As[s*ind] = True
            ind += 1

print(cnt)
import numpy as np
import itertools

n = map(int, input().split())
x = [list(map(int,input().split())) for i in range(n)]

res = 0
for v in itertools.combinations(x, 2):
  a = numpy.array(v[0])
  b = numpy.array(v[1])
  res += np.linalg.norm(b-a)

print(res)

### FIXED CODE ###

import math
import itertools

n = int(input())
x = [list(map(int, input().split())) for i in range(n)]

res = 0
cnt = 0
for v in itertools.permutations(x):
  for i in range(n-1):
    res += math.sqrt((v[i+1][0] - v[i][0]) ** 2 + (v[i+1][1] - v[i][1]) ** 2)
  cnt += 1

print((res+0.0)/cnt)
#Coding:Utf-8
N=int(input())
print(f'{2/N:.10f}')


### FIXED CODE ###

#Coding:Utf-8
N=int(input())
if N%2==0:
    print('{:.10f}'.format(N/2/N))
elif N%2==1:
    print('{:.10f}'.format((int(N/2)+1)/N))
from math import sqrt
a,b,c=map(int,input().split())
k=c-a-b
if k>0 and k*k> 4*a*b:
  print("Yes")
else print("No")


### FIXED CODE ###

from math import sqrt
a,b,c=map(int,input().split())
k=c-a-b
if k>0 and k*k> 4*a*b:
  print("Yes")
else:
  print("No")
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    n+=2
    return fibonacci_sub2(n-2, 1, 0)

def fibonacci_sub2(n, fibo_minus1, fibo_minus2):
    return fibo_minus1 if n==0 else fibonacci_sub2(n-1, fibo_minus1+fibo_minus2, fibo_minus1)


N,M = map(int, input().split()) #1 2
if M != 0:
    a = [int(input()) for i in range(M)]
else:
    print(fibonacci(N-1)%1000000007)
    exit()
ans = []
nstep = range(N)
preidx = 0

for idx,i in enumerate(a):
    if i - preidx == 1 and idx != 0:
        print(0)
        exit()
    if idx == 0 and i-preidx-1 != 0:
        ans.append([idx,i-preidx-1])
    elif idx > 0:
        ans.append([idx,i-preidx-2])
    preidx = i
else:
    if preidx != N:
        ans.append([idx,N-preidx-1])

fibsum = 1
for idx,val in enumerate(ans):
    fibsum *= fibonacci(val[1])
    fibsum %= 1000000007 
print(fibsum)







### FIXED CODE ###

import sys
sys.setrecursionlimit(10000001)
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    n+=2
    return fibonacci_sub2(n-2, 1, 0)%1000000007

def fibonacci_sub2(n, fibo_minus1, fibo_minus2):
    return fibo_minus1%1000000007 if n==0 else fibonacci_sub2(n-1, (fibo_minus1+fibo_minus2)%1000000007, fibo_minus1%1000000007)%1000000007


N,M = map(int, input().split()) #1 2
if M != 0:
    a = [int(input()) for i in range(M)]
else:
    if N == 1:
        print(1)
        exit()
    else:
        print(fibonacci(N)%1000000007)
        exit()
ans = []
nstep = range(N)
preidx = 0

for idx,i in enumerate(a):
    if i - preidx == 1 and idx != 0:
        print(0)
        exit()
    if idx == 0 and i-preidx-1 != 0:
        ans.append([idx,max(0,i-preidx-1)])
    elif idx > 0:
        ans.append([idx,max(0,i-preidx-2)])
    preidx = i
else:
    if preidx != N:
        ans.append([idx,max(0,N-preidx-1)])

fibsum = 1
for idx,val in enumerate(ans):
    fibsum *= max(1,fibonacci(val[1]))
    fibsum %= 1000000007 
print(fibsum)
n, m, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A_ruiseki = []
if A[0]<=k:
    A_ruiseki.append(A[0])
    for i in range(1, n):
        if A_ruiseki[i-1]+A[i] <= k :
            A_ruiseki.append(A_ruiseki[i-1]+A[i])
        else:
            break

B_ruiseki = []
if B[0]<=k:

    B_ruiseki.append(B[0])
    for i in range(1, n):
        if B_ruiseki[i-1]+B[i] <= k :
            B_ruiseki.append(B_ruiseki[i-1]+A[i])
        else:
            break

ans = len(A_ruiseki)

for i in range(len(A_ruiseki)):
    time = A_ruiseki[i]
    expected = max(ans-i-2, 0)

    if time + B_ruiseki[expected] > k:
        continue
    if expected > 0:
        time += B_ruiseki[expected-1]
    for j in range(expected, len(B)):

        if time + B[j] > k:
            break

        time += B[j]

        ans =i+2+j

print(ans)

### FIXED CODE ###

n, m, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A_ruiseki = [0]
for i in range(n):
    if A_ruiseki[-1]+A[i] <= k :
        A_ruiseki.append(A_ruiseki[-1]+A[i])
    else:
        break

B_ruiseki = [0]
for i in range(m):
    if B_ruiseki[-1]+B[i] <= k :
        B_ruiseki.append(B_ruiseki[-1]+B[i])
    else:
        break

ans = len(A_ruiseki)-1

for i in range(len(A_ruiseki)):
    time = A_ruiseki[i]
    expected = max(ans-i, 0)

    if len(B_ruiseki) <= expected:
        continue

    if time + B_ruiseki[expected] > k:
        continue

    time += B_ruiseki[expected]

    for j in range(expected, len(B)):
        if time + B[j] > k:
            break

        time += B[j]
        ans =i+j+1

print(ans)
from collections import deque
n, m = map(int, input().split())
INF = 100000000

to = [[] for _ in range(m)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
print('Yes')
q = deque([])
dist = [INF] * n
pre = [-1] * n
dist[0] = 0
q.append(0)

while len(q) > 0:
    v = q.popleft()
    for i in to[v]:
        if dist[i] != INF:
            continue
        dist[i] = dist[v] + 1
        pre[i] = v
        q.append(i)

for i in range(n):
    ans = pre[i]
    ans += 1
    print(ans)


### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
INF = 100000000

to = [[] for _ in range(100005)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
print('Yes')
q = deque([])
dist = [INF] * n
pre = [-1] * n
dist[0] = 0
q.append(0)

while len(q) > 0:
    v = q.popleft()
    for i in to[v]:
        if dist[i] != INF:
            continue
        dist[i] = dist[v] + 1
        pre[i] = v
        q.append(i)

for i in range(1, n):
    ans = pre[i]
    ans += 1
    print(ans)
import numpy as np
n,m = map(int,input().split())
x = np.array(list(map(int, input().split())))
if n>= m:
    print(0)
    exit()
x.sort()
xd = np.diff(x)
xd2=xd.tolist()
for i in range(n-1):
    xd2.remove(max(xd2))
print(sum(xd2))


### FIXED CODE ###

import numpy as np
n,m = map(int,input().split())
x = np.array(list(map(int, input().split())))
if n>= m:
    print(0)
    exit()
x.sort()
xd = sorted(np.diff(x))
print(sum(xd[:m-n]))
import math

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

print(A * B // math.gcd(A, B))


### FIXED CODE ###

import fractions as f

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

print(A * B // f.gcd(A, B))
while 1:
	temp = input()
	if (temp==0):
		break
	N = temp
	a = []
	for i in range(N):
	    a.append(map(int, raw_input().split())+[0])
	a.append([0 for i in range(0,temp+1)])	 
	for i in range(0,temp):#????????¢??????
		for j in range(0,temp):#????????¢??????
			a[i][temp] += a[i][j]
	for k in range(0,temp+1):#????????¢??????
		for l in range(0,temp):#????????¢??????
			a[temp][k] += a[l][k]
	for m in range(temp+1):
		print " ".join(map(str,a[m]))

### FIXED CODE ###

import sys
try:
	while 1:
		temp = input()
		if (temp==0):
			break
		N = temp
		a = []
		for i in range(N):
			a.append(map(int, raw_input().split())+[0])
		a.append([0 for i in range(0,temp+1)])
		for i in range(0,temp):
			for j in range(0,temp):
				a[i][temp] += a[i][j]
		for k in range(0,temp+1):
			for l in range(0,temp):
				a[temp][k] += a[l][k]
		for m in range(0,temp+1):
			for n in range(0,temp+1):
				sys.stdout.write(str(a[m][n]).rjust(5))
			print ""
except(RuntimeError):
	pass
s = input()
l = len(s)
if s[l - 1] == "s":
	s += "es"
else:
 	l.append("s")
print(s)

### FIXED CODE ###

s = input()
if s[-1] == "s":
	s += "es"
else:
 	s += "s"
print(s)
N=input()
S=list(input())

if len(N)%2!=0:
  print('No')
else:
  if S[:N/2]==S[N/2]:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

N=int(input())
S=list(input())
 
if N%2!=0:
    print('No')
else:
    if S[:N//2]==S[N//2:]:
        print('Yes')
    else:
        print('No')
A=int(input())
B=int(input())

C=B//(A-1)
if (B-A)%(A-1)!=0:
    print(C+1)

else:
    print(C)

### FIXED CODE ###

import math
A,B=map(int, input().split())
if A<B:
  k=math.ceil((B-A)/(A-1))+1
  print(k)
elif B==1:
  print(0)
else:
  print(1)
#!/usr/bin/env python

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)
INF = float("inf")
MOD = 10**9+7

def popcount(n):
    ret = 0
    for i in range(18):
        if n>>i & 1:
            ret += 1
    return ret

def main():
    N = int(input())
    X = input().decode().rstrip()

    # X に含まれる "1" の数
    x_cnt = 0
    for i in range(N):
        if X[i]=="1":
            x_cnt += 1

    # i 桁目が 0 : x_cnt += 1
    # i 桁目が 1 : x_cnt -= 1
    # より, X mod x_cnt +1, X mod x_cnt-1 を事前計算しておく
    n_plus,n_minus = 0,0
    for i in range(N):
        if X[i]=="1":
            n_plus += 2**(N-1-i)
            n_plus %= x_cnt + 1
            n_minus += 2**(N-1-i)
            n_minus %= x_cnt - 1
    
    for i in range(N):
        ans = 1
        if X[i]=="1":
            # 1 -> 0 に変換した結果, １が全く存在しない場合
            if x_cnt == 1:
                print(0)
                continue
            a = (n_minus - pow(2,(N-1-i), x_cnt-1)) % (x_cnt-1)
        else:
            a = (n_plus + pow(2,(N-1-i), x_cnt+1)) % (x_cnt+1)
        while a > 0:
            pop_cnt = popcount(a)
            a %= pop_cnt
            ans += 1
        print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

#!/usr/bin/env python

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)
INF = float("inf")

def popcount(n):
    ret = 0
    for i in range(18):
        if n>>i & 1:
            ret += 1
    return ret

def main():
    N = int(input())
    X = input().decode().rstrip()

    # X に含まれる "1" の数
    x_cnt = X.count("1")

    # i 桁目が 0 : x_cnt += 1
    # i 桁目が 1 : x_cnt -= 1
    # より, X mod x_cnt +1, X mod x_cnt-1 を事前計算しておく
    x_mod_pl,x_mod_mi = 0,0
    d_pl,d_mi = 1,1
    mod_pl,mod_mi = x_cnt+1,max(1,x_cnt-1)
    for i in range(N-1,-1,-1):
        if X[i]=="1":
            x_mod_pl = (x_mod_pl + d_pl) % mod_pl
            x_mod_mi = (x_mod_mi + d_mi) % mod_mi
        d_pl = (d_pl*2) % mod_pl
        d_mi = (d_mi*2) % mod_mi
    
    for i in range(N):
        ans = 1
        if X[i] == "1":
            # 1 -> 0 に変換した結果, １が全く存在しない場合
            if x_cnt == 1:
                print(0)
                continue
            a = (x_mod_mi - pow(2,(N-1-i), mod_mi)) % mod_mi
        else:
            a = (x_mod_pl + pow(2,(N-1-i), mod_pl)) % mod_pl

        while a > 0:
            pop_cnt = popcount(a)
            a %= pop_cnt
            ans += 1

        print(ans)

if __name__ == "__main__":
    main()
N = int(input())
A = map(int, input().split())

pairs = []

for i in range(len(A)):
    if A[A[i] - 1] == i + 1:
        pairs.append(1)

print(len(pairs) // 2)

### FIXED CODE ###

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

pairs = []

for i in range(len(A)):
    if A[A[i] - 1] == i + 1:
        pairs.append(1)

print(len(pairs) // 2)
def INT(): x = int(input()) return x
def LIST(): x = list(map(int, input().split())) return x

S = input()
if S[2]==S[3] and S[4] == S[5]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###



S = str(input())
if S[2] == S[3] and S[4] == S[5]:
    print("Yes")
else:
    print("No")
n, k = map(int, input().split())
if n >= k:
  print(n%k)
 
else:
  print(min(n, abs(k-n)))

### FIXED CODE ###

a, b, c = map(int, input().split())
print(c, a, b)
S = list(input())
result = []
if len(set(S))==2:
  for s in S:
    result.append(S.count(s))
    if (result[0]==result[1]) == 2:
      print("Yes")
  

### FIXED CODE ###

S = list(input())
result = []
if len(set(S))==2:
  for s in list(set(S)):
    result.append(S.count(s))
  if result[0]==result[1]:
    print("Yes")
  else:
    print("No")
else:
  print("No")
import math

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

br = [list(map(int, input().split())) for _ in range(m)]

ans = []

def ncr(n, r):
    if n<r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

subg = {i+1:i+1 for i in range(n)}

nodes = {i+1:1 for i in range(n)}

res = []
r = ncr(n, 2)

def fetch(i):
    if i == subg[i]:
        return i
    j = fetch(subg[i])
    subg[i] = j
    return j

for a, b in reversed(br):
    # print(subg, nodes)

    if len(nodes.keys()) == 1:
        res.append(0)
        continue
    else:
        res.append(r)

    mi, ma = min(a,b), max(a,b)
    v, w = max(fetch(mi), fetch(ma)), min(fetch(mi), fetch(ma))
    
    x = nodes[v] 
    y = nodes[w]

    r += ncr(x, 2) + ncr(y, 2)
    r -= ncr(x+y, 2)

    nodes[w] += nodes[v]
    del nodes[v]
    subg[mi] = w
    subg[ma] = w

for i in reversed(res):
    print(i)



### FIXED CODE ###


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

br = [list(map(int, input().split())) for _ in range(m)]

ans = []

def nc2(n):
    if n<2:
        return 0
    return n * (n-1) // 2


class UnionFind:

    def __init__(self, size):
        self.table = [-1 for _ in range(size+1)]
        self.size = [1 for _ in range(size+1)]

    def find(self, x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] != self.table[s2]:
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                    self.size[s1] += self.size[s2]
                    self.size[s2] = 0
                else:
                    self.table[s1] = s2
                    self.size[s2] += self.size[s1]
                    self.size[s1] = 0
            else:
                self.table[s1] += -1
                self.table[s2] = s1
                self.size[s1] += self.size[s2]
                self.size[s2] = 0

    def get_size(self, x):
        s1 = self.find(x)
        return self.size[s1]

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

res = []
r = nc2(n)

uf = UnionFind(n)

for a, b in reversed(br):

    res.append(r)

    if not uf.check_same(a,b):
        r -= uf.get_size(a)*uf.get_size(b)

    uf.union(a,b)

for i in reversed(res):
    print(i)