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

h,w=map(int,input().split())
from itertools import *
g=[input() for _ in range(h)]
cw=[[] for _ in range(h)]
for i in range(h):
  gw=[(s,len(list(c))) for s,c in groupby(g[i])]
  for s,c in gw:
    if s=='.': cw[i]+=[c]*c
    else: cw[i]+=[0]*c
gt=list(zip(*g))
ch=[[] for _ in range(w)]
for i in range(w):
  gh=[(s,len(list(c))) for s,c in groupby(gt[i])]
  for s,c in gh:
    if s=='.': ch[i]+=[c]*c
    else: ch[i]+=[0]*c
ch=list(zip(*ch))
print(max(cw[i][j]+ch[i][j]-1 for i in range(h) for j in range(w)))

### FIXED CODE ###

h,w=map(int,input().split())
f=lambda:[[0]*w for _ in range(h)]
g=[input() for _ in range(h)]
l,r=f(),f()
for i in range(h):
  lc=rc=0
  for j in range(w):
    if g[i][j]=='.': lc+=1; l[i][j]=lc
    else: lc=0
    if g[i][-1-j]=='.': rc+=1; r[i][-1-j]=rc
    else: rc=0
d,u=f(),f()
for i in range(w):
  dc=uc=0
  for j in range(h):
    if g[j][i]=='.': dc+=1; d[j][i]=dc
    else: dc=0
    if g[-1-j][i]=='.': uc+=1; u[-1-j][i]=uc
    else: uc=0
print(max(l[i][j]+r[i][j]+d[i][j]+u[i][j]-3 for i in range(h) for j in range(w)))
### BUGGY CODE ###

n = int(input())

tt = list(map(int, input().split()))
v = list(map(int, input().split()))

time = sum(tt);

border = [0] *(n+1)
start_v = [0] *(n+1)
end_v = [0] *(n+1)

temp = 0
for i in range(n):
	temp += tt[i]
	border[i+1] = temp
	start_v[i] = v[i]
	end_v[i+1] = v[i]

t = 0
idx = 0
ans = 0
vlast = 0
v0 = 0

# print (border)
while t < time :
	t += 0.5
	
	# tle回避
	if t < border[idx+1] and abs(v0- (vlast-0.5) ) < 0.001:
		v0 = vlast - 0.5
		ans += 0.5 * (vlast + v0) / 2
		vlast = v0
		continue

	#直接制約
	v0 = v[idx]
	if t == border[idx+1]:
		idx += 1
#		v0 = min(v0, v[idx])

	for j in range(len(border)):
		
		if border[j] <= t:
			#前の時刻からの制約
			temp = end_v[j] + (t - border[j])
			if v0 > temp:
				v0 = temp
		if border[j] >= t:
			#後ろの時刻からの制約
			temp = start_v[j] + (border[j] - t)
			if v0 > temp:
				v0 = temp

#	print(v0)

	ans += (vlast + v0)
	vlast = v0

ans /= 4.0
print (ans)



### FIXED CODE ###

n = int(input())

tt = list(map(int, input().split()))
v = list(map(int, input().split()))

time = sum(tt);
INF = 999999
border = [0] *(n+1)
start_v = [0] *(n+1)
end_v = [0] *(n+1)

temp = 0
for i in range(n):
	temp += tt[i]
	border[i+1] = temp
	start_v[i] = v[i]
	end_v[i+1] = v[i]

t = 0
idx = 0
ans = 0
vlast = 0
v0 = 0
new_interval = False
limitation_front =0 # 最初の計算に必要

# print (border)
while t < time :
	t += 0.5
	new_interval = False

	#直接制約
	v0 = v[idx]
	if t == border[idx+1]:
		idx += 1
		new_interval = True
