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

from collections import deque
H, W = map(int, input().split())
grid = [list(input()) + [False] for _ in range(H)]
grid = grid + [[False for _ in range(W + 1)]]
d = ((1, 0), (-1, 0), (0, 1), (0, -1))


def bfs(q):
    res_q = deque()
    while len(q):
        x, y = q.popleft()
        for dx, dy in d:
            nx = x + dx
            ny = y + dy

            if grid[nx][ny] == '.':
                res_q.append((nx, ny))
                grid[nx][ny] = '#'
    return res_q


q = deque()
for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            q.append((i, j))

res = 0
while len(q):
    res += 1
    q = bfs(q)

print(res - 1)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]

# d = [[2001] * W for _ in range(H)]


def bfs(q):
    res_q = deque()
    while len(q):
        x, y = q.popleft()
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy

            if (0 <= nx < H) and (0 <= ny < W) and grid[nx][ny] != '#':
                res_q.append((nx, ny))
                grid[nx][ny] = '#'
    return res_q


q = deque()
for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            q.append((i, j))

res = 0
while len(q):
    res += 1
    q = bfs(q)

print(res - 1)
### BUGGY CODE ###

#!/usr/bin/python3

import sys
import resource
import bisect
from collections import defaultdict

sys.setrecursionlimit(1000000)
#resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))



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

nbs = defaultdict(list)

for i in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen = [ 0 for i in range(n) ]
dp = [ float('inf') for i in range(n) ]

def getmlen(cur, p, ctail):
    ca = a[cur]

    oidx = 0
    ov = 0
    
    idx = bisect.bisect_left(dp, ca)
    ov = dp[idx]

    ntail = ctail
    if ctail < idx:
        ntail = idx

    dp[idx] = ca
    mlen[cur] = ntail + 1
    
    for ch in nbs[cur]:
        if ch == p:
            continue

        getmlen(ch, cur, ntail)

    dp[idx] = ov
    return



getmlen(0, -1, 0)

for i in range(n):
    print(mlen[i])


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from bisect import bisect_left
 
N = int(input())
a = [int(i) for i in input().split()]
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  u, v = map(int, input().split())
  vec[u - 1].append(v - 1)
  vec[v - 1].append(u - 1)
 
lis = [a[0]]
ret = [0] * N
def dfs(cur, pre) :
  for nex in vec[cur] :
    if nex == pre : continue
    if a[nex] > lis[-1] :
      lis.append(a[nex])
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis.pop()
    else :
      pos = bisect_left(lis, a[nex])
      v = lis[pos]
      lis[pos] = a[nex]
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis[pos] = v
 
dfs(0, -1)
 
ret[0] = 1
for i in range(N) :
  print(ret[i])
### BUGGY CODE ###

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

c = 0

for i in a:
    if a.count(i) < i:
        a.remove(i)
        c += 1
    
for i in a:
    if a.count(i) > i:
        a.remove(i)
        c += 1
        
print(c)

### FIXED CODE ###

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

cnt = [0]*(10**5)
c = 0

for i in a:
    if i <= 10**5:
        cnt[i-1] += 1
    else:
        c += 1



for i in range(10**5):
    if cnt[i] > i+1:
        c += cnt[i] - (i+1)
    
    elif cnt[i] < i+1:
        c += cnt[i]

print(c)
### BUGGY CODE ###

n = int(input())
a = list(input().split())
b = []
for i in range(n):
  if i % 2 == 0:
    b.append(a[i])
  else:
    b.insert(0, a[i])
if n % 2 == 1:
  b.reverse()

print(" ".join(b))


### FIXED CODE ###

n = int(input())
a = list(input().split())
b = []

