Harryxun/stf_run huggingface dataset:
from math import sqrt

def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0:
        a, b = b, a%b
    return b

def divisor(a):
    lim = int(sqrt(a))
    divset = set()
    for i in range(1, lim + 1):
        if a % i == 0:
            divset |= {i, a//i}
    return divset

def is_prime(a):
    lim = int(sqrt(a))
    for i in range(2, lim + 1):
        if a % i == 0: return False
    else: return True

N = int(input())
A = [abs(int(input())) for n in range(N+1)]

gcd_of_A = A[0]
for a in A[1:]:
    gcd_of_A = gcd(gcd_of_A, a)

if gcd_of_A > 1:
    commondiv = divisor(gcd_of_A)
    while True:
        A[0] //= gcd_of_A
        newgcd = A[0]
        for a in A[1:]:
            a //= gcd_of_A
            newgcd = gcd(newgcd, a)
        if newgcd == 1: break
        else:
            newdivisor = divisor(newgcd)
            commondiv |= newdivisor
            gcd_of_A = newgcd
    
    primes = []
    for div in commondiv:
        if div > 1 and is_prime(div): primes.append(div)
    primes.sort()
    for p in primes: print(p)




### FIXED CODE ###

def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0:
        a, b = b, a%b
    return b

def divisor(a):
    i = 1
    divset = set()
    while i * i <= a:
        if a % i == 0: divset |= {i, a//i}
        i += 1
    divset.remove(1)
    return divset

def is_prime(a):
    if a <= 3: 
        prime = [False, False, True, True]
        return prime[a]
    i = 2
    while i * i <= a:
        if a % i == 0: return False
        i += 1
    else: return True

N = int(input())
A = [None] * (N+1)
for i in reversed(range(N+1)):
    A[i] = int(input())

primes_bool = [True] * (N + 1)
primes = []
for p in range(2, N+1):
    if primes_bool[p]:
        primes.append(p)
        p_mult = p * 2
        while p_mult <= N:
            primes_bool[p_mult] = False
            p_mult += p

ans = []
used = set()
gcd_of_A = abs(A[N])
for a in A[:N]:
    if a != 0: gcd_of_A = gcd(abs(a), gcd_of_A)

commondiv = divisor(gcd_of_A)
for d in commondiv:
    if d > 1 and is_prime(d): 
        ans.append(d)
        used |= {d}

for p in primes:
    if A[0] % p == 0:
        for i in range(1, p):
            coefficient = 0
            index_a = i
            while index_a <= N:
                coefficient += A[index_a]
                coefficient %= p
                index_a += p-1
            if coefficient > 0: break
        else:
            if p not in used: ans.append(p)

ans.sort()
for a in ans: print(a)
import math

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

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

print(lcm(a, b))

### FIXED CODE ###

def gcd(x, y):
    if x == 0:
        return y
    else:
        return gcd(y % x, x)

def lcm(x, y):
    return (x * y) // gcd(x, y)
a,b = map(int,input().split())

print(lcm(a,b))
a =map(int,raw_input().split())
if a[0]>a[1]:
        print "a > b"
elif a[0]<a[1]:
        print "a < b"
else:
        print "a == b"
~                       

### FIXED CODE ###

a =map(int,raw_input().split())
if a[0]>a[1]:
        print "a > b"
elif a[0]<a[1]:
        print "a < b"
else:
        print "a == b"
a, b, c = ma@(int, input().split())
if a + b + c > 21:
  print("bust")
else:
  print("win")

### FIXED CODE ###

a, b, c = map(int, input().split())
if a + b + c > 21:
  print("bust")
else:
  print("win")
import sys
sys.setrecursionlimit(10**9)

N, WW = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(N)]
W, V = zip(*l)
M = [[-1] * (WW + 1) for i in range(N + 1)]
def cal(i, w):
  if M[i][w] >= 0:
    return M[i][w]
  if i == N:
    v = 0
  elif w < W[i]:
    v = cal(i + 1, w)
  else:
    v = max(cal(i + 1, w), cal(i + 1, w - W[i]) + V[i])
  M[i][w] = v
  return v

print(cal(0, WW))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

N, WW = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(N)]
W, V = zip(*l)
M = [{} for i in range(N + 1)]
def cal(i, w):
  if w in M[i]:
    return M[i][w]
  if i == N:
    v = 0
  elif w < W[i]:
    v = cal(i + 1, w)
  else:
    v = max(cal(i + 1, w), cal(i + 1, w - W[i]) + V[i])
  M[i][w] = v
  return v