#		v0 = min(v0, v[idx])

	if(not new_interval):
		limitation_front += 0.5
		if v0 > limitation_front:
			v0 = limitation_front
	
	if new_interval: 
		limitation_front = INF
		for j in range(n+1):
			if border[j] <= t:
				#前の時刻からの制約
				temp = end_v[j] + (t - border[j])
				if v0 > temp:
					v0 = temp
				if limitation_front > temp:
					limitation_front = temp
			else:
				break
			#print (limitation_front)


	for j in range(n+1):
		if border[j] >= t:
			#後ろの時刻からの制約
			temp = start_v[j] + (border[j] - t)
			if v0 > temp:
				v0 = temp

	#print(v0)

#	ans += 0.5 * (vlast + v0) / 2
	ans += (vlast + v0)
	vlast = v0

ans /= 4.0
print (ans)
### BUGGY CODE ###

import itertools

N, C = map(int, input().split())
D = [tuple(map(int, input().split())) for _ in range(C)]
L = [tuple(map(int, input().split())) for _ in range(N)]

lst = [[0] * 3 for _ in range(C)]
for y in range(N):
    for x in range(N):
        for c in range(C):
            lst[c][(x + y) % 3] += D[L[y][x] - 1][c]

ans = float('inf')
for t in itertools.permutations(range(C),3):
    ans = min(ans, sum(lst[t[i]][i] for i in range(3)))
print(ans)


### FIXED CODE ###

import itertools

N, C = map(int, input().split())
D = [tuple(map(int, input().split())) for _ in range(C)]
L = [tuple(map(int, input().split())) for _ in range(N)]

lst = [[0] * 3 for _ in range(C)]
for y in range(N):
    for x in range(N):
        for c in range(C):
            lst[c][(x + y) % 3] += D[L[y][x] - 1][c]

ans = float('inf')
for t in itertools.permutations(range(C), 3):
    ans = min(ans, sum(lst[t[i]][i] for i in range(3)))
print(ans)
### BUGGY CODE ###

from operator import itemgetter

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

num = N
for i in range(N)[::-1]:
    sort_A[i] = A.index(num) + 1
    num -= 1

print(' '.join(list(map(str,sort_A))))

### FIXED CODE ###

from operator import itemgetter

N = int(input())
A = list(map(int,input().split()))
index_A = sorted([[i+1,x] for i,x in enumerate(A)],key=itemgetter(1))
A = [i[0] for i in index_A]

print(" ".join(list(map(str,A))))
### BUGGY CODE ###

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

def resolve(a):
    target = N
    result = 0
    for i in a:
        if target > i: target = i
        result += target
    return result

print(sum([resolve(a[x:]) for x in range(N)]))


### FIXED CODE ###

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

index = [-1] * (n + 1)
for i, v in enumerate(a):
    index[v] = i

area = [[i, i] for i in range(n + 1)]
result = 0
for i in range(n, 0, -1):
    position = index[i]
    l, r = area[position]
    area[r + 1][0] = l # right
    area[l - 1][1] = r # left
    result += (position - l + 1) * (r - position + 1) * i
print(result)
### BUGGY CODE ###

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

for v in range(A, B+1):
    if v < A+K or B-K < v:
        print(v)

### FIXED CODE ###

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

if A+K-1 < B-K+1:
    l = list(range(A, A+K))+list(range(B-K+1, B+1))
else:
    l = list(range(A, B+1))

for v in l:
    print(v)
### BUGGY CODE ###

from collections import Counter

n = int(input())
c_list = []
ans = 0

for i in range(n):
  c = Counter(input())
  ans += c_list.count(c)
  c_list.append(c)
  
print(ans)
    

### FIXED CODE ###

from collections import Counter

n = int(input())
ans = 0
ctr = Counter()

for i in range(n):
  s = ''.join(sorted(list(input())))
  if s in ctr:
    ans += ctr[s]
  ctr[s] += 1
  
print(ans)
### BUGGY CODE ###

import numpy as np
n, k = map(int, input().split())
a = list(map(int, input().split()))

for i in range(min(k, 50)):
    b = [0] * (n + 1)
    for j in range(n):
        l = max(0, j - a[j])
        r = min(n - 1, j + a[j])
        b[l] += 1
        b[r + 1] -= 1
    a = np.cumsum(b)[:-1]