if n % 2 == 0:
  for i in range(n//2):
    b.append(a[n-1-i*2])
  for i in range(n//2):
    b.append(a[i*2])
else:
  for i in range(n//2+1):
    b.append(a[n-i*2-1])
  for i in range(n//2):
    b.append(a[i*2+1])

print(" ".join(b))
### BUGGY CODE ###

n,k=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
x=[l[i][0] for i in range(n)]
x.sort()
y=[l[i][1] for i in range(n)]
y.sort()
ans=[]
for i1 in range(n):
  for i2 in range(n):
    for i3 in range(n):
      for i4 in range(n):
        ct=0
        for i5 in range(n):
          if min(x[i1],x[i2])<=l[i5][0]<=max(x[i1],x[i2]) and min(y[i3],y[i4])<=l[i5][1]<=max(y[i3],y[i4]):ct+=1
        if ct>=k:
          ans.append(abs(x[i1]-x[i2])*abs(y[i3]-y[i4]))
print(min(ans))

### FIXED CODE ###

n,k=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
x=[l[i][0] for i in range(n)]
x.sort()
y=[l[i][1] for i in range(n)]
y.sort()
ans=[]
for i1 in range(n):
  for i2 in range(i1,n):
    for i3 in range(n):
      for i4 in range(i3,n):
        ct=0
        for i5 in range(n):
          if min(x[i1],x[i2])<=l[i5][0]<=max(x[i1],x[i2]) and min(y[i3],y[i4])<=l[i5][1]<=max(y[i3],y[i4]):ct+=1
        if ct>=k:
          ans.append(abs(x[i1]-x[i2])*abs(y[i3]-y[i4]))
print(min(ans))
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=-10**9

for i in range(1,n+1):
    m=i
    co=0
    an=0
    for j in range(n):
        m=p[m-1]
        co+=1
        if m==i:
            break      
    m=i
    x=[0 for j in range(co+1)]
    for j in range(co):
        m=p[m-1]
        x[j+1]=x[j]+c[m-1]
    
    if k<=co:
        ans=max(ans,max(x[j] for j in range(1,k+1)))
    else:
        if x[-1]<=0:
            ans=max(ans,max(x[j] for j in range(1,co+1)))
        else:
            f=max(0,k%co-1)
            an+=x[-1]*f
            s=k-f*co
            
            m=i
            for i in range(s):
                m=p[m-1]
                an+=c[m-1]
                ans=max(ans,an)
    
print(ans)
    



### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=-10**9

for i in range(1,n+1):
    m=i
    co=0
    an=0
    for j in range(n):
        m=p[m-1]
        co+=1
        if m==i:
            break      
    m=i
    x=[0 for j in range(2*co)]
    for j in range(2*co-1):
        m=p[m-1]
        x[j+1]=x[j]+c[m-1]
    
    if k<=co:
        ans=max(ans,max(x[j] for j in range(1,k+1)))
    else:
        if x[co]<=0:
            ans=max(ans,max(x[j] for j in range(1,co+1)))
        else:
            f=max(0,(k//co)-1)
            an+=x[co]*f
            s=k-f*co
            ans=max(ans,an+max(x[j] for j in range(1,s+1)))
            
            
            
            
print(ans)
### BUGGY CODE ###

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

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

### FIXED CODE ###

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

for num in range(A, min(B+1, A+K)):
    print(num)
for num in range(max(A+K, B-K+1), B+1):
    print(num)
### BUGGY CODE ###

import itertools

n = int(input())

a = list(map(int,input().split()))
ans = 0
for seq in itertools.combinations(range(n),2):
    if abs(seq[0]-seq[1]) == a[seq[0]] + a[seq[1]]:
        ans+=1
print(ans)

### FIXED CODE ###

from collections import Counter

n = int(input())

a = list(map(int,input().split()))
ans = 0
cc = Counter()

for i,val in enumerate(a):
    if i - val > 0:
        ans+=cc[i-val]
    cc[i+val]+=1

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

from math import ceil
from numpy import array
n, a, b = map(int, input().split())
h = array(sorted([int(input()) for i in range(n)]))

def enough(T):
    global h
    c = 0
    h2 = h - b * T
    for i, f in enumerate(h2 > 0):
        if not f:continue
        c += ceil(h2[i]/(a - b))
    if c <= T: return 1
    else: return 0

def bisearch():
    lo = 0
    hi = ceil(max(h)/b)
    while lo < hi:
        mid = (lo + hi) // 2
        midval = enough(mid)
        if midval < 1: lo = mid + 1
        else: hi = mid
    return lo

print(bisearch())

### FIXED CODE ###

from math import ceil
import numpy as np
n, a, b = map(int, input().split())
h = np.array(sorted([int(input()) for i in range(n)]))

def enough(T):
    global h
    h2 = h - b * T
    c = sum(np.ceil(h2[h2 > 0]/(a - b)))
    if c <= T: return 1
    else: return 0

def bisearch():
    lo = 0
    hi = ceil(max(h)/b)
    while lo < hi:
        mid = (lo + hi) // 2
        midval = enough(mid)
        if midval < 1: lo = mid + 1
        else: hi = mid
    return lo

print(bisearch())
### BUGGY CODE ###

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

S = [None] * N
T = [None] * N
X = [None] * N
for i in range(N):
    S[i], T[i], X[i] = map(int, input().split())

D = [None] * Q
for i in range(Q):
    D[i] = int(input())
    
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks, reverse=True)
#print(roadworks)

# Dは入力時点でソート済み
walkers = D[:]
ans = [-1] * len(walkers)
import bisect
for x, s, t in roadworks:
    left = bisect.bisect_left(walkers, s - x)
    right = bisect.bisect_left(walkers, t - x)
    #print(left, right)
    for i in range(left, right):
        #print(i)
        ans[i] = x
    
#print(walkers)
for a in ans:
    print(a)
    




    
    


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())

S = [None] * N
T = [None] * N
X = [None] * N
for i in range(N):
    S[i], T[i], X[i] = map(int, input().split())

D = [None] * Q
for i in range(Q):
    D[i] = int(input())
    
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks, key=lambda x: x[0])
#print(roadworks)

# Dは入力時点でソート済み
walkers = D[:]
ans = [-1] * Q
skip = [-1] * Q

import bisect
for x, s, t in roadworks:
    left = bisect.bisect_left(walkers, s - x)
    right = bisect.bisect_left(walkers, t - x)
    
    i = left
    while i < right:
        if skip[i] == -1:
            ans[i] = x
            skip[i] = right
            i += 1
        else:
            i = skip[i]

    
#print(walkers)
for a in ans:
    print(a)
### BUGGY CODE ###

def run():
  H, N = map(int, input().split())
  ab = [list(map(int, input().split())) for n in range(N)]
  dp = [float('inf')]*(H+1)
  for h in range(H+1):
    for n in range(N):
      a, b = ab[n]
      if h <= a:
        dp[h] = min(dp[h], b)
      else:
        dp[h] = min(dp[h], dp[h-a]+b)
  print(dp[-1])
    
if __name__ == '__main__':
    run()

### FIXED CODE ###

def run():
  H, N = map(int, input().split())
  ab_li = [tuple(map(int, input().split())) for n in range(N)]
  dp = [0]*(H+1)
  for i in range(1, H+1):
    new_li = []
    for n in range(N):
      a, b = ab_li[n]
      if a <= i:
        new_li.append(dp[i-a]+b)
      else:
        new_li.append(b)
    dp[i] = min(new_li)
  print(dp[-1])
  
if __name__ == '__main__':
  run()
### BUGGY CODE ###

n = int(input())
D = list(map(int,input().split()))
m = int(input())
T = list(map(int,input().split()))
cnt = 0
for t in T:
  if t in D:
    cnt += 1
    D.remove(t)
if cnt == m:
  print('YES')
else:
  print('NO')
  

### FIXED CODE ###

N=int(input())
D=list(map(int, input().split()))
M=int(input())
T=list(map(int, input().split()))
if N<M:
  print('NO')
  exit()
  
A={}
B={}
for i in D:
  if i not in A:
    A[i]=0
  A[i]+=1
  
for i in T:
  if i not in B:
    B[i]=0
  B[i]+=1
  
for i in B.keys():
  if not i in A:
    print('NO')
    exit()
  if A[i]<B[i]:
    print('NO')
    exit()
print('YES')
### BUGGY CODE ###

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


def Gcd(a, b):
    if b == 0:
        return a
    return Gcd(b, a%b)


def gcd_list(num_list):
    for i, num in enumerate(num_list):
        if i == 0:
            g = num
        else:
            g = Gcd(num, g)
    return g

GCD = 0
for i in range(N):
    others = A[:]
    others.pop(i)
    gcd = gcd_list(others)
    if gcd > GCD:
        GCD = gcd
print(GCD)

### FIXED CODE ###

from fractions import gcd

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

GCD1 = []
g = A[0]
for a in A:
    g = gcd(g, a)
    GCD1.append(g)

B = A[::-1]
g = B[0]
GCD2 = []
for b in B:
    g = gcd(g, b)
    GCD2.append(g)

ans = 1
for i in range(N):
    if i == 0:
        a = GCD2[N-2]
    elif i == N-1:
        a = GCD1[N-2]
    else:
        a = gcd(GCD1[i-1], GCD2[N-i-2])
    ans = max(ans, a)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env/ python3
N = int(input())
S = input()
#A, B, C = input().split()
#A, B, C, X, Y = map(int, input().split())

#N = int(input())
#H, W = map(int, input().split())
#S = [input() for _ in range(H)]
#print(A[0][0])

ans = 0
tmp = []
#first = []
#second = []
#third = []
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            if([S[i], S[j], S[k]] not in tmp):
                ans += 1
                tmp.append([S[i], S[j], S[k]])
            #if (S[i] not in first) or (S[j] not in second) or (S[k] not in third): ans += 1
            #if i not in first: first.append(S[i])
            #if j not in second: second.append(S[j])
            #if k not in third: third.append(S[k])                        
print(ans)

### FIXED CODE ###

#!/usr/bin/env/ python3
N = int(input())
S = input()
#A, B, C = input().split()
#A, B, C, X, Y = map(int, input().split())

#N = int(input())
#H, W = map(int, input().split())
#S = [input() for _ in range(H)]
#print(A[0][0])

ans = 0
for tmp_num in range(1000):
    tmp = str(tmp_num).zfill(3)
    digit = 0
    for i in range(N):
        if S[i] == tmp[digit]:
            digit += 1
            if digit == 3:
                ans += 1
                break
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# モジュールのインポート
import math


def get_input() -> int:
    """
    標準入力を取得する.

    Returns:\n
        int: 標準入力
    """
    N = int(input())

    return N


def has_z(n: int, x: int, y: int) -> bool:
    """
    条件を満たすzが存在するかどうか確認する.

    Args:\n
        n (int): 整数
        x (int): 整数
        y (int): 整数

    Returns:\n
        bool: 条件を満たすzが存在すれば真、しなければ偽
    """
    d = 4 * n - 3 * x**2 - 3 * y**2 - 2 * x * y
    if d < 0:
        return False
    z = (-(x + y) + math.sqrt(d)) / 2
    return (z.is_integer()) and (z >= 1)


def main(N: int) -> None:
    """
    メイン処理.

    Args:\n
        N (int): 整数（1 <= N <= 10^4）
    """
    for n in range(1, N + 1):
        ans = 0
        max_v = int(math.sqrt(n))
        for x in range(1, max_v + 1):
            for y in range(x, max_v + 1):
                if has_z(n, x, y):
                    ans += 1 + (x != y)
        print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N = get_input()

    # メイン処理
    main(N)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# モジュールのインポート
import math
import itertools

# 標準入力を取得
N = int(input())

# メイン処理


def g(x: int, y: int, z: int) -> int:
    return x**2 + y**2 + z**2 + x*y + y*z + z*x


l = [0 for n in range(N)]
for x, y, z in itertools.product(range(1, int(math.sqrt(N)) + 1), repeat=3):
    v = g(x, y, z)
    if v <= N:
        l[v - 1] += 1

# 結果出力
for ans in l:
    print(ans)
### BUGGY CODE ###

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

ab.sort(key=lambda x:x[1])
#print(ab)
split=[0,]

while len(ab)!=0:
  if ab[0][1]-split[-1]>0 and ab[0][0]-split[-1]<=0:
    ab.pop(0)
  else:
    split.append(ab[0][1]-1)
  
  #print(ab)
print(len(split)-1)

### FIXED CODE ###

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

ab.sort(key=lambda x:x[1])
#print(ab)
split=[0,]

#while len(ab)!=0:
for item in ab:
  if (item[1]-split[-1]>0 and item[0]-split[-1]<=0)!=True:
    split.append(item[1]-1)
  
  #print(ab)
print(len(split)-1)
### BUGGY CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))

cnt = {}
x = 0
y = K
while len(p[x:y]) == K:
    cnt[x] = sum(p[x:y])
    x += 1
    y += 1

for x, v in cnt.items():
    if v == max(cnt.values()):
        output = p[x:x+K]

ans = 0
for o in output:
    ans += sum(range(o+1))/o

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
cnt = [int(x) * 0.5 + 0.5 for x in input().split()]

add = [0]
for i in cnt:
    add.append(add[-1]+i)

ans = [add[i+K]-add[i] for i in range(N-K+1)]

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

N = int(input())
MOD = 998244353
def func(x):
    a = [23,26]
    out = 1
    for i in range(30):
        if not i in a:
            out = (out*x)%MOD
        x *= x
        x %= MOD
    return out

def func2(x):
    x = bin(x)[2:]
    out = 1
    b = 3
    for i in range(len(x)):
        if x[-1-i] == "1":
            out *= b
            out %= MOD
        b *= b
        b %= MOD
    return out

ans = 0
d = 1
b = 1
for i in range((N//2)):
    ans += d * b
    b *= 2
    b %= MOD
    ans %= MOD
    d = ((N-i)*d)%MOD
    d = (d*func(i+1))%MOD

print((func2(N)-ans*2)%MOD)

### FIXED CODE ###

N = int(input())
MOD = 998244353

list_size = 10000010

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)


def conv(n,r):
    if r == 0:
        return 1
    return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

ans = 0
for i in range((N//2)):
    ans += conv(N,i) * pow(2,i,MOD)
    ans %= MOD

print((pow(3,N,MOD)-ans*2)%MOD)
### BUGGY CODE ###

n = int(input())
ans = [0] * (n + 1)
for x in range(1, n):
    for y in range(1, n):
        for z in range(1, n):
            if x**2 + y**2 + z**2 + x*y + y*z + z*x <= n:
                ans[x**2 + y**2 + z**2 + x*y + y*z + z*x] += 1
print(*ans[1:], sep='\n')

### FIXED CODE ###

n = int(input())
ans = [0] * (n + 1)
for x in range(1, int(n**0.5) + 1):
    for y in range(1, int(n**0.5) + 1):
        for z in range(1, int(n**0.5) + 1):
            if x**2 + y**2 + z**2 + x*y + y*z + z*x <= n:
                ans[x**2 + y**2 + z**2 + x*y + y*z + z*x] += 1
print(*ans[1:], sep='\n')
### BUGGY CODE ###

from functools import reduce
import fractions
import sys
sys.setrecursionlimit(20000)

def lcm_base(a, b):
    return a * b / fractions.gcd(a, b)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N = int(input())
A = sorted(list(map(int, input().split())))
B = [0 for _ in range(N)]
mod = 10**9+7

ll = lcm_list(A)
ans = 0
for i in A:
    ans += ll // i
print(int(ans%mod))


### FIXED CODE ###

from fractions import gcd

def lcm(c,d):
    return c//gcd(c,d)*d
mod=10**9+7
n=int(input())
a=[int(i) for i in input().split()]
l=a[0]
for i in range(1,n):
    l=lcm(l,a[i])
ans=0
for i in range(n):
    ans+=l//a[i]
    #ans%=mod
print(ans%mod)
### BUGGY CODE ###

k=int(input())
if k%2==0 or k%5==0:
    print(-1)
    exit()
count=1
while True:
    if int('7'*count)%k==0:
        print(count)
        break
    count+=1


### FIXED CODE ###

k=int(input())
if k%2==0 or k%5==0:
    print(-1)
    exit()
a=0
for i in range(k):
    a=(a*10+7)%k
    if a==0:
        print(i+1)
        exit()
### BUGGY CODE ###

# coding: utf-8
X = int(input())

for i in range(1000000000):
    for j in range(-10000, 100000):
        if i ** 5 - j ** 5 == X:
            print(i, j)
            exit()

### FIXED CODE ###

# coding: utf-8
X = int(input())

for i in range(-118, 120):
    for j in range(-119, 119):
        if i ** 5 - j ** 5 == X:
            print(i, j)
            exit()
### BUGGY CODE ###

n,m=map(int,input().split())
data=[]
p=[0]*n
y=[[] for _ in range(n)]
q=[]
for i in range(m):
    p_i,y_i=map(int,input().split())
    data.append([p_i,y_i])
    p[p_i-1]+=1
    y[p_i-1].append(y_i)
    if p_i-1 not in q:
        q.append(p_i-1)
for i in q:
    y[i].sort()
for i in range(m):
    ans_p=data[i][0]
    ans_y=y[ans_p-1].index(data[i][1])+1
    ans_p=(str(ans_p)).zfill(6)
    ans_y=(str(ans_y)).zfill(6)
    print(ans_p+ans_y)

### FIXED CODE ###

from operator import itemgetter
n,m=map(int,input().split())
data=[]
for i in range(m):
    p_i,y_i=map(int,input().split())
    data.append([p_i,y_i,i])
data.sort()
data.append([n+1,0,m])
buf=1
for i in range(m):
    data[i].append(buf)
    if data[i][0]==data[i+1][0]:
        buf+=1
    else:
        buf=1
data.sort(key=itemgetter(2))
for i in range(m):
    ans_p=data[i][0]
    ans_y=data[i][3]
    ans_p=(str(ans_p)).zfill(6)
    ans_y=(str(ans_y)).zfill(6)
    print(ans_p+ans_y)
### BUGGY CODE ###

from collections import deque
import bisect
n = int(input())
d = []
for i in range(n):
    c, s = input().split()
    if c == "insert":
        d.insert(bisect.bisect_left(d, s), s)
    else:
        j = bisect.bisect_left(d, s)
        if j < len(d) and d[j] == s:
            print("yes")
        else:
            print("no")


### FIXED CODE ###

n = int(input())
d = {}
for i in range(n):
    c, s = input().split()
    if c == "insert":
        d[s] = 0
    else:
        if s in d:
            print("yes")
        else:
            print("no")
### BUGGY CODE ###

N = int(input())

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

ans = 0

for i in range(N):
    for j in range(i+1,N):
            tmp = a[i]*a[j]
            ans += tmp

m = 10**9 + 7

ans = ans % m

print(ans)

### FIXED CODE ###

N = int(input())

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

ans = 0
sum = 0

for i in range(N):
    sum += a[i]

for i in range(N-1):
    sum -= a[i]
    ans += a[i]*sum

m = 10**9 + 7

ans = ans % m

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

import sys
input = sys.stdin.readline

h, n = map(int, input().split())
a = []
b = []
for _ in range(n):
    ai,bi=map(int,input().split())
    a.append(ai)
    b.append(bi)

dp=[float("inf")]*(2*10000+1)
dp[0]=0

for i in range(h):
    for j in range(n):
        if (i+a[j])>2*10000:
            dp[2*10000]=min(dp[2*10000],dp[i]+b[j])
            continue
        dp[i+a[j]]=min(dp[i+a[j]],dp[i]+b[j])

ans=float("inf")
for j in range(h,2*10000+1):
    ans=min(ans,dp[j])
print(ans)
    
            


### FIXED CODE ###

h, n = map(int, input().split())
a = []
b = []
for _ in range(n):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)
 
dp = [float("inf")] * (2 * 10000 + 1)
dp[0] = 0
for i in range(h):
    for j in range(n):
        if (i + a[j]) > 2 * 10000:
            dp[2 * 10000] = min(dp[2 * 10000], dp[i] + b[j])
            continue
        dp[i + a[j]] = min(dp[i + a[j]], dp[i] + b[j])
 
ans = float('inf')
for j in range(h, 2 * 10000 + 1):
    ans = min(ans, dp[j])
print(ans)
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
pre_len = len(a) # 最初の長さ
ans = list()
for i in range(1,N+1):
	try:
		del a[:a.index(i)]
		ans.append(a[0])
	except ValueError :
		break

if len(ans) == 0:
	print(-1)
else:
	print(pre_len-len(ans))



### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
pre_len = len(a) # 最初の長さ
ans = list()

target = 1
for i in range(N):
	if a[i] == target:
		ans.append(i+1)
		target += 1


if len(ans) == 0:
	print(-1)
else:
	print(pre_len-len(ans))
### BUGGY CODE ###

h,n = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]
a,b = map(list,zip(*ab))

dp = [float("inf")]*(h+1)
dp[0] = 0

for i in range(h):
  for d,c in ab:
    hp = min(i+d,h)
    dp[hp] = min(dp[hp],dp[i]+c)

print(dp[h])

### FIXED CODE ###

h,n = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]

dp = [float("inf")]*(h+1)
dp[0] = 0

for i in range(h):
  for d,c in ab:
    hp = min(i+d,h)
    dp[hp] = min(dp[hp],dp[i]+c)

print(dp[-1])
### BUGGY CODE ###

N, A, B=map(int,input().split())
llist=[N]
for i in range(N-1):
    if i<A or (i>B+1) and A>1  :
       llist.append("blue")
    else :
        llist.append("red")
print(llist.count("blue"))

### FIXED CODE ###


n, a, b = map(int, input().split())
period = a+b
times = n//period
k = n%period
n =  a if k >a else k
print(times*a + n)