print(cal(0, WW))
A,B,C,X,Y = map(int,input().split())
min_ = min(X,Y)
max_ = max(X,Y)

res = A*X + B*Y

m = 2 * C * max(X, Y);

sum = C * 2* min_

if(C<=0.5 * A and C <= 0.5 * B):
    sum += 2*C*(max_-min_)

elif(max_==X):
    sum += (max_-min_)*A
else:
    sum += (max_-min_)*B
    
print(min(m,min(res,sum)))

### FIXED CODE ###

S = input()
S_c = S.count("o")
if(S_c==3):
    print("1000")
elif(S_c==2):
    print("900")
elif(S_c ==1):
    print("800")
else:
    print("700")
import math

def c(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = int(input())
# k,x = map(int,input().split())
s_l = []
for i in range(n):
        s_l.append(input())

for i in range(n):
        a = ''
        for x in sorted(s_l[i]):
                a += x
        s_l[i] = a

cnt = 0
# for i in range(n):
#         for j in range(1,n-i):
#                 if s_l[i] == s_l[i+j]:
#                         cnt += 1
set_s_l = set(s_l)
l = []
for val in set_s_l:
        l.append(s_l.count(val))
for i in l:
        cnt += c(i,2)
print(cnt)

### FIXED CODE ###

import math
from collections import defaultdict

n = int(input())
# k,x = map(int,input().split())
s_l = []
for i in range(n):
        s = list(input())
        s.sort()
        s_l.append(''.join(s))

# for i in range(n):
#         s_l.append(''.join(sorted(s_i_l[i])))
#         # for x in sorted(s_l[i]):
#         #         a += x
#         # s_l[i] = a
cnt = 0

d = defaultdict(lambda: 0)
for s in s_l:
        d[s] += 1

for v in d.values():
        cnt += int(v*(v-1)/2)
print(cnt)
n = input()[:-1]
while n[:len(n)//2] != [len(n)//2:]:
  n = n[:-1]
print(len(n))

### FIXED CODE ###

n = input()[:-1]
while n[:len(n)//2] != n[len(n)//2:]:
  n = n[:-1]
print(len(n))
import math
from functools import lru_cache

MOD = 1000000007


@lru_cache(None)
def fibo(x):
    if x <= 1:
        return 1
    return fibo(x - 2) + fibo(x - 1)


n, m = list(map(int, input().split(" ")))
a_list = [int(input()) for _ in range(m)]
ngs = [i in a_list for i in range(n)]
ngs.append(False)
for i in range(n):
    if ngs[i] and ngs[i + 1]:
        print(0)
        exit()
cnts = []
cnt = 0

for ng in ngs:
    if ng:
        cnts.append(cnt)
        cnt = 0
        continue
    cnt += 1
cnts.append(cnt)
ans = 1
for c in cnts:
    if c != 0:
        ans *= fibo(c - 1)
# print(ngs)
# print(cnts)
print(ans % MOD)


### FIXED CODE ###

MOD = 1000000007
N = 100001

fibo = [1, 1] + [0] * N
for i in range(2, N):
    fibo[i] = (fibo[i - 1] + fibo[i - 2]) % MOD

n, m = list(map(int, input().split(" ")))
a_list = [int(input()) for _ in range(m)]
is_ngs = [0] * (n + 2)
for a in a_list:
    is_ngs[a] = 1
for i in range(n):
    if is_ngs[i] and is_ngs[i + 1]:
        print(0)
        exit()
cnts = []
cnt = 0

for i in range(n + 1):
    if is_ngs[i]:
        cnts.append(cnt)
        cnt = 0
        continue
    cnt += 1
cnts.append(cnt)
ans = 1
for c in cnts:
    if c != 0:
        ans *= fibo[c - 1]
# print(is_ngs)
# print(cnts)
print(ans % MOD)
n,a,b=map(int, input.split())
print(max(n*a,b))

### FIXED CODE ###

n,a,b = map(int,input().split())
print(min(a * n, b))
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)

ans = []
for i in range(m+1) :
  if a[i] < sum(a) / (4 * m) :
    continue
  else :
    ans.append(a[-1])

if len(ans) == m :
  print('Yes')
else :
  print('No')

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)

ans = []
for i in range(m) :
  if a[i] < sum(a) / (4 * m) :
    continue
  else :
    ans.append(a[-1])

if len(ans) == m :
  print('Yes')
else :
  print('No')
input_nums = [int(c) for c in input().split(" ")]
x = input_nums[0]
y = input_nums[1]
ad = 0

if x = y:
  print(0)
  return

if x > y:
  ad = 2
if (x < 0 and y > 0) or (x >= 0 and y <= 0):
  ad = 1
  
x, y = abs(x), abs(y)

print(abs(x-y)+ad)



### FIXED CODE ###

input_nums = [int(c) for c in input().split(" ")]
x = input_nums[0]
y = input_nums[1]
ad = 0

if x > y:
  ad = 2
if (x < 0 and y > 0) or (x >= 0 and y <= 0):
  ad = 1
if x == y:
  ad = 0

x, y = abs(x), abs(y)

print(abs(x-y)+ad)
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


s = input()
x,y = map(int, input().split())

xs = []
ys = []
isx = True
i = 0
n = len(s)
while i<n and s[i]=="F":
    x -= 1
    i += 1

while i<n:
    c = 0
    while i<n and s[i]=="F":
        i += 1
        c += 1
    if isx and c>0:
        xs.append(c)
    elif c>0:
        ys.append(c)
    isx = not isx
    i += 1
    
def sub(l, target):
    # lの一部の符号を反転してtargetを作れるか
    val = sum(l)
    prev = [False] * (2*(val+1))
    prev[val] = True
    current = None
    for num in l:
        current = [False] * (2*(val+1))
        for i in range(2*(val+1)):
            if i-num>=0 and prev[i-num]:
                current[i] = True
            if i+num<2*val+2 and prev[i+num]:
                current[i] = True
        prev = current
    if current is None:
        current = prev
    return current[target+val]

if sub(xs, x) and sub(ys, y):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


s = input()
x,y = map(int, input().split())

xs = []
ys = []
isx = True
i = 0
n = len(s)
while i<n and s[i]=="F":
    x -= 1
    i += 1

while i<n:
    c = 0
    while i<n and s[i]=="F":
        i += 1
        c += 1
    if isx and c>0:
        xs.append(c)
    elif c>0:
        ys.append(c)
    isx = not isx
    i += 1
    
def sub(l, target):
    # lの一部の符号を反転してtargetを作れるか
    val = sum(l)
    prev = [False] * (2*(val+1))
    prev[val] = True
    current = None
    for num in l:
        current = [False] * (2*(val+1))
        for i in range(2*(val+1)):
            if i-num>=0 and prev[i-num]:
                current[i] = True
            if i+num<(2*val+2) and prev[i+num]:
                current[i] = True
        prev = current
    if current is None:
        current = prev
    return current[target+val]

if sum(abs(item) for item in xs)>=abs(x) and sum(abs(item) for item in ys)>=abs(y) and sub(xs, x) and sub(ys, y):
    print("Yes")
else:
    print("No")
n=input()
if len(set(n))=3:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

n=input()
if len(set(n))==3:
    print('Yes')
else:
    print('No')
import sys

N = int(sys.stdin.readline().strip())

i = 1
for i in range(1, N):
    sum_i = i * (i + 1) // 2
    if N <= sum_i:
        break

max_i = i
sum_i = i * (i + 1) // 2
res = sum_i - N 
# print("sum", sum_i)
# print("res", res)
# print(i)
ans = set([i for i in range(1, max_i+1)])
if res:
    ans.remove(res)

for i in ans:
    print(i)

### FIXED CODE ###

import sys

N = int(sys.stdin.readline().strip())

A = []
t = 0
i = 1
while t <= N:
    t += i
    A.append(i)
    i += 1
# print(A) 
for i in A:
    if t - N == i:
        # print("continue", i)
        continue
    else:
        print(i)
import math
while True:
    n = int(input())
    score = [ int(i) for i in input().split(" ") ] 
    average = sum(score) / n
    if n == 0:
        break
    print("{:.8f}".format(math.sqrt(sum([(x-average) ** 2]) / n ) 

### FIXED CODE ###

import math
while True:
    n = int(input())
    if n == 0:
        break
    s = [int(i) for i in input().split(" ")]
    m = sum(s) / n
    print("{:.8f}".format(math.sqrt(sum([(x-m) ** 2 for x in s]) / n)))
from sympy import prime, sieve
from collections import Counter

# p = [i for i in sieve.primerange(0,10)]
N = int(input())
cnt = 0
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
li = prime_factorize(N)
li = [str(n) for n in li]
# print(li)
counter = Counter(li)
values, counts = zip(*counter.most_common())
# print(counts)
for i in range(len(counts)):
    if 1 <= counts[i] <= 2:
        cnt += 1
    elif 3 <= counts[i] <= 5:
        cnt += 2
    elif 6 <= counts[i] <= 9:
        cnt +=3
print(cnt)

### FIXED CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
n = int(input())
l = factorization(n)
ans = 0
for c in l:
    if c[0]==1:
        break
    lim = c[1]
    num = 1
    while lim >= num:
        lim -= num
        num += 1
    ans += num-1
print(ans)
a,b,c=map(int,input().split)
print(c-a+b)


### FIXED CODE ###

a,b,c=map(int,input().split())
print(max(0,c-a+b))
n = input()
s = set()
for c in n:
  s.push(c)
if s.len() == 4:
  print("Good")
else:
  print("Bad")

### FIXED CODE ###

n = input()
for i in range(0, 3):
  if n[i] == n[i+1]:
    print("Bad")
    exit(0)
print("Good")
N = int(input())
A = list(map(int, input().split()))
M = A[0]
ans = 0
for i in range(1,N):
  if M > A[i]:
    ans += M-A[i]
  else:
    M = A[i]
print(ans)v

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
M = A[0]
ans = 0
for i in range(1,N):
  if M > A[i]:
    ans += M-A[i]
  else:
    M = A[i]
print(ans)
import sys
i=0
while True:
    x=sys.stdin.readline().strip()
    if x==0:
        break
    print("Case %d: %d"%(i+1,x))
    i+=1

### FIXED CODE ###

import sys
i=1
while True:
    x=sys.stdin.readline().strip()
    if x=="0":
        break
    print("Case %d: %s"%(i,x))
    i+=1
A, B = map(int, input().split())
S = input()

if S[A] == '-' or isdigit(S[0:A]) or isdigit(S[A+1:A+B+1]):
  print("No")
else:
  print("Yes")

### FIXED CODE ###

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

if S[A] == '-' and S[0:A].isdigit() and S[A+1:A+B+1].isdigit():
  print("Yes")
else:
  print("No")
N,Q = map(int,input().split())
ablist = [[] for _ in range(N)]
anslist = [0]*(N)

for i in range(N-1):
    a,b = map(int,input().split())
    ablist[a-1].append(b-1)
    ablist[b-1].append(a-1)

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

for q,x in pxlist:
    anslist[q-1] += x

def dfs(nownode,oya=-1):
    for nextnode in ablist[nownode]:
        if oya == nextnode:
            continue
        anslist[nextnode] += anslist[nownode]
        dfs(nextnode,nownode)
dfs(0)
print(*anslist)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 

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

T = [[]for i in range(N)]

for i in range(N-1):
    a, b = map(int, input().split())
    T[a-1].append(b-1)
    T[b-1].append(a-1)

X = [0 for i in range(N)]
for i in range(Q):
    p, x = map(int, input().split())
    X[p-1] += x

# def dfs(x, p):
#     for j in T[x]:
#         if j == p:
#             continue
#         X[j] += X[x]
#         dfs(j, x)
def dfs(nownode,oya=-1):
    for nextnode in T[nownode]:
        if oya == nextnode:
            continue
        X[nextnode] += X[nownode]
        dfs(nextnode,nownode)

dfs(0, -1)

print(*X)
S=input()
T=input()
for i in range(len(S)):
    if S[i]==T[0]:
        new_s=S[i:]+S[:i]
         if new_s==T:
             print("Yes")
             exit()

print("No")

### FIXED CODE ###

S = input()
T = input()
for i in range(len(S)):
    if S[i] == T[0]:
        new_s = S[i:] + S[:i]
        if new_s == T:
            print("Yes")
            exit()
print("No")
spots_and_people = input().split()
spot_values = input().split()

N_spot = int(spots_and_people[1])
N_people = int(spots_and_people[0])

spot_values = [ int(value) for value in spot_values ]
spot_values.sort()

line_length = [ spot_values[i+1] - spot_values[i] for i in range(N_spot-1) ]
line_length.sort()


if N_spot == N_people:
  travel = 0
  
for i in range(N_people-1):
  line_length.pop(-1)
  

travel = sum(line_length)

print(travel)

### FIXED CODE ###

spots_and_people = input().split()
spot_values = input().split()

N_spot = int(spots_and_people[1])
N_people = int(spots_and_people[0])

spot_values = [ int(value) for value in spot_values ]
spot_values.sort()

line_length = [ spot_values[i+1] - spot_values[i] for i in range(N_spot-1) ]
line_length.sort()


if N_spot <= N_people:
	travel = 0

else:
	for i in range(N_people-1):
  		line_length.pop(-1)
  

	travel = sum(line_length)

print(travel)
N, Q=map(int, input().split())
tree=[[] for _ in range(N)]
for i in range(N-1):
  a,b=map(int, input().split())
  tree[a-1].append(b-1)


add=[0]*N
for i in range(Q):
  p,x=map(int, input().split())
  add[p-1]+=x

ans=[0]*N
def dfs(start, pre, preval):
  addval=preval+add[start]
  ans[start]+=addval
  for next_node in tree[start]:
    dfs(next_node, start,addval)
dfs(0,-1,0)  
for a in ans:
  print(a, end=" ")

### FIXED CODE ###

from collections import deque 
N,Q=map(int, input().split())
G=[[] for _ in range(N)]
for i in range(N-1):
    a,b=map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
X=[0]*N
for i in range(Q):
    p,x=map(int, input().split())
    X[p-1]+=x
que=deque([(0,-1)])
#print(que)
while que:
    now, pre=que.pop()
    for nex in G[now]:
        if nex==pre:
            continue
        else:
            X[nex]+=X[now]
            que.append((nex,now))

print(" ".join(map(str, X)))
N = int(input())
S = input()
count_R = 0
count_G = 0
count_B = 0
count = 0
for i in range(N):
    if S[i] == 'R':
        count_R = count_R+1
    elif S[i] == 'G':
        count_G = count_G+1
    else:
        count_B = count_B+1
count = count_R*count_G*count_B

for i in range(N):
  for j in range(i+1,N):
    if S[i] != S[j]:
      k = 2*j-1
      if k>N:
        break
      else:
        if S[i] != S[k] and S[j] != S[k]:
          count = count-1
print(count)

### FIXED CODE ###

N = int(input())
S = input()
count_R = 0
count_G = 0
count_B = 0
count = 0
for i in range(N):
    if S[i] == 'R':
        count_R = count_R+1
    elif S[i] == 'G':
        count_G = count_G+1
    else:
        count_B = count_B+1
count = count_R*count_G*count_B

for i in range(N):
  for j in range(i+1,N):
    if S[i] != S[j]:
      k = 2*j-i
      if k>=N:
        break
      else:
        if S[i] != S[k] and S[j] != S[k]:
          count = count-1
print(count)
class UnionFind:
    """size(int)を指定
    root(x:int)->int:      根を求める
    unite(x,y:int):        要素をグループにまとめる 
    isSame(x,y:int)->bool: 要素同士が同じグループか判定する
    """
    # 分離はできない
    # 始め各要素は別々のグループ  
    def __init__(self,n):
        self.par = [-1]*n # 親の番号
        self.size = [1]*n
        for i in range(n):
            self.par[i] = i  # はじめ すべての頂点が根
    
    def root(self, x: int) -> int:
        """根を求める"""
        if self.par[x] == x: # if root
            return x
        else:
            self.par[x] = self.root(self.par[x]) # 経路圧縮
            return self.par[x]
    
    def isSame(self, x:int, y:int)->bool:
        """x と y が同じ集合に属するか否か"""
        return self.root(x)==self.root(y)
    
    def unite(self, x:int, y:int):
        """x と y の属する集合を併合"""
        x = self.root(x)
        y = self.root(y)
        if x == y: return
        self.par[x] = y
        self.size[y] += self.size[x]
        self.size[x] = 0
        
    def getsize(self, x:int):
        return self.size[self.root(x)]
        
N,M = map(int, input().split())
ab = tuple(tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M))

def comb2(n):
    if n==0: return 0
    return n*(n-1)//2

uf = UnionFind(N)
ans = []
nex = comb2(N)

for ai,bi in reversed(ab):
    ans.append(nex)
    if nex==0: continue
    sa = uf.getsize(ai)
    sb = uf.getsize(bi)
    nex = ans[-1] + comb2(sa) + comb2(sb)
    uf.unite(ai,bi)
    nex -= comb2(uf.getsize(ai))
    

for a in reversed(ans):
    print(a)

### FIXED CODE ###

#UnionFindクラス
class UnionFind:
    def __init__(self,n):
        self.par =  [i for i in range(n)]
        self.rank = [1 for _ in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # xとyの根を結合させる
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y: return
        if self.rank[x] < self.rank[y]:
            x, y = y, x
        self.rank[x] += self.rank[y]
        self.par[y] = x

    # x,yの根が同じかどうかを返す（根が同じ:True、根が異なる:False）
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    # xが含まれる木の要素数を返す
    def size(self, x):
        return self.rank[self.find(x)]
    
n,m = map(int,input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(m)]
uf = UnionFind(n)
accm = []
for ai,bi in reversed(ab):
    if uf.is_same(ai,bi):
        accm.append(0)
    else:
        accm.append(uf.size(ai)*uf.size(bi))
    uf.union(ai,bi)

accm = accm[::-1]
for i in range(1,len(accm)):
    accm[i] += accm[i-1]
for a in accm:
    print(a)
def mpow(a,b,m):
    ans=1
    while b >0 :
        if b&1:
            ans = (ans*a)%m
        a=(a*a)%m
        b=b>>1

    return ans

def calcmod(X,m,N):
    mod=0
    for i in range(N+1):
        if X&(1<<i) > 0:
            mod += mpow(2,i,m)
            mod%=m
    return mod

def popcount(m):
    return bin(m).count("1")


def findsteps(mm):
    cnt=0
    while mm !=0:
        cnt+=1
        mm=mm%popcount(mm)
    return cnt
N=int(input())
X=int(input(),2)

##we need to find X%(m-1) and X%(m+1)
m=popcount(X)
m1=m+1
m2=m-1
firstmod=calcmod(X,m1,N)
if m2 !=0:
    secondmod=calcmod(X,m2,N)
fans=[0 for i in range(N)]
k=0
for i in range(N-1,-1,-1):
    if X & (1<<i) >0:
        ##the bit was set
        ##we need to find X%(m-1) - (2^i)%(m-1)
        if m2 == 0:
            ans=0
        else:
            mm=secondmod - mpow(2,i,m2)
            if mm < 0:
                mm+=m2
            mm=mm%m2
            ans=1+findsteps(mm)
    else:
        mm = firstmod + mpow(2,i,m1)
        mm=mm%m1
        ans=1+findsteps(mm)
    fans[k] = ans
    k+=1
        ##the bit was not set
for i in fans:
    print(i)

### FIXED CODE ###

L,R,d=[int(c) for c in input().split()]
ans=0
for i in range(L,R+1):
    if i%d == 0:
        ans+=1

print(ans)
from collections import defaultdict
N, M = map(int, input().split())
E = defaultdict(list)
for i in range(M):
    x, y = map(int, input().split())
    E[x].append(y)
dp = [-1] * N
def solve(n):
    if dp[n-1] != -1:
        return dp[n-1]
    dp[n-1] = 0
    for nn in E[n]:
        dp[n-1] = max(dp[n-1], solve(nn)+1)
    return dp[n-1]
ans = 0
for i in range(N):
    ans = max(ans, solve(i+1))
print(ans)

### FIXED CODE ###

from collections import deque
from collections import defaultdict
N, M = map(int, input().split())
d = [0]*N
G = defaultdict(list)
for i in range(M):
    s, t = map(int, input().split())
    d[t-1] += 1
    G[s-1].append(t-1)
q = deque([])
for i in range(N):
    if d[i] == 0:
        q.append(i)
ans = []
while q:
    s = q.popleft()
    ans.append(s)
    for t in G[s]:
        d[t] -= 1
        if d[t] == 0:
            q.append(t)
dp = [0] * (N+1)
num = 0
for i in range(0,N):
    for n in G[ans[i]]:
        dp[n] = max(dp[n], dp[ans[i]]+1)
print(dp[ans[-1]])
#!/usr/bin/env python3
import sys


def solve(N: int, K: int, H: "List[int]"):
    if K >= N:
        return 0
    return sum(sorted(H, reverse=True)[K:])


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    H = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, K, H))

if __name__ == '__main__':
    main()


### FIXED CODE ###

from math import ceil
H, A = list(map(int, input().split()))
print(ceil(H/A))
c = input()

print('a' if c.islower() else 'A) 

### FIXED CODE ###

c = input()

print('a' if c.islower() else 'A')