print(*a)


### FIXED CODE ###

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

for i in range(min(k, 50)):
    b = [0] * (n + 1)
    for j in range(n):
        l = max(0, j - a[j])
        r = min(n - 1, j + a[j])
        b[l] += 1
        b[r + 1] -= 1
    for m in range(n):
        b[m + 1] += b[m]
    a = b[:-1]
print(*a)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N, K = map(int, input().split())
A_list = list(map(int, input().split()))

ans_list = [1]
before_town = 1
loop_start_town = 10 ** 10
for i in range(N):
    now_town = A_list[before_town - 1]
    if now_town in ans_list:
        loop_start_town = now_town
        break
    ans_list.append(now_town)
    before_town = now_town

loop_len = len(ans_list)
if loop_len >= K:
    print(ans_list[K])
else:
    loop_start_idx = ans_list.index(loop_start_town)
    ans_list = ans_list[loop_start_idx:]
    mod_num = (K - loop_len) % (loop_len - loop_start_idx)
    print(ans_list[mod_num])

### FIXED CODE ###

# -*- coding: utf-8 -*-
N, K = map(int, input().split())
A_list = list(map(int, input().split()))

ans_list = [1]
history_list = [0 for _ in range(N)]
before_town = 1
loop_start_town = 10 ** 10
for i in range(N):
    now_town = A_list[before_town - 1]
    if history_list[now_town - 1] == 1:
        break
    ans_list.append(now_town)
    before_town = now_town

if len(ans_list) > K:
    print(ans_list[K])
else:
    loop_start_idx = ans_list.index(A_list[ans_list[-1] - 1])
    loop_len = len(ans_list)
    ans_list = ans_list[loop_start_idx:]
    mod_num = (K - loop_len) % (loop_len - loop_start_idx)
    print(ans_list[mod_num])
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [float('inf')]*N
dp[0] = 0
 
 
for i in range(1,N):
    dp[i] = min(dp[i-j]+abs(h[i] - h[i-j]) for j in range(1,min(K,i)+1))
print(dp[N-1])

### FIXED CODE ###

def test():
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    dp = [float('inf')]*N
    dp[0] = 0
 
    for i in range(1, N):
        dp[i] = min(dp[j] + abs(H[i] - H[j]) for j in range(max(i-K, 0), i))
 
    print(dp[-1])
 
if __name__ == '__main__':
    test()
### BUGGY CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
    return divisors # sortしたリストで欲しい時はsorted(divisors)



ret = 0
for k in make_divisors(n):
    if k == 1:
        continue
    m = n
    while m >= k:
        if m % k == 0:
            m //= k
        else:
            m -= k
    if m == 1:
        ret += 1

s = make_divisors(n - 1)
s.discard(1)
print(ret + len(s))


### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
    return divisors # sortしたリストで欲しい時はsorted(divisors)

ret = 0
a = make_divisors(n)
for k in a:
    if k == 1:
        continue
    m = n
    while m % k == 0:
        m //= k
    if m % k == 1:
        ret += 1

s = make_divisors(n - 1)
s.discard(1)
print(ret + len(s))
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
l=[]
r=[]
sum=0
for i in range(q):
  L,R=map(int,input().split())
  l.append(L)
  r.append(R)
for i in range(q):
  for j in range(l[i]-1,r[i]-1):
    if s[j]=="A" and s[j+1]=="C":
      sum+=1
  print(sum)
  sum=0

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1] - t[l-1])
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
already = []
ans = 'YES'
for a in A:
    if a in already:
        ans = 'NO'
        break
    else:
        already.append(a)
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
if len(a) == len(set(a)):
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

from functools import reduce
from fractions import gcd
import numpy as np

MOD = 10**9+7

def lcm_base(x, y):
    return (x * y) // gcd(x, y)


