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

#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))


N = int(input())

for n in range(1, N + 1):
    ans = 0
    n_range = int(math.sqrt(n))
    for z in range(1, n_range):
        y_range = int(math.sqrt(n - z ** 2))
        for y in range(1, min(n_range, y_range)):
            x_range = int(math.sqrt(n - y ** 2 - z ** 2))
            for x in range(1, min(x_range, n_range)):
                if x**2 + y**2 + z ** 2 + x*y + y*z + x*z == n:
                    ans += 1
    print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))


N = int(input())

anss = [0 for i in range(N + 1)]
for x in range(1, int(math.sqrt(N))):
    for y in range(1, int(math.sqrt(N))):
        for z in range(1, int(math.sqrt(N))):
            tmp = x ** 2 + y ** 2 + z ** 2 + x*y + x*z + y*z
            if tmp <= N:
                anss[tmp] += 1 

for i in range(1, N + 1):
    print(anss[i])
### BUGGY CODE ###

import math
from functools import lru_cache, reduce


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def prefix_sum(arr, a):
    arr.append(arr[-1]+a)
    return arr


def solve():
    """
    OPT[i][j] = min(OPT[i][k]+OPT[k+1][j])+sum(A[i:j+1])    i <= k < j
    OPT[i][j] = 0 if i == j
    """
    N = read_int()
    A = read_ints()
    prefix = reduce(prefix_sum, A, [0])

    @lru_cache(None)
    def dp(i, j):
        if i == j:
            return 0
        return min(dp(i, k)+dp(k+1, j)+(prefix[j+1]-prefix[i]) for k in range(i, j))

    return dp(0, N-1)


if __name__ == '__main__':
    print(solve())


### FIXED CODE ###

import math
from functools import lru_cache, reduce


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def prefix_sum(arr, a):
    arr.append(arr[-1]+a)
    return arr


def solve():
    """
    OPT[i][j] = min(OPT[i][k]+OPT[k+1][j])+sum(A[i:j+1])    i <= k < j
    OPT[i][j] = 0 if i == j
    """
    N = read_int()
    A = read_ints()
    prefix = reduce(prefix_sum, A, [0])

    @lru_cache(None)
    def dp(i, j):
        if i == j:
            return 0
        return min(dp(i, k)+dp(k+1, j)+(prefix[j+1]-prefix[i]) for k in range(i, j))

    OPT = [[0]*N for _ in range(N)]
    for j in range(N):
        for i in range(j-1, -1, -1):
            OPT[i][j] = min(OPT[i][k]+OPT[k+1][j] for k in range(i, j))+(prefix[j+1]-prefix[i])

    return OPT[0][N-1]


if __name__ == '__main__':
    print(solve())
### BUGGY CODE ###

N = int(input())
ans = 0

def pf(n):
    ret = []
    for i in range(2, n):
        if n % i != 0: continue
        c = 0
        while n % i == 0:
            c += 1
            n //= i
        ret.append((i, c))
    while n % 2 ==0:
        n //= 2
        ret.append(2)
    f = 3
    c = 0
    while f * f <= n:
        if n % f == 0:
            c += 1
            n //= f
        else:
            ret.append((f, c))
            c = 0
            f += 2
    if n != 1:
        ret.append((n, 1))
    return ret

for p in pf(N):
    i, c = p
    t = 1
    while c >= t:
        c -= t
        t += 1
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0

d = 2
while d * d < n:
    if n % d != 0:
        d += 1
        continue

    e = d
    while n % e == 0:
        n //= e
        e *= d
        ans += 1

    while n % d == 0:
        n //= d
if n != 1:
    ans += 1

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

import sys
sys.setrecursionlimit(10000000)
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
INF = 500000
mod = 10**9+7

N = int(input())
A = [int(x) for x in input().split()]
dic = defaultdict(lambda : 0)
for a in A:
    for i in range(2, int(a**0.5)+1):
        if a % i == 0:
            c = 0
            while a % i == 0:
                c += 1
                a //= i
            if dic[i] < c:
                dic[i] = c
    if a > 1 and dic[a] == 0:
        dic[a] = 1
MAX = 1
for k in dic:
    MAX *= pow(k, dic[k])
ans = 0
for a in A:
    ans += MAX//a
    ans %= mod
print(ans)


### FIXED CODE ###

