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

import sys

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


def dfs(G, v, p, C):
    """G: graph, v: vertex, p: parent"""
    # Loop for each child
    for c in G[v]:
        if c == p:
            continue
        dfs(G, c, v, C)
        C[v].extend(C[c])


def main():
    N, Q = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)

    # Give all children for each parent
    C = [[i] for i in range(N)]
    dfs(G, 0, -1, C)

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

    print(" ".join(map(str, point)))


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

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


def dfs(G, v, p, point):
    """G: graph, v: vertex, p: parent"""
    # Loop for each child
    for c in G[v]:
        if c == p:
            continue
        point[c] += point[v]
        dfs(G, c, v, point)


def main():
    N, Q = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)

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

    dfs(G, 0, -1, point)
    print(" ".join(map(str, point)))


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

import heapq

def main():
    n, m = map(int, input().split())
    a = [list(map(int, input().split())) for i in range(n)]
    a_t = list(zip(*a))
    a_s = set(a_t[0])
    cnt = 0
    h = [(l[1]*-1) for l in a if l[0] == 1]
    heapq.heapify(h)
    if 1 in a_s:
        cnt += heapq.heappop(h)
    for i in range(2, m+1):
        if i in a_s:
            p = [(l[1]*-1) for l in a if l[0] == i]
            for j in p:
                heapq.heappush(h, j)
        if h !=[]:
            cnt += heapq.heappop(h)
    print(-1*cnt)   
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import heapq

def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(n)]
    a_t = list(zip(*ab))
    AB = [[] for _ in range(m+1)]
    for a, b in zip(*a_t):
        if a <= m:
            AB[a].append(b*-1)
    # print(AB)
    cnt = 0
    h = [] 
    heapq.heapify(h)
    for i in AB:
        for j in i:
            heapq.heappush(h, j)
            # print('h', h)
        if h:
            cnt += heapq.heappop(h)
    print(-1*cnt)   

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

K=int(input())

D=7
for i in range(10000000):
    if D%K==0:
        print(i+1)
        break
#    print(D)
    D=D*10+7
    D%=K
else:
    print(-1)


### FIXED CODE ###

K=int(input())

D=7
for i in range(1000000):
    if D%K==0:
        print(i+1)
        break
#    print(D)
    D=D*10+7
    D%=K
else:
    print(-1)
### BUGGY CODE ###

a, b = map(int, input().split())
n = 1
L = []
for i in range(min(a, b), max(a, b)+1):
  n = n * i
if n == 0:
  print('Zero')
elif n > 0:
  print('Positive')
else:
  print('Negative')

### FIXED CODE ###

a, b = map(int, input().split())
n = 1
L = []
if a * b < 0:
  print('Zero')
elif a + b > 0 or (a - b) % 2 == 1:
  print('Positive')
else:
  print('Negative')
### BUGGY CODE ###