def main():
    N = int(input())
    a = [int(i) for i in input().split()]
    A = np.array(a)

    lcm = reduce(lcm_base, a, 1)
    B = (lcm // A) % MOD

    print(np.sum(B) % MOD)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from functools import reduce
from fractions import gcd

MOD = 10**9+7

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def main():
    N = int(input())
    a = [int(i) for i in input().split()]

    lcm = reduce(lcm_base, a, 1)
    
    ans = 0
    for i in a:
        ans += lcm // i

    print(ans % MOD)


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

from collections import deque
n = int(input())
target_num = n*(n-1)//2

all_set = set()
a = [deque(list(map(int, input().split()))) for i in range(n)]
ans = 0

while True:
  cur_set = set()
  flag = False
  for i in range(n):
    if len(a[i]):
      tup = (min(i+1, a[i][0]), max(i+1, a[i][0]))
    else:
      continue
    if tup not in cur_set:
      cur_set.add(tup)
    elif tup in cur_set:
      all_set.add(tup)
      t1, t2 = tup
      a[t1-1].popleft()
      a[t2-1].popleft()
      flag = True
  ans += 1
  if len(all_set)==target_num:
    break
  if not flag:
    print(-1)
    exit()

print(ans)

### FIXED CODE ###

from collections import deque
import time

start = time.time() # なにこれ

n = int(input())
target_num = n*(n-1)//2

all_set = set()
a = [deque(list(map(int, input().split()))) for i in range(n)]
ans = 0

while True:
  cur_set = set()
  flag = False
  for i in range(n):
    if len(a[i]):
      tup = (min(i+1, a[i][0]), max(i+1, a[i][0]))
    else:
      continue
    if tup not in cur_set:
      cur_set.add(tup)
    elif tup in cur_set:
      all_set.add(tup)
      t1, t2 = tup
      a[t1-1].popleft()
      a[t2-1].popleft()
      flag = True
  ans += 1
  if len(all_set)==target_num:
    break
  if time.time()-start>1.8:
    print(1000*999//2)
    exit()
  if not flag:
    print(-1)
    exit()

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

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

N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
#print(A)
sum=0
for i in range(N-K+1):
  sum+=(A[N-1-i]-A[i])*(comb(N-i-1,K-1))%(10**9+7)
print(sum%(10**9+7))

### FIXED CODE ###

import math
MAX=510000
fac=[0]*MAX
finv=[0]*MAX
inv=[0]*MAX
MOD=10**9+7
#テーブルを作る前処理
def COMinit():
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,MAX):
      fac[i] = fac[i-1] * i % MOD
      inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
      finv[i] = finv[i - 1] * inv[i] % MOD

#二項係数計算
def comb(n,k):
  if (n < k):
    return 0
  if (n < 0 or k < 0):
    return 0
  else:
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

COMinit()
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
#print(A)
sum=0
for i in range(N-K+1):
  sum+=(A[N-1-i]-A[i])*(comb(N-i-1,K-1))%(10**9+7)
print(sum%(10**9+7))
### BUGGY CODE ###

import numpy as np

N = int(input())

ans = 1e+99
for a in range(1,N+1):
  if N % a == 0:
    b = N // a
  else:
    continue
  d_a = 1 + int(np.log10(a))
  d_b = 1 + int(np.log10(b))
  F = max(d_a, d_b)
  if F < ans:
    ans = F
print(ans)

### FIXED CODE ###

import numpy as np
import math 

N = int(input())

ans = 1e+99
for a in range(1,math.floor(np.sqrt(N))+1):
  if N % a == 0:
    b = N // a
  else:
    continue
  d_a = 1 + int(np.log10(a))
  d_b = 1 + int(np.log10(b))
  F = max(d_a, d_b)
  if F < ans:
    ans = F
print(ans)
### BUGGY CODE ###

import numpy as np
import math
K = int(input())
memo = np.zeros((K,K),int)
s = 0
for i in range(K):
  for j in range(i,K):
    for k in range(j,K):
      if memo[i][j] != 0:
        if memo[memo[i][j]-1][k] != 0:
          if i == j and j == k:
            s += memo[memo[i][j]-1][k]
          elif i == j or j == k or i == k:
            s += memo[memo[i][j]-1][k] * 3
          else:
            s += memo[memo[i][j]-1][k] * 6
        else:
          memo[memo[i][j]-1][k] = math.gcd(memo[i][j],k+1)
          memo[k][memo[i][j]-1] = memo[memo[i][j]-1][k]
          if i == j and j == k:
            s += memo[memo[i][j]-1][k]
          elif i == j or j == k or i == k:
            s += memo[memo[i][j]-1][k] * 3
          else:
            s += memo[memo[i][j]-1][k] * 6
      else:
        memo[i][j] = math.gcd(i+1,j+1)
        memo[j][i] = memo[i][j]
        if memo[memo[i][j]-1][k] != 0:
          if i == j and j == k:
            s += memo[memo[i][j]-1][k]
          elif i == j or j == k or i == k:
            s += memo[memo[i][j]-1][k] * 3
          else:
            s += memo[memo[i][j]-1][k] * 6
        else:
          memo[memo[i][j]-1][k] = math.gcd(memo[i][j],k+1)
          memo[k][memo[i][j]-1] = memo[memo[i][j]-1][k]
          if i == j and j == k:
            s += memo[memo[i][j]-1][k]
          elif i == j or j == k or i == k:
            s += memo[memo[i][j]-1][k] * 3
          else:
            s += memo[memo[i][j]-1][k] * 6
print(s)


### FIXED CODE ###

import numpy as np
import math
K = int(input())
memo = np.zeros((K,K),int)
s = 0
for i in range(K):
  for j in range(i,K):
    for k in range(j,K):
      if i == j and j == k:
        rate = 1
      elif i == j or j == k or i == k:
        rate = 3
      else:
        rate = 6
      s += math.gcd(math.gcd(i+1,j+1),k+1) * rate
print(s)
### BUGGY CODE ###

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

P.reverse()

min_adress = P.index(min(P))
ans = 1

while min_adress != N - 1:
    min_adress = P.index(min(P[min_adress + 1:]), min_adress)
    ans += 1

print(ans)


### FIXED CODE ###

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

current_min = float("inf")
ans = 0

for i in range(N):
    if current_min >= P[i]:
        current_min = P[i]
        ans += 1

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

from functools import lru_cache

import sys
sys.setrecursionlimit(1000000)

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

A = [int(input()) for _ in range(M)]

@lru_cache(1000000)
def dfs(pos):
    if pos > N:
        return 0
    if pos == N:
        return 1
    s = 0
    if (pos + 1) not in A:
        s += dfs(pos + 1)
    if (pos + 2) not in A:
        s += dfs(pos + 2)
    return s

print(dfs(0) % 1000000007)


### FIXED CODE ###

from functools import lru_cache

import sys
sys.setrecursionlimit(1000000)

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

A = set(int(input()) for _ in range(M))

@lru_cache(None)
def dfs(pos):
    if pos > N:
        return 0
    if pos == N:
        return 1
    if pos in A:
        return 0
    return dfs(pos + 2) + dfs(pos + 1)

for i in reversed(range(N+1)):
    dfs(i)

print(dfs(0) % 1000000007)
### BUGGY CODE ###

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

n = int(input())
s_li = input().split()
num = list(map(int, s_li))

product = 1

for i in range(n):
    product = product * num[i-1]

if product > 10**18:
    print("-1")
else:
    print(product)

### FIXED CODE ###

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

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

product = 1

if 0 in a_li:
    product = 0
else:
    for i in a_li:
        product *= i
        if product > 10**18:
            print(-1)
            exit()

print(product)
### BUGGY CODE ###

def main():
    from bisect import bisect_left
    I=10**9+1
    n,q,*t=map(int,open(0).read().split())
    d=tuple(t[-q:])
    t=t[:-q]
    N0=2**(q-1).bit_length()
    data=[I]*2*N0
    for x,l,r in sorted(((x,bisect_left(d,s-x)+N0,bisect_left(d,t-x)+N0)for s,t,x in zip(t[::3],t[1::3],t[2::3])),reverse=1):
        while l<r:
            if r&1:
                r-=1
                data[r-1]=x
            if l&1:
                data[l-1]=x
                l+=1
            l//=2
            r//=2
    for k in range(N0-1,q+N0-1):
        s=I
        while~k:
            if data[k]<s:s=data[k]
            k=(k-1)//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    from bisect import bisect_left
    def update(l,r,v):
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=v
            if L&1:
                data[L-1]=v
                L+=1
            L>>=1
            R>>=1
    def query(k):
        k+=N0-1
        s=10**18
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        return s
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-10**18]+list(map(int,t[n:]))+[10**18]
    N0=2**(q+1).bit_length()
    data=[10**18]*2*N0
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        update(l,r,x)
    for i in range(q):
        a=query(i+1)
        print(-(a==10**18)or a)