import sys
# sys.setrecursionlimit(1000000)
input = sys.stdin.readline
# from bisect import *
from collections import *
# from heapq import *
# INF = 500000
mod = 10**9+7

def primes(n):
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1, int(n**0.5)//3+1):
        if sieve[i]:
            k = 3*i+1|1
            sieve[k*k//3::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2, 3] + [3*i+1|1 for i in range(1, n//3-correction) if sieve[i]]

N = int(input())
A = [int(x) for x in input().split()]
ps = primes(int(max(A)**0.5)+1)
dic = defaultdict(lambda : 0)
for a in A:
    for i in ps:
        if a < i:
            break
        if a % i == 0:
            c = 0
            while a % i == 0:
                c += 1
                a //= i
            if dic[i] < c:
                dic[i] = c
    if a > 1 and dic[a] == 0:
        dic[a] = 1
MAX = 1
for k in dic:
    MAX = MAX * pow(k, dic[k], mod) % mod
ans = 0
for a in A:
    ans += MAX * pow(a, mod-2, mod)
    ans %= mod
print(ans)
### BUGGY CODE ###

N, Q = [int(item) for item in input().split()]

tree_list = [input().split() for j in range(1, N)]
query_list = [input().split() for k in range(Q)]


class Node:
    def __init__(self, val):
        self.val = val
        self.child_list = []
        self.cnt = 0

class my_tree:
    def __init__(self, tree_list):
        self.node_list = []

        for i in range(N):
            self.node_list.append(Node(i+1))

        for a, b in tree_list:
            a, b = int(a), int(b)

            child_node = self.node_list[b-1]
            parent_node = self.node_list[a-1]
            self.node_list[a-1].child_list.append(child_node)
            self.node_list[b-1].child_list.append(parent_node)
        
    def adding(self, query_list):
        for a, data in query_list:
            a, data = int(a), int(data)
            self.node_list[a-1].cnt += data

        stack = [self.node_list[0]]
        parent_node_list = [self.node_list[0]]*(N + 1)

        while True:
            v = stack.pop()
            for child in v.child_list:
                if child != parent_node_list[v.val -1]:
                    child.cnt += v.cnt
                    parent_node_list[child.val -1] = v
                    stack.append(child)
            
            if len(stack) == 0:
                break


ins = my_tree(tree_list)
ins.adding(query_list)
print(*[node.cnt for node in ins.node_list])


### FIXED CODE ###

N, Q = [int(item) for item in input().split()]

tree_list = [input().split() for j in range(1, N)]

query_list = [input().split() for k in range(Q)]
query_list_int = [[int(k) for k in i] for i in query_list]

val_list = [0 for _ in range(N)]

linked_node_list = [[] for _ in range(N)]

for a, b in tree_list:
    a, b = int(a)-1, int(b) -1
    linked_node_list[a].append(b)
    linked_node_list[b].append(a)


for index, val in query_list_int:
    val_list[index-1] += val

stack = [0]
parent = [0] * (N+1)

while True:
    v=stack.pop()
    for child in linked_node_list[v]:
        if child != parent[v]:
            parent[child] = v
            stack.append(child)
            val_list[child] += val_list[v]
    if not stack:
        break

print(*val_list)
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


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

    result = []

    for i in range(1, N):
        result.append(abs(sum(A[:i]) - sum(A[i:])))
    print(min(result))


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


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

    A_sum = sum(A)
    tmp = 0

    result = []

    for a in A:
        tmp += a
        result.append(abs(A_sum - tmp * 2))
    print(min(result[:-1]))


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

import numpy as np

N = int(input())
A = [int(i) for i in input().split()]
A = np.array(A)
B = np.zeros(N)
list_B = [0] * N

for i in range(N)[::-1]:
  if A[i] != (np.sum(B[i::i+1]) % 2):
    B[i] = 1
    list_B[i] = i + 1

print(int(np.sum(B)))
list_B = ' '.join([str(a) for a in [i for i in list_B if i != 0]])
print(list_B)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
B = [0] * N
list_B = [0] * N

for i in range(N)[::-1]:
  if A[i] != (sum(B[i::i+1]) % 2):
    B[i] = 1
    list_B[i] = i + 1

print(int(sum(B)))
list_B = ' '.join([str(a) for a in [i for i in list_B if i != 0]])
print(list_B)
### BUGGY CODE ###

n=int(input())
a=list(map(int, input().split()))
for value in range(n):
    print(a.count(value+1))

### FIXED CODE ###

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

c = collections.Counter(a)
for value in range(n):
    if value == 0:
        continue
    else:
        print(c[value])
print(0)
### BUGGY CODE ###

from operator import mul
from functools import reduce
N = int(input())
A = list(map(int, input().split()))

if 0 in A:
    print(0)
else:
    sum=reduce(mul,A)
    if sum>1000000000000000000:
        print(-1)
    else:
        print(sum)

### FIXED CODE ###


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

if 0 in A:
    print(0)
else:
    for n in range(N):
        sum = sum * A[n]
        if sum>1000000000000000000:
            print(-1)
            break
    else:
        print(sum)
### BUGGY CODE ###

import collections
S=input()
l=len(S)
t=0
p=0
m=[]
ss=[0]*2019
ss[0]=1
for i in range(l):
    p=(p+int(S[i])*(10**(l-1-i)))%2019
    ss[p]+=1
for c in ss:
    t+=c*(c-1)//2
print(t)


### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

N,K=map(int,input().split())
a=[]

for i in range(N):
    b=int(input())
    a.append(b)

a=sorted(a)


min=a[K-1]-a[0]
for j in range(N-K+1):
    s=a[j:j+K]
    
    if min >= s[K-1]-s[0]:
        min=s[K-1]-s[0]
        
print(min)      

### FIXED CODE ###

N,K=map(int,input().split())
a=[]

for i in range(N):
    b=int(input())
    a.append(b)

a=sorted(a)

b=[]
for j in range(N-K+1):
    c=a[j+K-1]-a[j]
    b.append(c)    
        
print(min(b))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
B = []
cnt = 0
for i in range(N):
    if A[i] in B == True:
        cnt += 1
    else:
        for j in range(i):
            if A[i] % A[j] == 0:
                cnt += 1
                if A[i] == A[j] and i == j+1:
                    cnt += 1
                for k in range(10 ** 5):
                    B.append(A[i] * k)
                break
print(N - cnt)


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
counter = Counter(A)
B = [1] * (max(A) + 1)
for a in A:
    for k in range(a  * 2,len(B),a):
            B[k] = 0
print(sum(B[a] == 1 and counter[a] == 1 for a in A))
### BUGGY CODE ###

import collections
import itertools

n = int(input())
S = [''.join(sorted(input())) for _ in range(n)]
d = [len(list(itertools.combinations(range(v),2))) for v in collections.Counter(S).values()]
print(sum(d))

### FIXED CODE ###

N = int(input())
S = [list(input()) for _ in range(N)]
cnt = 0
dic = {}
for s in S:
    s.sort()
    s_ = "".join(s)
    if s_ in dic.keys():
        cnt += dic[s_]
        dic[s_] += 1
    else:
        dic[s_] = 1
print(cnt)
### BUGGY CODE ###

class UnionFind:
    def __init__(self, n, p):
        '木の初期化をする'
        # zero-index
        self.p  = [-1] * n
        self.rank = [1]*n
        # one -index
        self.g  = [set([i]) for i in range(n+1)]
        self.gp = [set([i]) for i in p]

    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.g[y+1] = self.g[y+1] | self.g[x+1]
            self.gp[y+1]= self.gp[y+1]| self.gp[x+1]
            self.p[x] = y # x の親を y にする
            return True
        else:
            return False

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

def main():
    n,m = map(int,input().split())
    p = [0] + list(map(int,input().split()))

    uf = UnionFind(n,p)
    for i in range(m):
        x,y = map(int,input().split())
        uf.unite(x-1,y-1)

    parent = [False]*n
    ans = 0
    for i in range(n):
        j = uf.find(i)
        if not parent[j]:
            parent[j] = True
            ans += len(uf.g[j+1]) + len(uf.gp[j+1]) - len(uf.g[j+1] | uf.gp[j+1])
    # ans = 0
    # for j in parent:
    #     ans += len(uf.g[j+1]) + len(uf.gp[j+1]) - len(uf.g[j+1] | uf.gp[j+1])
    print(ans)
main()


### FIXED CODE ###

class UnionFind:
    def __init__(self, n, p):
        '木の初期化をする'
        # zero-index
        self.p  = [-1] * n
        self.rank = [1]*n

    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.p[x] = y # x の親を y にする
            return True
        else:
            return False

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

def main():
    n,m = map(int,input().split())
    p = list(map(int,input().split()))

    uf = UnionFind(n,p)
    for i in range(m):
        x,y = map(int,input().split())
        uf.unite(x-1,y-1)

    ans = 0
    for i,j in enumerate(p):
        ans += uf.same(i, j-1)
    print(ans)
main()
### BUGGY CODE ###

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

def main():
    countb = 0
    count = 0
    while(1):
        for i in range(A):
            count+=1
            countb+=1
            if count >=N:
                return countb
        for i in range(B):
            count+=1
            if count >=N:
                return countb
a = main()

print(a)

### FIXED CODE ###

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

num = N // (A+B) * A
amari = N % (A+B)
num += min(amari, A)

print(num)
### BUGGY CODE ###

#!usr/bim/python
#! -*- coding: utf-8 -*-

import numpy as np

nc = raw_input()
nc = nc.split()
n,c = map(int,nc)

tt = np.zeros([(10**5),c],int)

for i in range(n):
    stc = raw_input()
    stc = stc.split()
    s,t,c = map(int,stc)
    j = s
    while j <= t:
        tt[j-1][c-1] = 1
        j += 1

ans = 1
for i in range(10**5):
    ans = max(ans,sum(tt[i]))

print ans


### FIXED CODE ###

#!usr/bim/python
#! -*- coding: utf-8 -*-

import numpy as np

nc = raw_input()
nc = nc.split()
n,c = map(int,nc)

tt = np.zeros([(10**5),c],int)

for i in range(n):
    stc = raw_input()
    stc = stc.split()
    s,t,c = map(int,stc)
    j = s
    while j <= t:
        tt[j-1][c-1] = 1
        j += 1

ans = np.max(np.sum(tt, axis=1))

print ans
### BUGGY CODE ###

P=998244353
N,K=map(int,input().split())
LR=[]
for _ in range(K):
  l,r=map(int,input().split())
  LR+=range(l,r+1)
LR=list(set(LR))
c=[0]*N
c[0]=1
for k in range(N):
  S=[x for x in LR if x<=k]
  while len(S):
    c[k]+=c[k-S[-1]]%P
    S.pop()
print(c[-1]%P)

### FIXED CODE ###

P=998244353
N,K=map(int, input().split())
LR=[list(map(int, input().split())) for _ in range(K)]

s=[0 for _ in range(N+1)]
s[1]=1
for i in range(1,N):
  s[i+1] = s[i]
  for l,r in LR:
    s[i+1]+=(s[max(0,i-l+1)]-s[max(0,i-r)])%P
    s[i+1]%=P
print((s[N]-s[N-1])%P)
### BUGGY CODE ###

l,r=map(int,input().split())
ans=2018
for i in range(l,r):
    for j in range(i+1,r+1):
        ans=min(i*j%2019,ans)
        if ans==0:
            break
print(ans)

### FIXED CODE ###

l,r=[int(i) for i in input().split()]
ans=2018
for i in range(l,r):
    for j in range(i+1,r+1):
        ans=min(i*j%2019,ans)
        if ans==0:
            print(ans)
            exit()
print(ans)
### BUGGY CODE ###

X, Y ,Z ,K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

C.sort(reverse=True)

ab_scores = sorted([a + b for a in A for b in B], reverse=True)[:K]
scores = sorted([ab + c for ab in ab_scores for c in C], reverse=True)

for i in scores[:K]:
    print(i)


### FIXED CODE ###

X, Y ,Z ,K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)


