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

import math
import sys
from collections import defaultdict

N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7

def factorization(n):


    """ n の素因数分解 / 基数と指数で取り出す

    """

    arr = defaultdict(int)
    tmp = n
    for i in range(2, int(-(-n**0.5 // 1)) + 1):  # sqrt(n) まで

        # i で割れるだけ割る、を繰り返す
        if tmp % i == 0:
            cnt = 0

            while tmp % i == 0:
                cnt += 1
                tmp //= i

            arr[i] = cnt  # 結果を追加

    if tmp != 1:
        arr[tmp] = 1  # まだ余っていれば追加しておく

    if arr == []:
        arr[n] = 1  # このブロック、必要か？

    return arr


N = int(sys.stdin.readline().rstrip())
A = [int(x) for x in sys.stdin.readline().rstrip().split()]

maxlist = defaultdict(int)
minlist = factorization(A[0])

pc = True
sp = True

S = set()

for a in A:
    d = factorization(a)
    # print(a, d)
    for p in d.keys():
        S.add(p)

        if min(maxlist[p], d[p]) != 0:
            pc = False
        maxlist[p] = max(maxlist[p], d[p])
    
    for p in S:
        minlist[p] = min(minlist[p], d[p])

for p in S:
    if minlist[p] != 0:
        sp = False

# print(maxlist)
# print(minlist)

if pc:
    print("pairwise coprime")
elif sp:
    print("setwise coprime")
else:
    print("not coprime")

### FIXED CODE ###

import sys
import math


N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7


def main():
    N = int(sys.stdin.readline().rstrip())
    A = [int(x) for x in sys.stdin.readline().rstrip().split()]

    maxA = max(A)

    # 1 <= a <= maxA までの、要素の登場回数
    C = [0] * (maxA + 1)
    for a in A:
        C[a] += 1

    pc = True

    # p の倍数である個数をカウントする
    for p in range(2, maxA + 1):
        cnt = 0
        for k in range(maxA // p + 1):
            cnt += C[k * p]

        # k*p となるような要素が2個以上あったら、pairwise coprime ではない
        if cnt > 1:
            pc = False

    if pc:
        print("pairwise coprime")
        return

    GCD = A[0]
    for i in range(1, N):
        GCD = math.gcd(GCD, A[i])

    if GCD == 1:
        print("setwise coprime")
        return

    print("not coprime")


main()
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
B=[list(map(int,input().split())) for i in range(Q)]
from bisect import bisect_left
# def 二分探索(リスト, 要素)
def index(lst, e):
    # Step 1. bisect_left して
    i = bisect_left(lst, e)
    
    # Step 2. 変な値を ValueError で弾いて
    if i == len(lst):
        return -1
    if lst[i] != e:
        return -1
    # Step 3. 値を返す。
    return i
def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    # ここで分割を行う
    left = arr[:mid]
    right = arr[mid:]

    # 再帰的に分割を行う
    left = merge_sort(left)
    right = merge_sort(right)

    # returnが返ってきたら、結合を行い、結合したものを次に渡す
    return merge(left, right)

def merge(left, right):
    merged = []
    l_i, r_i = 0, 0

    # ソート済み配列をマージするため、それぞれ左から見ていくだけで良い
    while l_i < len(left) and r_i < len(right):
        # ここで=をつけることで安定性を保っている
        if left[l_i] <= right[r_i]:
            merged.append(left[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            r_i += 1

    # 上のwhile文のどちらかがFalseになった場合終了するため、あまりをextendする
    if l_i < len(left):
        merged.extend(left[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
    return merged

A=merge_sort(A)
for i in B:
    j=1
    while j!=-1:
        j=index(A,i[0])
        if not j==-1:
            A[j]=i[1]
        A=merge_sort(A)
    print(sum(A))


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
B=[list(map(int,input().split())) for i in range(Q)]

dp=[0 for i in range(1,10**6)]
for i in A:
    dp[i]+=1
S=sum(A)
for i in B:
    S+=(i[1]-i[0])*dp[i[0]]
    print(S)
    dp[i[1]]+=dp[i[0]]
    dp[i[0]]=0
### BUGGY CODE ###

import collections
h,w = map(int, input().split())
s=[input()for _ in range(h)]
r=[[1,0],[-1,0],[0,1],[0,-1]]
def bfs(i,j):
    global h,w,r
    f=[-1 for _ in range(h*w)]
    que = collections.deque([[i,j,0]])
    while que:
        i,j,k = que.popleft()
        f[i*w+j] =k
        for sr in r:
            ti = i + sr[0]
            tj = j + sr[1]
            if ti>=0 and tj>=0 and ti<h and tj<w:
                if s[ti][tj] == ".":
                    if f[ti*w+tj] == -1:
                        que.append([ti,tj,k+1])
    return max(f)

def main():
    res = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] ==".":
                tres = bfs(i,j)
                res = max(res,tres)
    print(res)

main()

### FIXED CODE ###

import collections

h, w = map(int, input().split())
s = [input() for _ in range(h)]
r = [[1, 0], [-1, 0], [0, 1], [0, -1]]


def bfs(i, j):
    global h, w, r
    f = [-1 for _ in range(h * w)]
    que = [[] for _ in range(h * w)]
    que[0].append([i, j])
    for k in range(h * w):
        if que[k]:
            res = k
            for i, j in que[k]:
                f[i * w + j] = k
                for sr in r:
                    ti = i + sr[0]
                    tj = j + sr[1]
                    if ti >= 0 and tj >= 0 and ti < h and tj < w:
                        if s[ti][tj] == ".":
                            if f[ti * w + tj] == -1:
                                que[k + 1].append([ti, tj])
    return res


fl = 0
for i in range(h):
    if "#" in s[i]:
        fl = 1
        break
if fl == 0:
    print(h + w - 2)
else:
    res = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == ".":
                res = max(res, bfs(i, j))
    print(res)
### BUGGY CODE ###

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

S = input()
N = len(S)

counter = 0
surplus = [0]*2019
surplus[0] += 1

for i in range(N):
    surplus[int(S[i:]) % 2019] += 1
#print(surplus)
for x in surplus:
    if x >= 2:
        counter += int(x*(x-1)/2)

print(counter)


### FIXED CODE ###

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

surplus = [0]*2019
surplus[0] += 1

d = 1
n = 0
for i in reversed(input()):
    n = (n + int(i)*d) %2019
    d = d*10 % 2019
    surplus[n] += 1

print(sum([i*(i-1)//2 for i in surplus]))
### BUGGY CODE ###


def main():
    s = input().strip()
    k = int(input().strip())

    ss = []
    for i in range(0, len(s)):
        for j in range(i, len(s)+1):
            if i == j:
                continue
            if len(ss) == 8:
                if ss[-1] > s[i:j]:
                    ss[-1] = s[i:j]
                    ss = list(set(ss))
                    ss.sort()
            else:
                ss.append(s[i:j])
                ss = list(set(ss))
                ss.sort()

    print(ss[k-1])

if __name__ == '__main__':
    main()


### FIXED CODE ###


def main():
    s = input().strip()
    k = int(input().strip())

    ss = []
    for i in range(0, len(s)):
        for j in range(i, i + k + 1):
            if i == j:
                continue
            if len(ss) == 6:
                if ss[-1] > s[i:j]:
                    ss[-1] = s[i:j]
                    ss = list(set(ss))
                    ss.sort()
            else:
                ss.append(s[i:j])
                ss = list(set(ss))
                ss.sort()

    print(ss[k-1])

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

def main():
    n = int(input())
    s = [""] * n
    ans = 0
    for i in range(n):
        s[i] = SortString(input())
    s.sort()
    for i in range(n - 1):
        for j in range(i + 1, n):
            if s[i] == s[j]:
                ans += 1
            else:
                break
    print(ans)


def SortString(text):
    n = len(text)
    textList = [""] * n
    for i in range(len(text)):
        textList[i] = text[i]
    return "".join(sorted(textList))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    s = [""] * n
    ans = 0
    for i in range(n):
        s[i] = SortString(input())
    sDictionary = {}
    for i in range(n):
        if sDictionary.get(s[i]):
            ans += sDictionary.get(s[i])
            sDictionary[s[i]] += 1
        else:
            sDictionary[s[i]] = 1
    print(ans)


def SortString(text):
    return "".join(sorted(list(text)))


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

n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353

dp=[[0]*s for _ in range(n)]    
tmp=1
for i in range(n):
    if a[i]<=s:
        dp[i][a[i]-1]=tmp%mod
    for j in range(s):
        if i>0:
            dp[i][j]+=dp[i-1][j]*2
            dp[i][j]%=mod
            if j+a[i]<s:
                dp[i][j+a[i]]+=dp[i-1][j]
                dp[i][j+a[i]]%=mod
    tmp*=2
            
print(dp[n-1][s-1])

### FIXED CODE ###

n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353

dp=[[0]*s for _ in range(n)]    
tmp=1
for i in range(n):
    if a[i]<=s:
        dp[i][a[i]-1]=tmp
    for j in range(s):
        if i>0:
            dp[i][j]+=dp[i-1][j]*2
            dp[i][j]%=mod
            if j+a[i]<s:
                dp[i][j+a[i]]+=dp[i-1][j]
                dp[i][j+a[i]]%=mod
    tmp*=2
    tmp%=mod
            
print(dp[n-1][s-1])
### BUGGY CODE ###

import itertools

N,K=list(map(int,raw_input().split()))
x=[]
y=[]
for i in range(N):
	a1,a2=map(int,raw_input().split())
	x.append(a1)
	y.append(a2)
#print x
#print y


ans=100000000000000000000
for i in range(N):
	for j in range(i,N):
		for k in range(N):
			for l in range(k,N):
				cnt=0
				for m in range(N):
					x_t=x[m]
					y_t=y[m]
					if (x_t>=x[i] and x_t<=x[j]) or (x_t>=x[j] and x_t<=x[i]):
						if (y_t>=y[k] and y_t<=y[l]) or (y_t>=y[l] and y_t<=y[k]):
							cnt+=1
				#print x[i],y[k],x[j],y[l],cnt,abs(x[i]-x[j])*abs(y[k]-y[l])
				#print cnt
				if cnt>=K:
					#print x[i],y[k],x[j],y[l],cnt,abs(x[i]-x[j])*abs(y[k]-y[l])
					ans=min(ans,abs(x[i]-x[j])*abs(y[k]-y[l]))


print ans

### FIXED CODE ###

import itertools

N,K=list(map(int,raw_input().split()))
x=[]
y=[]
pts=[]
for i in range(N):
	a1,a2=map(int,raw_input().split())
	x.append(a1)
	y.append(a2)
	pts.append([a1,a2])

#print "# x,y"
x.sort()
y.sort()
#print x
#print y

#print "# pts"
#print pts
pts.sort(key=lambda x:x[0])
#print pts

ans=10**20


for y1 in y:
	for y2 in y:
		if y1>=y2:
			continue
		for x1 in x:
			cnt=0
			for p in pts:
				if p[0]>=x1 and p[1]>=y1 and p[1]<=y2:
					#print p[0],p[1],x1,y1,y2
					cnt+=1
					if cnt==K:
						x2=p[0]
						#print x1,y1,x2,y2,cnt,abs(x2-x1)*abs(y2-y1)
						ans=min(ans,abs(x2-x1)*abs(y2-y1))
						break

print ans
### BUGGY CODE ###

s = input()
num = int(input())
change_flag = 1
for i in range(num):
    a = input().split(" ")
    if(a[0] == "1"):
        change_flag *= -1
    else:
        if((a[1] == "1" and change_flag == 1) or (a[1] == "2" and change_flag == -1)):
            s = a[2] + s
        else:
            s = s + a[2]

if(change_flag == -1):
    s = s[::-1]
print(s)



### FIXED CODE ###

s = input()
b = ""
f = ""
change_flag = 1
for i in range(int(input())):
    a = input().split(" ")
    if(a[0] == "1"):
        change_flag *= -1
    else:
        if((a[1] == "1" and change_flag == 1) or (a[1] == "2" and change_flag == -1)):
            b = a[2] + b
        else:
            f = f + a[2]

if(change_flag == -1):
    print(f[::-1]+s[::-1]+b[::-1])
else:
    print(b+s+f)
### BUGGY CODE ###

N,K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
before = 1
for i in A[:K]:
    before *= i

for i in range(K,len(A)):
    val = before
    val /= A[i-K]
    val *= A[i]

    if(val > before):
        print("Yes")
    else:
        print("No")
    before = val

### FIXED CODE ###

N,K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

for i in range(K,N):
    if(A[i-K] < A[i]):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from collections import Counter

N, K = map(int, input().split())
cnt = Counter(list(map(int, input().split())))
res = 0
l = len(cnt)
for i in range(l, K, -1):
    res += cnt.most_common(i)[-1][1]
print(res)

### FIXED CODE ###

from collections import Counter

N, K = map(int, input().split())
cnt = Counter(list(map(int, input().split())))
res = 0
l = len(cnt)
mc = cnt.most_common()
for i in range(l - 1, K - 1, -1):
    res += mc[i][1]
print(res)
### BUGGY CODE ###

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

rev = 0
for _ in range(q):
    que = input()
    if que[0] == "1":
        rev ^= 1

    else:
        t, f, c = que.split()
        if rev:
            if f == "1":
                s = s + c
            else:
                s = c + s

        else:
            if f == "1":
                s = c + s
            else:
                s = s + c

if rev:
    print(s[::-1])
else:
    print(s)


### FIXED CODE ###

from collections import deque

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

s = deque(s)

rev = 0
for _ in range(q):
    que = input()
    if que[0] == "1":
        rev ^= 1

    else:
        t, f, c = que.split()
        if rev:
            if f == "1":
                s.append(c)
            else:
                s.appendleft(c)

        else:
            if f == "1":
                s.appendleft(c)
            else:
                s.append(c)

s = list(s)
if rev:
    print(*s[::-1], sep="")
else:
    print(*s, sep="")
### BUGGY CODE ###

import math
Q = int(input())
lr = [list(map(int, input().split())) for i in range(Q)]

max_l = max(lr, key=lambda x:x[1])[1]

a = list(range(2,int(math.ceil(max_l**0.5)+1)))
prime = list(range(2,max_l+1))
i = 1
while True:
    b = filter(lambda x: x%a[i-1] != 0,a[i:])
    a = a[:i]
    a.extend(b)
    i += 1
    if i > len(a):
        break

for i in range(len(a)):
    prime = list(filter(lambda x: x%a[i] != 0 or x == a[i],prime))

p = 0
count = {}
for i in range(1,max_l+2,2):
    if (i in prime) and ((i+1)/2 in prime):
        p += 1
    count[i] = p
count[-1] = 0
for i in range(Q):
    print(count[lr[i][1]]-count[lr[i][0]-2])


### FIXED CODE ###

import math
Q = int(input())
lr = [list(map(int, input().split())) for i in range(Q)]

max_l = max(lr, key=lambda x:x[1])[1]

prime = list(range(2,int(math.ceil(max_l**0.5)+1)))

m = 1
while True:
    b = filter(lambda x: x%prime[m-1] != 0,prime[m:])
    prime = prime[:m]
    prime.extend(b)
    m += 1
    if m > len(prime):
        break

like2017 = {-1:0,1:0}
for i in range(3,max_l+2,2):
    k = 0
    for j in prime:
        if (i%j == 0 or ((i+1)/2)%j == 0) and i != j and (i+1)/2 != j:
            k += 1
            break
    if k == 0:
        like2017[i] = like2017[i-2] + 1
    else:
        like2017[i] = like2017[i-2]


for i in range(Q):
    print(like2017[lr[i][1]]-like2017[lr[i][0]-2])
### BUGGY CODE ###

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

for i in range(n):
    print(a.count(i+1))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
count=[0]*n
for i in range(n-1):
    count[a[i]-1]=count[a[i]-1]+1

for i in range(n):
    print(count[i])
### BUGGY CODE ###

N, M = list(map(int, input().split()))
A=[0] * M
B=[0] * M

import math

for i in range(M):
  A[i], B[i] = list(map(int, input().split()))

  
island_dict = [i for i in range(N+1)] #{i+1:i+1 for i in range(N)} #島が属するグループ
#group_dict = [[i] for i in range(N+1)] #{i+1:[i+1] for i in range(N)} #グループに属する島
group_len_dict= [1 for i in range(N+1)] #{i+1:1 for i in range(N)}

answer = [0] * M
answer[-1] = math.factorial(N) // (math.factorial(N-2)*2)
  
for i in range(M)[:0:-1]:
  if island_dict[A[i]] == island_dict[B[i]]:
    answer[i-1] = answer[i]
  else:
    groupA = island_dict[A[i]]
    groupB = island_dict[B[i]] #グループ合併, groupB消滅
    NA = group_len_dict[groupA]
    NB = group_len_dict[groupB]
    
    if NA>=NB:
      island_dict = [groupA if g==groupB else g for g in island_dict]
      group_len_dict[groupA] = group_len_dict[groupA] + group_len_dict[groupB]
      
    else:
      island_dict = [groupB if g==groupA else g for g in island_dict]
      group_len_dict[groupB] = group_len_dict[groupA] + group_len_dict[groupB]

      
    answer[i-1] = answer[i] - NA*NB


for i in range(M):
  print(answer[i])
    
    

### FIXED CODE ###

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

roots = [(i,1) for i in range(N+1)] # root, num_islands_in_group

inconveniences = [0]*(M+1)
inconveniences[-1] = N*(N-1)//2 #すべての橋が崩落するとNC2

def find_root(a, roots=roots):
  if roots[a][0] == a:
    return roots[a]
  else:
    roots[a] = find_root(roots[a][0])
  return roots[a]

def reduce_inconvenience_with_unite(a, b, roots=roots):
  root_a, n_a = find_root(a)
  root_b, n_b = find_root(b)
  if root_a == root_b:
    return 0
  else:
    if n_a > n_b:
      roots[root_a] = (root_a, n_a + n_b) # 二項目は何でも良い
      roots[root_b] = (root_a, n_a + n_b)
    else:
      roots[root_a] = (root_b, n_a + n_b) # 二項目は何でも良い
      roots[root_b] = (root_b, n_a + n_b)
    return n_a * n_b

for i, ab in enumerate(AB[:0:-1]): #実は1個めの橋は全く関係ない
  a, b = ab
  inconveniences[M-1-i] = inconveniences[M-i] - reduce_inconvenience_with_unite(a,b)

for inc in inconveniences[1:]:
  print(inc)
### BUGGY CODE ###

n = int(input())
for i in range(1, n+1):
    count = 0
    x = 1
    while (x+1)**2 <= i-2:
        y = 1
        while x**2 + y**2 + x*y + x + y <= i-1:
            z = 1
            while x**2 + y**2 + z**2 +x*y + y*z + z*x <= i:
                if x**2 + y**2 + z**2 +x*y + y*z + z*x == i:
                    count += 1
                    break
                else:
                    z += 1
            y += 1
        x += 1
    print(count)

### FIXED CODE ###

n = int(input())
ans = [0 for i in range(10050)]
for x in range(1, 105):
    for y in range(1, 105):
        for z in range(1, 105):
            f = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if f < 10050:
                ans[f] += 1
for i in range(n):
    print(ans[i+1])
### BUGGY CODE ###

l, r = list(map(int, input().split()))
MOD = 2019
diff = r - l
l = l%MOD
r = l + diff
ans = 2018
for i in range(l,r):
    for j in range(i+1, r+1):
        ans = min(ans, (i%MOD*j%MOD)%MOD )
      
print(ans)

### FIXED CODE ###

l, r = list(map(int, input().split()))
MOD = 2019
diff = r - l
ans = 0
if diff < 2019:
    l = l%MOD
    r = l + diff
    ans = 2018
    for i in range(l,r):
        for j in range(i+1, r+1):
            ans = min(ans, (i%MOD*j%MOD)%MOD )
      
print(ans)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
MOD = 998244353

def comb(n, r, mod=MOD):
    r = min(n - r, r)
    res = 1
    fac = 1
    for i in range(r):
        res *= n - i
        res %= mod
        fac *= i + 1
        fac %= mod
    return res * pow(fac, mod-2, mod) % mod

def main():
    N, M, K = map(int, readline().rstrip().split())
    res = 0
    for k in range(K+1):
        n = N - k
        res += comb(N-1, k, MOD) * pow(M-1, n-1, MOD) * M
        res %= MOD
    
    print(res)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline
MOD = 998244353

N, M, K = map(int, readline().rstrip().split())
fact = [1] * (N+1)
finv = [1] * (N+1)
inv = [1] * (N+1)
inv[0] = 0
for i in range(2, N+1):
    fact[i] = (fact[i-1] * i % MOD)
    inv[i] = (-inv[MOD%i] * (MOD // i)) % MOD
    finv[i] = (finv[i-1] * inv[i]) % MOD

def comb(n, r, mod=MOD):
    if r < 0 or n < r:
        return 0
    return fact[n] * finv[r] * finv[n-r] % mod

def main():
    res = 0
    for k in range(K+1):
        res += comb(N-1, k, MOD) * pow(M-1, N-k-1, MOD) * M
        res %= MOD
    
    print(res)


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

N,Q = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(N-1)]
px = [list(map(int,input().split())) for i in range(Q)]

graph={}
for i in range(1,N+1):
    graph[i]=[]
for i in range(N-1):
    graph[ab[i][0]].append(ab[i][1])
    graph[ab[i][1]].append(ab[i][0])

value = [0] * (N+1)
for p,x in px:
    value[p] += x

from collections import deque
todo = deque([[1,0]])
while len(todo) > 0:
    x,parent = todo.pop()
    value[x] += value[parent]
    for y in graph[x]:
        if y == parent:
            continue
        todo.append([y,x])

print(*value[1:])

### FIXED CODE ###

N,Q = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(N-1)]
px = [list(map(int,input().split())) for i in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N+1)
for p,x in px:
    value[p] += x

from collections import deque
todo = deque([(1,0)])
while len(todo) > 0:
    x,parent = todo.pop()
    value[x] += value[parent]
    for y in graph[x]:
        if y == parent:
            continue
        todo.append((y,x))

answer = ' '.join(map(str,value[1:]))
print(answer)
### BUGGY CODE ###

import sys

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

Result = 0

Count_Blue = 0
if 1<=N<=10**18 and A >= 0 and B >= 0 and \
   0< A + B <= 10**18:
    for Count in range(1,10**100+1):
        if Result < N:
            Mod = Count % 2
            if Mod==1:
                for i in range(A):
                    if Result < N:
                        Result = Result + 1
                        Count_Blue += 1
            elif Mod==0:
                Result = Result + 1 * B
        else:
            print(Count_Blue)
            sys.exit()

### FIXED CODE ###

import sys

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

Count_Blue = 0
if 1<=N<=10**18 and A > 0 and B >= 0 and \
   0< A + B <= 10**18:
    Add_Blue = 1 * A
    Add_Both = Add_Blue + 1 * B

    q = N // Add_Both
    mod = N % Add_Both
    if mod < Add_Blue:
        Count_Blue = (q *Add_Blue) + mod
    else:
        Count_Blue = (q * Add_Blue) + Add_Blue
    print(Count_Blue)
elif A == 0:
    print(Count_Blue)
### BUGGY CODE ###

N,K = [int(x) for x in input().split()]
count = [0]*(K+1)
ans = 0
for i in range(K,0,-1):
    kosuu = (K//i)**N
    if K // i >= 2:
        for j in range(K//i,1,-1):
            kosuu -= count[j*i]
    ans += (i*kosuu)%1000000007
    count[i] = kosuu
print(ans%1000000007)

### FIXED CODE ###

N,K = [int(x) for x in input().split()]
count = [0]*(K+1)
ans = 0
mod = 1000000007
for i in range(K,0,-1):
    kosuu = pow(K//i,N,mod)
    if K // i >= 2:
        for j in range(K//i,1,-1):
            kosuu -= count[j*i]
    ans += i*kosuu
    count[i] = kosuu
print(ans%mod)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
ans = (sum(p[:k])+k)/2
for i in range(1, n-k+1):
    p3 =  (sum(p[(i):(k+i)])+k)/2
    ans = max([ans, p3])
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
tmp = sum(p[:k])
ans = [tmp]
if n == k:
    ans_mae = ans[0]
    print((ans_mae+k)/2)
else:
    for i in range(1,n-k+1):
        tmp = tmp - p[i-1] + p[i+k-1]
        ans.append(tmp)
    print((max(ans)+k)/2)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
a=0
for i in range(len(A)):
    if A.count(A[i])+A.count(A[i]-1)+A.count(A[i]+1)>a:
        a=A.count(A[i])+A.count(A[i]-1)+A.count(A[i]+1)
print(a)

### FIXED CODE ###

import collections
N=int(input())
A=list(map(int,input().split()))
B=dict(collections.Counter(A))
a=0
Bk=B.keys()
for i in Bk:
    if i-1 in Bk:
        if i+1 in Bk:
            if a<B[i]+B[i-1]+B[i+1]:
                a=B[i]+B[i-1]+B[i+1]
        else:
            if a<B[i]+B[i-1]:
                a=B[i]+B[i-1]
    elif i+1 in Bk:
        if a<B[i]+B[i+1]:
            a=B[i]+B[i+1]
    else:
        if a<B[i]:
            a=B[i]
print(a)