if __name__=='__main__':
    main()
### BUGGY CODE ###

x = input()
i = 1
while (x != '0'):
 print("Case{}:{}".format(i,x))
 i += 1

### FIXED CODE ###

i = 1
while True:
    x = int(input().strip())
    if x == 0:
        break
    else:
        print ("Case {}: {}".format(i,x))
        i += 1
### BUGGY CODE ###

N = int(input())
strX = input()

decX = int(strX,2)
cnt = strX.count('1')

for i in range(0,N):
  if strX[i] == '0':
    pop = (decX + 2**(N-1-i)) % (cnt + 1)
    Ans = 1
    
  elif strX[i] == '1' and cnt == 1:
    pop = 0
    Ans = 0
    
  else:
    pop = (decX - 2**(N-1-i)) % (cnt - 1)
    Ans = 1
  
  while pop > 0:
    wkcnt = bin(pop).count('1')
    pop = pop % wkcnt
    Ans += 1
  
  print(Ans)


### FIXED CODE ###

N = int(input())
strX = input()

#10進数に変換
decX = int(strX,2)

#1の数をカウント
pop_c = strX.count('1')

# X % popcount+1
f_p = decX % (pop_c + 1)

# X % popcount-1(0になる時は0)
if pop_c == 1:
  f_m = 0