from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    x_sum = sum(a) // 2
    x = [0] * n
    for i in range(n):
        tmp = x_sum
        idx = (i + 1) % n
        for _ in range((n - 1) // 2):
            tmp -= a[idx]
            idx += 2
            idx %= n
        x[i] = 2 * tmp
    print(*x)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


### FIXED CODE ###

from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    x_sum = sum(a) // 2
    x = [0] * n
    tmp = x_sum
    idx = 1
    for _ in range((n - 1) // 2):
        tmp -= a[idx]
        idx += 2
        idx %= n
    x[0] = 2 * tmp
    for i in range(n - 1):
        x[i + 1] = 2 * (a[i] - x[i] // 2)
    print(*x)


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

n, m = map(int, input().split())
alist = list(map(int, input().split()))

for i in range(m):
    num = max(alist)
    num = num >> 1

    alist.remove(max(alist))
    alist.append(num)

print(sum(alist))


### FIXED CODE ###

import heapq


n, m = map(int, input().split())
alist = list(map(int, input().split()))
alist = list(map(lambda x: -x, alist))
heapq.heapify(alist)

for i in range(m):
    minus_max = alist[0]
    heapq.heapreplace(alist, ((-1)*minus_max >> 1)*(-1))

print(-1*sum(alist))
### BUGGY CODE ###

n,m=map(int,input().split())
A=sorted([int(i) for i in input().split()])

for i in range(m):
  A[-1]=A[-1]//2
  A.sort()
  
ans=sum(A)
print(ans)


### FIXED CODE ###

import heapq

n,m=map(int,input().split())
A=[int(i)*(-1) for i in input().split()]
heapq.heapify(A)

for i in range(m):
  M=heapq.heappop(A)
  heapq.heappush(A,-((-M)//2))
  
ans=-sum(A)
print(ans)
### BUGGY CODE ###

count = int(input())
nlist = []
for i in range(count):
    a = int(input())
    nlist.append(a)
mlist = tuple(nlist)
biggest = max(mlist)
nlist.remove(biggest)

for i in range(count):
    if mlist[i] == biggest:
        print(max(nlist))
    else:
        print(biggest)


### FIXED CODE ###

count = int(input())
nlist = []
for i in range(count):
    a = int(input())
    nlist.append(a)
mlist = tuple(nlist)
biggest = max(mlist)
nlist.remove(biggest)
c = max(nlist)

for i in range(count):
    if mlist[i] == biggest:
        print(c)
    else:
        print(biggest)
### BUGGY CODE ###

N, M = map(int,input().split())
side = [[]for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    side[a-1].append([b-1,c])
node = [-float('inf')]*N
node[0] = 0
queue = [0]
nque = []
for i in range(N+5):
    while queue:
        q = queue.pop(-1)
        for a,c in side[q]:
            if node[a] < node[q]+c:
                node[a] = node[q]+c
                nque.append(a)
    queue = nque[:]
    nque = []
ans = node[-1]
for i in range(N+5):
    while queue:
        q = queue.pop(-1)
        for a,c in side[q]:
            if node[a] < node[q]+c:
                node[a] = node[q]+c
                nque.append(a)
    queue = nque[:]
    nque = []
if node[-1] == ans:
    print(ans)
else:
    print('inf')

### FIXED CODE ###

N,M = map(int,input().split())
gra = [[]for i in range(N)]
p = [[0]+[-float("inf")]*(N-1) for i in range(N*2+1)]
p[0][0] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    gra[a-1].append([b-1,c])
for i in range(N*2):
    for j in range(N):
        for b,c in gra[j]:
            p[i+1][b] = max(p[i+1][b],p[i][j]+c,p[i][b])
print(["inf",p[N][-1]][p[N][-1] == p[-1][-1]])
### BUGGY CODE ###

n, k, q = map(int, input().split())
scores = [k] * n
for _ in range(q):
    i = int(input()) - 1
    for j in range(n):
        if i == j:
            continue
        scores[j] -= 1
for s in scores:
    print('Yes' if s > 0 else 'No')

### FIXED CODE ###

n, k, q = map(int, input().split())
scores = {i: 0 for i in range(n)}
for _ in range(q):
    i = int(input()) - 1
    scores[i] += 1
for i in range(n):
    print('Yes' if k - (q - scores[i]) > 0 else 'No')
### BUGGY CODE ###

n=int(input())
s=0
for i in range(1,n+1):
    s+=(i-1)%i
print(s)

### FIXED CODE ###

n=int(input())
print((n-1)*n//2)
### BUGGY CODE ###

import math

def ABC159D(a):
    if a<2:
        return 0
    else:
        return math.factorial(a)//math.factorial(a-2)//2


n=int(input())
a=list(map(int,input().split()))
d1=dict()
for i in a:
    if i not in d1:
        d1[i]=1
    else:
        d1[i] += 1
#print(d1)
d2={i:ABC159D(j) for i,j in d1.items()}
d3={i:ABC159D(j-1)-d2[i] for i,j in d1.items()}
#print(d2,d3)
p=sum(d2.values())
for i in a:
    print(p+d3[i])
    


### FIXED CODE ###

import math

def mycounter(d,i):
    if i in d:
        d[i]+=1
    else:
        d[i]=1
    return d
    
def ABC159D(a):
    if a<2:
        return 0
    else:
        return math.factorial(a)//math.factorial(a-2)//2

n=int(input())
a=list(map(int,input().split()))
d = dict()
for i in a:
    d=mycounter(d,i)
p=sum([ABC159D(i) for i in d.values()])
for i in a:
    print(p-d[i]+1)
### BUGGY CODE ###

n,k=map(int,input().split())
a=0
while k<=n+1:
    mi=0
    ma=0
    for t in range(k):
        mi+=t
        ma+=(n-t)
    a+=(ma-mi+1)
    k+=1
print(a)

### FIXED CODE ###

n,k=map(int,input().split())
d=0
for i in range(k,n+2):
    b=i*(i-1)/2
    c=i*(2*n-i+1)/2
    d+=(c-b+1)
print(int(d)%(10**9+7))
### BUGGY CODE ###

from math import log

def exp(n, base):
    e = int(log(n, base))
    if base ** (e + 1) <= n:
        return e + 1
    else:
        return e

def min_withdraw(n):
    if n < 6:
        return n
    else:
        exp_nine = exp(n, 9)
        exp_six = exp(n, 6)
        return 1 + min(min_withdraw(n - (6 ** exp_six)), min_withdraw(n - (9 ** exp_nine)))
    
    
if __name__ == '__main__':
    n = int(input())
    print(min_withdraw(n))

### FIXED CODE ###

from math import log
 
def exp(n, base):
    e = int(log(n, base))
    if base ** (e + 1) <= n:
        return e + 1
    else:
        return e
 
def min_withdraw(n):
    if n < 6:
        return n
    else:
        exp_nine = exp(n, 9)
        exp_six = exp(n, 6)
        return 1 + min(min_withdraw(n - (6 ** exp_six)), min_withdraw(n - (9 ** exp_nine)))
    
    
if __name__ == '__main__':
    n = int(input())
    print(min_withdraw(n))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0
flag = True
r = set(list(range(n)))
while True:
    if not r:
        print(ans)
        break
    tmp = 0
    for j in r:
        if not a[j]:
            tmp += 1
            continue
        c = a[j][0]
        if c == "-":
            continue
        if j + 1 == a[c-1][0]:
            a[j][0] = "-"
            a[c-1][0] = "-"
    for j in range(n):
        if a[j]:
            if a[j][0] == "-":
                a[j] = a[j][1:]
                flag = False
                if not a[j]:
                    r.remove(j)
    if flag:
        print(-1)
        break
    else:
        ans += 1


### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0
r = set(list(range(n)))
N = n*(n-1) // 2 + 1
for _ in range(N):
    if not r:
        print(_)
        break
    ne = set()
    flag = True
    for j in r:
        if not a[j]:
            continue
        c = a[j][0]
        if c == "-":
            continue
        if j + 1 == a[c-1][0]:
            a[j][0] = "-"
            a[c-1][0] = "-"
            ne.add(j)
            ne.add(c-1)
    for j in list(ne):
        if a[j]:
            if a[j][0] == "-":
                a[j].pop(0)
                flag = False
                if not a[j]:
                    ne.remove(j)
    if flag:
        print(-1)
        break
    else:
        r = ne
### BUGGY CODE ###

import math

def comb(a, b):
    return math.factorial(a) // (math.factorial(b) * math.factorial(a - b))

n, m = map(int, input().split())
ans = 1
p = 0
for _ in range(m):
    a = int(input())
    cnt = 0
    if a == p:
        print(0)
        exit()
    s = a - 1 - p
    for i in range(s // 2 + 1):
        cnt += comb(s - i, i)
    p = a + 1
    ans = (ans * cnt) % (10 ** 9 + 7)
s = n - p
cnt = 0
for i in range(s // 2 + 1):
    cnt += comb(s - i, i)
ans = (ans * cnt) % (10 ** 9 + 7)
print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
dp = [0] * (n + 1)
safe = [True] * (n + 1)
mod = 10 ** 9 + 7
for _ in range(m):
    a = int(input())
    safe[a] = False
dp[0] = 1
if safe[1] is True:
    dp[1] = 1 
for i in range(2, n+1):
    if safe[i-1] is True:
        dp[i] += dp[i-1]
    if safe[i-2] is True:
        dp[i] += dp[i-2]
    dp[i] %= mod
print(dp[n])
### BUGGY CODE ###

N = int(input())

sum = 0

for j in range(1,N+1):
    k = int(N/j)
    sum += int((1+k)*k/2*j)

print(sum)

### FIXED CODE ###

N = int(input())

sum = 0

for j in range(1,N+1):
    k = N//j
    sum += (1+k)*k*j//2
print(sum)
### BUGGY CODE ###

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

ans = -float('inf')
for i in range(n):
    score = []
    check = [0] * n
    now = i
    cycle = 0
    for _ in range(k):
        go = p[now] - 1
        if check[go] == 1:
            break
        now = go
        if len(score) == 0:
            score.append(c[now])
        else:
            score.append(score[-1] + c[now])
        check[now] = 1
        cycle += 1

    t = k // cycle
    m = k % cycle

    sum_cycle = score[-1]
    if m == 0:
        ans = max(sum_cycle * t, max(score), ans)
    else:
        ans = max(sum_cycle * t + max(score[:m]), max(score), ans)

    #print('sum_cycle:', sum_cycle, 'cycle:', cycle, 'ans:', ans)
    #print(i+1, score)
print(ans)

### FIXED CODE ###

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

ans = -float('inf')
for i in range(n):
    score = []
    check = [0] * n
    now = i
    cycle = 0
    for _ in range(k):
        go = p[now] - 1
        if check[go] == 1:
            break
        now = go
        if len(score) == 0:
            score.append(c[now])
        else:
            score.append(score[-1] + c[now])
        check[now] = 1
        cycle += 1

    t = k // cycle
    m = k % cycle

    sum_cycle = score[-1]
    if m == 0:
        ans = max(sum_cycle * t, sum_cycle * (t - 1) + max(score), max(score), ans)
    else:
        ans = max(sum_cycle * t + max(score[:m]), sum_cycle * (t - 1) + max(score), max(score), ans)

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

N, P = list(map(int, input().split()))
if N == 1:
    print(P)
    exit()
elif P == 1:
    print("1")
    exit()

ans = 1
tmp = P

for i in range(2, P):
    po = pow(i, N)
    while tmp % po == 0:
        tmp = tmp // po
        ans = ans * i
        # print(i, tmp, ans)

    if tmp < po:
        break

print(ans)


### FIXED CODE ###

N, P = list(map(int, input().split()))
if N == 1:
    print(P)
    exit()
elif P == 1:
    print("1")
    exit()

ans = 1
tmp = P

for i in range(2, int(pow(P, 1 / N)) + 1):
    po = pow(i, N)
    while tmp % po == 0:
        tmp = tmp // po
        ans = ans * i
        # print(i, tmp, ans)

    if tmp < po:
        break

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

N = int(input())
S = input()
L = list(S)
first = [L.index(str(i)) if str(i) in S else None for i in range(10)]
con = 0

for n in range(0,1000):
  c = str(n)
  c = "0" * (3 - len(c)) + c
  if first[int(c[0])] != None and first[int(c[0])] < N - 1:
    i = first[int(c[0])]
    for j in range(i + 1,len(S) - 1):
        if S[j] == c[1] and c[2] in S[j + 1:]:
          con += 1
          break

print(con)


### FIXED CODE ###

N = int(input())
S = input()
con = 0

for i in range(10):
  if str(i) in S:
    p = S.index(str(i))
    S2 = S[p + 1:]
    for j in range(10):
      if str(j) in S2:
        q = S2.index(str(j))
        S3 = S2[q + 1:]
        for k in range(10):
          if str(k) in S3:
            con += 1

print(con)
### BUGGY CODE ###

N = int(input())
S = input()
minimum = 300000

for i in range(N):
    leftWestNum = S[:i].count('W')
    rightEstNum = S[i+1:N].count('E')
    tmpMin = leftWestNum + rightEstNum
    if tmpMin < minimum:
        minimum = tmpMin
    
    
print(minimum)


### FIXED CODE ###

N = int(input())
S = input()
#------------------------------
#########タイムオーバー########
#------------------------------
# minimum = 300000
# for i in range(N):
    # leftWestNum = S[:i].count('W')
    # rightEstNum = S[i+1:N].count('E')
    # tmpMin = leftWestNum + rightEstNum
    # if tmpMin < minimum:
        # minimum = tmpMin
# print(minimum)

minimum = 3000000
numEast = [0] * (N+1)
numWest = [0] * (N+1)
for i in range(N):
    if S[i] == 'E':
        numEast[i+1] = numEast[i] + 1
        numWest[i+1] = numWest[i]
    else:
        numEast[i+1] = numEast[i]
        numWest[i+1] = numWest[i] + 1

for i in range(N):
    tmpMin = numWest[i] + (numEast[N]-numEast[i+1])
    if tmpMin < minimum:
        minimum = tmpMin

print(minimum)
### BUGGY CODE ###

N,K=map(int,input().split())
a=sorted(list(map(int,input().split())),reverse=True)
F=sorted(list(map(int,input().split())))

def judge(t):
    global a,F,N,K
    K_t=K
    for i in range(N):
        target=t//F[i]
        if a[i]<=target:
            continue
        if K_t>=a[i]-target:#引けるかどうか
            K_t-=a[i]-target
        else:
            return False
    return True

t_max=10**12+1 #絶対True
t_min=-1 #絶対False
while t_max>t_min+1:
    t_mid=(t_max+t_min)//2
    if judge(t_mid):
        t_max=t_mid
    else:
        t_min=t_mid
print(t_max)

### FIXED CODE ###

N,K=map(int,input().split())
a=sorted(list(map(int,input().split())),reverse=True)
F=sorted(list(map(int,input().split())))
import numpy as np
a=np.array(a)
F=np.array(F)

t_max=a[0]*F[-1] #絶対True
t_min=-1 #絶対False
while t_max>t_min+1:
    t_mid=(t_max+t_min)//2
    K_temp=np.sum(np.maximum(a-t_mid//F,0))
    if K_temp<=K:
        t_max=t_mid
    else:
        t_min=t_mid
print(t_max)
### BUGGY CODE ###

N = int(raw_input())
A = []
for n in xrange(N):
  A.append(map(int, raw_input().split(' ')))

def route(f, t, now, arrived):
  if now == t:
    return 0
  min_dist = float('inf')
  for k in xrange(N):
    if k in arrived or (k == t and len(arrived) == 1):
      continue
    min_dist = min(route(f, t, k, arrived|set([k]))+A[now][k], min_dist)
  return min_dist

answer = 0
for i in xrange(N):
  for j in xrange(i):
    L = route(i, j, i, set([i]))
    if A[i][j] == L:
      pass
    elif A[i][j] > L:
      print -1
      exit()
    else:
      answer += A[i][j]

print answer

### FIXED CODE ###

N = int(raw_input())
A = []
for n in xrange(N):
  A.append(map(int, raw_input().split(' ')))
  A[n][n] = 1000000001

answer = 0
for i in range(N):
  Ai = A[i]
  for j in range(i):
    Aij = Ai[j]
    L = min(map(sum, zip(Ai, A[j])))
    if Aij < L:
      answer += Aij
    else:
      if Aij > L:
        print -1
        exit()
print answer
### BUGGY CODE ###

from collections import deque
n = int(input())
l = deque()

for _ in range (n):
    cmd = input().split(' ')
    
    if cmd[0]=='insert':
        val = int(cmd[1])
        l.appendleft(val)
                
    if cmd[0]=='delete':
        val = int(cmd[1])
        try:l.remove(val)
        except :pass
    
    if cmd[0]=='deleteFirst':
        l.popleft()
       
    if cmd[0]=='deleteLast':
        l.pop()
print(*l)



### FIXED CODE ###

from collections import deque
n = int(input())
l = deque()
for _ in range (n):
    cmd = input().split(' ')
    if cmd[0]=='insert':
        l.appendleft(cmd[1])  
    if cmd[0]=='delete':
        try:l.remove(cmd[1])
        except :pass
    if cmd[0]=='deleteFirst':
        l.popleft()
    if cmd[0]=='deleteLast':
        l.pop()
print(*l)
### BUGGY CODE ###

n=int(input());a=input().split();d={}
for i in a:
  if int(i)==a.count(i):
    continue
  if i not in d:
    d[i]=min(a.count(i),abs(int(i)-a.count(i)))
print(sum([i for i in d.values()]))

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
dict={}
count=0
for i in a:
  if i not in dict:
    dict[i] = 1
    continue
  dict[i] += 1
for i,j in dict.items():
  if i > j:
    count += j
  elif i < j:
    count += j-i
print(count)
### BUGGY CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
counter = 0
#for i in range(len(A)) :
#    A[i] = A[i] % M
for j in range(len(A)) :
    P = 0
    for k in range(j,N) :
        P += A[k]
        if P % M == 0 :
            counter += 1
print(counter)



### FIXED CODE ###

from collections import Counter

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

cums = [0]
for a in A:
    cums.append((cums[-1] + a) % M)

ctr = Counter(cums)

ans = 0
for v in ctr.values():
    ans += v*(v-1)//2
print(ans)
### BUGGY CODE ###

from itertools import islice


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

for i in range(N - 1, 0, -1):
    p = A[i]
    for j in islice(A, i * 2, N, i):
        p ^= j
        B[i] = p ^ A[i]

B[0] = A[0] ^ (sum(B) % 2)


S = []
for i, b in enumerate(B):
    if b == 1:
        S.append(str(i + 1))

if len(S) == 0:
    print(0)
else:
    print(len(S))
    print(' '.join(S))


### FIXED CODE ###

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

for i in range(N - 1, -1, -1):
    p = A[i]
    j = i + 1
    while i < N:
        if B[i]:
            p ^= 1
        i += j
    B[j - 1] = p

S = [i + 1 for i, c in enumerate(B) if c]

print(len(S))
print(*S)
### BUGGY CODE ###

N, C = map(int, input().split())
dic = []
L = 0
for i in range(N):
  s, t, c = map(int, input().split())
  dic += [(c-1,s,t)]
  if 2*t+1>L:
    L = 2*t+1

sm = [0]*L
for c in range(C):
  tt = [0]*(L)
  for i in range(N):
    if dic[i][0]==c:
      tt[dic[i][1]*2-1] += 1
      tt[dic[i][2]*2] -= 1
  for i in range(1,L):
    tt[i] += tt[i-1]
  for i in range(L):
    if tt[i]>0:
      sm[i] += 1
print(max(sm))

### FIXED CODE ###

N, C = map(int, input().split())
dic = []
for i in range(N):
  s, t, c = map(int, input().split())
  dic += [(c-1,s,t)]

L = 2*100000+1
sm = [0]*L
for c in range(C):
  tt = [0]*(L)
  for i in range(N):
    if dic[i][0]==c:
      tt[dic[i][1]*2-1] += 1
      tt[dic[i][2]*2] -= 1
  for i in range(1,L):
    tt[i] += tt[i-1]
  for i in range(L):
    if tt[i]>0:
      sm[i] += 1
print(max(sm))
### BUGGY CODE ###

import sys

def main():
    input = sys.stdin.readline
    mod = 998244353
    
    a, b, c, d = map(int, input().split())
    dp = dict()
    for i in range(a, c+1):
        for j in range(b, d+1):
            if i == a and j == b:
                dp[(i, j)] = 1
                continue
            if j == b:
                dp[(i, j)] = dp[(i-1, j)]*j%mod
                continue
            if i == a:
                dp[(i, j)] = dp[(i, j-1)]*i%mod
                continue
            dp[(i, j)] = (dp[(i-1, j)]*j+dp[(i, j-1)]*i+mod-dp[(i-1, j-1)]*(i-1)*(j-1))%mod
    print(dp[(c, d)])        
            

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    mod = 998244353
    
    a, b, c, d = map(int, input().split())
    dp = [[0]*(d+1) for _ in range(c+1)]
    for i in range(a, c+1):
        for j in range(b, d+1):
            if i == a and j == b:
                dp[i][j] = 1
                continue
            if j == b:
                dp[i][j] = dp[i-1][j]*j%mod
                continue
            if i == a:
                dp[i][j] = dp[i][j-1]*i%mod
                continue
            dp[i][j] = (dp[i-1][j]*j+dp[i][j-1]*i+mod-dp[i-1][j-1]*(i-1)*(j-1)%mod)%mod
    print(dp[c][d])        
            

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

N, b, r = map(int, input().split())

s = 0
t = 0
for i in range(10**100):
    t = t+b+r
    s += 1
    if N<=t:
        if (t-N)<r:
            print(s*b)
            exit()
        else:
            print((s-1)*b+N-t+b+r)
            exit()

### FIXED CODE ###

N, b, r = map(int, input().split())

t = N//(b+r)
s = N%(b+r)

if s>=b:
    print((t+1)*b)
else:
    print(t*b + s)