scores = []
for a in range(len(A)):
    for b in range(len(B)):
        if (a + 1) * (b + 1) > K:
            break
        for c in range(len(C)):
            if (a + 1) * (b + 1) * (c + 1) > K:
                break
            score = A[a] + B[b] + C[c]
            scores.append(score)

scores.sort(reverse=True)

for i in range(K):
    print(scores[i])
### BUGGY CODE ###

N = int(input())
S_dict = {}

for i in range(N):
    s = input()
    if s in S_dict.keys():
        S_dict[s] += 1
    else:
        S_dict[s] = 1

max_S = sorted([d[0] for d in S_dict.items() if d[1]==max(S_dict.values())])
for i in max_S:
    print(i)

### FIXED CODE ###

from collections import Counter

stdin = open(0)
N = int(stdin.readline())
S = stdin.read().split()

counter = Counter(S)
max_cnt = max(counter.values())
names = [n for n,c in counter.items() if c==max_cnt]
names.sort()
print(*names, sep='\n')
### BUGGY CODE ###

class unionfind:
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def find(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
import sys
input=sys.stdin.readline
n=int(input())
l=sorted([tuple(map(int,input().split())) for i in range(n)])
import collections
d=collections.defaultdict(int)
j=1
for i in l:
    if d[i]==0:
        d[i]=j
        j+=1
from heapq import heappush,heappop
pq=[]
for i in range(n-1):
    c=l[i+1][0]-l[i][0]
    heappush(pq,(c,l[i],l[i+1]))
l.sort(key=lambda x:x[1])
for i in range(n-1):
    c=l[i+1][1]-l[i][1]
    heappush(pq,(c,l[i],l[i+1]))
ans=0
uf=unionfind(n)
while pq:
    c,x,y=heappop(pq)
    x,y=d[x],d[y]
    if not uf.same(x,y):
        ans+=c
        uf.unite(x,y)
print(ans)

### FIXED CODE ###

class unionfind:
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def find(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
import sys
input=sys.stdin.readline
n=int(input())
l=[tuple(map(int,input().split())) for i in range(n)]
l.sort(key=lambda x:x[0])
import collections
d=collections.defaultdict(int)
j=1
for i in l:
    if d[i]==0:
        d[i]=j
        j+=1
pq=[]
for i in range(n-1):
    pq.append((l[i+1][0]-l[i][0],d[l[i]],d[l[i+1]]))
l.sort(key=lambda x:x[1])
for i in range(n-1):
    pq.append((l[i+1][1]-l[i][1],d[l[i]],d[l[i+1]]))
ans=0
pq.sort(key=lambda x:x[0])
uf=unionfind(n)
for c,x,y in pq:
    if not uf.same(x,y):
        ans+=c
        uf.unite(x,y)
print(ans)
### BUGGY CODE ###

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

for _ in range(0, N):
    for _ in range(0, A):
        list.append('b')
    for _ in range(0, B):
        list.append('r')

for i in range(0, N):
    if list[i] == 'b':
        count = count + 1


print(count)


### FIXED CODE ###

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

x = N // (A + B)
y = N % (A + B)


if y <= A:
    print(x * A + y)
else:
    print(x*A+A)
### BUGGY CODE ###

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

import sys

for scc in range(M//2, -1, -1):
    excess_c = M - scc*2
    if excess_c//2 + N >= scc:
        print(scc)
        sys.exit(0)

print(0)

### FIXED CODE ###

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

if N < M//2:
    scc_min = max(1, N)
else:
    scc_min = M//2
scc_max = N + M//2

while scc_min < scc_max:
    scc = (scc_min + scc_max) // 2
    excess_c = M - scc*2
    if scc_min + 1 == scc_max:
        break
    if excess_c > 0 and excess_c//2 + N >= scc:
        scc_min = scc
    else:
        scc_max = scc - 1

excess_c = M - scc_max*2
if excess_c > 0 and excess_c//2 + N >= scc_max:
    print(scc_max)
else:
    print(scc_min)
### BUGGY CODE ###

s=input()
n=len(s)
t=[]
mod=2019
for i in range(n):
    t.append(int(s[i:])%mod)
t.append(0)
from collections import Counter
d=Counter(t)
ans=0
for v in d.values():
    ans+=(v*(v-1))//2
print(ans)

### FIXED CODE ###

s=input()
n=len(s)
mod=2019
sum=0
p=1
d={}
d[0]=1
for i in range(n-1,-1,-1):
    sum=(sum+int(s[i])*p)%mod
    if sum in d:
        d[sum]+=1
    else:
        d[sum]=1
    p=(p*10)%mod
ans=0
for v in d.values():
    ans+=(v*(v-1))//2
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
s = 0
cnt = 0
m = 0
for i in range(n):
    for j in range(m,n):
        s += a[j]
        if s == 0:
            cnt += 1
    m += 1
    s = 0
print(cnt)

### FIXED CODE ###

import math
from collections import Counter
from itertools import accumulate

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

def C(n,r):
    return P(n,r)//math.factorial(r)

n = int(input())
a = list(map(int,input().split()))
ac = [0] + list(accumulate(a))
c = Counter(ac)

cnt = 0
for v in c.values():
    if v >= 2:
        cnt += C(v,2)
print(cnt)