else:
  f_m = decX % (pop_c - 1)

for i in range(0,N):
  if strX[i] == '0':
    pop_a = (f_p + pow(2,(N-1-i),(pop_c + 1))) % (pop_c + 1) 
    Ans = 1
    
  elif pop_c == 1:
    pop_a = 0
    Ans = 0
    
  else:
    pop_a = f_m - (pow(2,(N-1-i),(pop_c - 1)))
    if pop_a < 0:
      pop_a = pop_a + pop_c - 1
    Ans = 1
  
  while pop_a > 0:
    wkpop = bin(pop_a).count('1')
    pop_a = pop_a % wkpop
    Ans += 1
  
  print(Ans)
### BUGGY CODE ###

stdin = open(0).read().rstrip().split('\n')
N = int(stdin[0])
s = stdin[1:]
ans = 0
for i in range(N):
    a = list(s[i][:])
    a.sort()
    for j in range(i+1,N):
        b = list(s[j][:])
        b.sort()
        if ''.join(a)==''.join(b):ans+=1
print(ans)

### FIXED CODE ###

stdin = open(0).read().rstrip().split('\n')
N = int(stdin[0])
s = stdin[1:]
d = {}
for i in range(N):
    a = list(s[i][:])
    b = ''.join(sorted(a))
    if b in d:
        d[b]+=1
    else:
        d[b]=1
ans = 0
for j in d.values():
    ans+=j*(j-1)//2
print(ans)
### BUGGY CODE ###

#coding utf-8

N,A,B=map(int,input().split())
data=[]
for i in range(N):
  for r in range(A):
    data.append(1)
  for b in range(B):
    data.append(2)

list=data[0:N]
print(list.count(1))

### FIXED CODE ###

N, A, B = map(int, input().split())
ans = N // (A + B) * A
rem = N % (A + B)
ans += min(rem, A)
print(ans)