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

from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra

N=int(input())
R=[]
C=[]
W=[]

for i in range(N-1):
    u, v, w = [int(i) for i in input().split()]
    R.append(u-1)
    C.append(v-1)
    W.append(w)
    R.append(v-1)
    C.append(u-1)
    W.append(w)
g = coo_matrix((W, (R, C)), shape=(N, N)).tocsr()
d = dijkstra(g, indices=0 ,directed=1, unweighted=False)
for i in d:
    print(int(i) % 2)



### FIXED CODE ###

from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()
N = int(input())
for i in range(N-1):
    u, v, w = [int(i) for i in input().split()]
    g.add_edge(u-1, v-1, w)
    g.add_edge(v-1, u-1, w)

d = Dijkstra(g, 0)

ans = []
for i in range(N):
    if d.dist[i] % 2 == 0 :
        ans.append(0)
    else:
        ans.append(1)

if sum(ans)==0:
    ans[-1] = 1

for i in range(N):
    print(ans[i])
### BUGGY CODE ###

def solve():
    n=int(input())
    x=list(map(int,input().split()))
    list1=[]
    def ap1(num):
        list1.append(num)
    for i in range(n):
        ap1([x[i],i+1])
    str1= lambda val: val[0]
    list1.sort(key=str1)
    numa=[]
    numb=[]
    for i in range(n):
        num3=list1[i][1]
        numa+=[num3]*(num3-1)
        numb+=[num3]*(n-num3)
    count1=0
    count2=0
    count3=0
    ans=[]
    ansnum=0
    def apans(num):
        ans.append(num)
    for i in range(n*n):
        yn=0
        if count1!=n:
            if i==list1[count1][0]-1:
                apans(list1[count1][1])
                count1+=1
                yn=1
        if yn==0:
            if count2!=len(numa):
                apans(numa[count2])
                count2+=1
            elif count3!=len(numb):
                apans(numb[count3])
                count3+=1
            else:
                if i!=n*n-1:
                    ansnum=1
                    break
    list2=[]
    def countnum(num):
        return list2.count(num)
    for i in range(n):
        list2=ans[:list1[i][0]]
        if countnum(list1[i][1])!=list1[i][1]:
            ansnum=1
            break
    if ansnum==1:
        print("No")
    else:
        print("Yes")
        print(*ans)
solve()


### FIXED CODE ###

def solve():
    n=int(input())
    x=list(map(int,input().split()))
    list1=[]
    def ap1(num):
        list1.append(num)
    for i in range(n):
        ap1([x[i],i+1])
    str1= lambda val: val[0]
    list1.sort(key=str1)
    numa=[]
    numb=[]
    for i in range(n):
        num3=list1[i][1]
        numa+=[num3]*(num3-1)
        numb+=[num3]*(n-num3)
    count1=0
    count2=0
    count3=0
    ans=[]
    ansnum=0
    def countnum(num):
        return ans.count(num)
    def apans(num):
        ans.append(num)
    for i in range(n*n):
        yn=0
        if count1!=n:
            if i==list1[count1][0]-1:
                if countnum(list1[count1][1])!=list1[count1][1]-1:
                    ansnum=1
                    break
                apans(list1[count1][1])
                count1+=1
                yn=1
        if yn==0:
            if count2!=len(numa):
                apans(numa[count2])
                count2+=1
            elif count3!=len(numb):
                apans(numb[count3])
                count3+=1
            else:
                if i!=n*n-1:
                    ansnum=1
                    break
    if ansnum==1:
        print("No")
    else:
        print("Yes")
        print(*ans)
solve()
### BUGGY CODE ###

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

h, n = map(int, input().split())
ab = set([])
for _ in range(n):
    ab.add(tuple(map(int,input().split())))
l = h + max(a for a, _ in ab)

#DP[i] = i までの魔法でモンスターの体力を減らすため消耗する魔力の最小値
dp = [10**8+1] * l
dp[0] = 0

for i in range(l):  #最大L回繰り返せばよい
    for a, b in ab:
        dp[i] = min(dp[i-a] + b, dp[i])
print(min(dp[h:]))


### FIXED CODE ###

import numpy as np
H,N=map(int, input().split())
A = [None]*N
B = [None]*N
for i in range(N):
  A[i],B[i]=map(int,input().split())
dp=[10**8]*(H+1)
A = np.array(A)
B = np.array(B)
dp = np.array(dp)
dp[0]=0
for i in range(1,H+1):
  x=np.amin((dp[np.maximum(0,i-A)]+B))
  dp[i]=min(x,dp[i])
print(dp[-1])
### BUGGY CODE ###

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

l1 = [float("inf")]*n
l2 = [float("inf")]*n

cnt1 = 0
i = 0
while cnt1 < k and i<n:
    if s[i] == "o":
        l1[i] = cnt1 + 1
        i += c + 1
        cnt1 += 1
    else:
        i += 1

cnt2 = k
i = n-1
while cnt2 != 0 and i>=0:
    if s[i] == "o":
        l2[i] = cnt2
        i -= c + 1
        cnt2 -= 1
    else:
        i -= 1

for i in range(1,k+1):
    if l1.index(i) == l2.index(i):
        print(l1.index(i) + 1)

### FIXED CODE ###

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

l2 = [float("inf")]*n

cnt2 = k
i = n-1
while cnt2 != 0:
    if s[i] == "o":
        l2[i] = cnt2
        i -= c + 1
        cnt2 -= 1
    else:
        i -= 1

cnt1 = 0
i = 0
while cnt1 < k:
    if s[i] == "o":
        if l2[i] == cnt1 + 1:
            print(i+1)
        i += c + 1
        cnt1 += 1
    else:
        i += 1
### BUGGY CODE ###

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

dp = [0] * N
for i in range(1, N):
    dp[i] = dp[i-1] + abs(h[i]-h[i-1])
    for j in range(2, K+1):
        if i-j < 0:
            break
        dp[i] = min(dp[i], dp[i-j] + abs(h[i]-h[i-j]))

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


### FIXED CODE ###

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

dp = [0] * N
for i in range(1, N):
    dp[i] = dp[i-1] + abs(h[i]-h[i-1])
    for j in range(2, K+1):
        if i-j < 0:
            break
        dp[i] = min(dp[i], dp[i-j] + abs(h[i]-h[i-j]))

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

n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
mod = 1000000007
dp = [1] + [1] * m
for i in range(n):
    newdp = [1] + [0] * m
    for j in range(m):
        if s[i] == t[j]:
            newdp[j + 1] = (newdp[j] + dp[j + 1]) % mod
        else:
            newdp[j + 1] = (newdp[j] + dp[j + 1] - dp[j] + mod) % mod
    dp = newdp
print(dp[-1])

### FIXED CODE ###

n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
mod = 1000000007
dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for i in range(0, len(s) + 1):
    for j in range(0, len(t) + 1):
        ret = 0
        if i == 0:
            ret = 1
        elif j == 0:
            ret = 1
        else:
            ret = (dp[i][j - 1] + dp[i - 1][j]) % mod
            if s[i - 1] != t[j - 1]:
                ret = (ret + mod - dp[i - 1][j - 1]) % mod
        dp[i][j] = ret
print(dp[len(s)][len(t)])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def solve():
    N = int(input())
    #(i,j) -> E[i-1][j-2], i < j
    E = [[0 for j in range(N+1)] for i in range(N+1)]
    E[1][2] = 1
    cl = {1}
    for j in range(3,N+1):
        for i in range(j-1,0,-1):
            if all(E[i][k] != E[k][j] for k in range(i+1,j)):
                E[i][j] = 1
            else:
                cl_ = cl - set(E[i][k] for k in range(i+1,j) if E[i][k] == E[k][j]) - {0}
                if cl_:
                    E[i][j] = min(cl_)
                else:
                    E[i][j] = max(cl)+1
                    cl.add(E[i][j])
                    
    
    res = '\n'.join(' '.join(map(str,e[i+2:])) for i, e in enumerate(E[1:]))
    return str(res)

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

### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np

def solve():
    N = int(input())
    E = np.array([[0,1],[0,0]])
    for i in range((N-1).bit_length()-1):
        E_ = E+(E>0)
        E = np.vstack([np.hstack([E_,np.ones_like(E)]),np.hstack([np.zeros_like(E), E_])])
    res = '\n'.join(' '.join(map(str,e[i+1:N])) for i, e in enumerate(E[:N]))
    return str(res)

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

N = int(input())

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

min_a = 999999999999999
for i in range(1, len(a)):
    cal = abs(sum(a[:i]) - sum(a[i:]))
    if cal < min_a:
        min_a = cal
print(min_a)

### FIXED CODE ###

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

su = sum(a)
diff = 1e10
cc = 0

for i in range(len(a)-1):
    cc += a[i]
    diff = min(diff, abs(su-2*cc))
print(diff)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
BC=[]
for i in range(Q):
    BC.append(list(map(int,input().split())))
for i in BC:
    for j in range(N):
        if A[j]==i[0]:
            A[j]=i[1]
    print(sum(A))

### FIXED CODE ###

import collections
def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]
N=int(input())
A=list(map(int,input().split()))
goukei=sum(A)
Q=int(input())
BC=[]
for i in range(Q):
    BC.append(list(map(int,input().split())))
c = collections.Counter(A)
for i in BC:
    goukei+=c[i[0]]*(i[1]-i[0])
    c[i[1]]=c[i[0]]+c[i[1]]
    c[i[0]]=0
    print(goukei)
### BUGGY CODE ###

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

for i in range(N):
  A[i] -= i


ans = 0
for i in range(N):
  a = A[i]
  c = A[i+1:].count(-a - 2 * i)
  ans += c
  
print(ans)

### FIXED CODE ###

from collections import deque, Counter

N = int(input())

A = [
  int(j) - i  for i, j in enumerate(input().split())
]
cnt_A = Counter(A)

ans = 0
d = deque(A)
for i in range(N):
  a = d.popleft()
  #c = d.count(-a - 2 * i)
  c = cnt_A[-a - 2 * i]
  ans += c
print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())
cnt = [[1 for _ in range(W)] for _ in range(H)]
for h in range(H):
    ws = 0
    for w in range(W):
        if S[h][w] == "#":
            ws = 0
        else:
            cnt[h][w] += ws
            ws += 1
    ws = 0
    for w in range(W-1, -1, -1):
        if S[h][w] == "#":
            ws = 0
        else:
            cnt[h][w] += ws
            ws += 1

for w in range(W):
    hs = 0
    for h in range(H):
        if S[h][w] == "#":
            hs = 0
        else:
            cnt[h][w] += hs
            hs += 1
    hs = 0
    for h in range(H-1, -1, -1):
        if S[h][w] == "#":
            hs = 0
        else:
            cnt[h][w] += hs
            hs += 1
ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, cnt[h][w])
print(ans)



### FIXED CODE ###

H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())
cnt = [[1 for _ in range(W)] for _ in range(H)]
for h in range(H):
    ws = 0
    for w in range(W):
        if S[h][w] == "#":
            ws = 0
        else:
            cnt[h][w] += ws
            ws += 1
    ws = 0
    for w in range(W-1, -1, -1):
        if S[h][w] == "#":
            ws = 0
        else:
            cnt[h][w] += ws
            ws += 1

for w in range(W):
    hs = 0
    for h in range(H):
        if S[h][w] == "#":
            hs = 0
        else:
            cnt[h][w] += hs
            hs += 1
    hs = 0
    for h in range(H-1, -1, -1):
        if S[h][w] == "#":
            hs = 0
        else:
            cnt[h][w] += hs
            hs += 1
ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, cnt[h][w])
print(ans)
### BUGGY CODE ###

def main():
    a, b, k = map(int, input().split())
    k -= 1
    for i in range(a, b + 1):
        if min(abs(a - i), abs(b - i)) <= k:
            print(i)


if __name__ == '__main__':
    main()


### FIXED CODE ###


def main():
    a, b, k = map(int, input().split())
    r = set()
    for i1 in range(a, min(a + k, b)):
        r.add(i1)
    for i2 in range(max(a, b - k + 1), b + 1):
        r.add(i2)
    r = list(r)
    r.sort()
    for j in r:
        print(j)

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

import sys

def parent(i):
    return (i + 1) / 2 - 1

def left(i):
    return 2 * i + 1

def right(i):
    return 2 * i + 2

def sibling(i):
    if i % 2 == 0:
        return i - 1
    else:
        return i + 1

def insert(S, k):
    S.append(k)
    now = len(S) - 1
    while True:
        p = parent(now)
        if p < 0:
            break
        elif S[now] > S[p]:
            S[now], S[p] = S[p], S[now]
        else:
            now = p

def extract(S):
    print S[0]
    S[0] = S[-1]
    S.pop()

    now = 0
    while True:
        l, r = left(now), right(now)
        if l < len(S):
            if r >= len(S) or S[now] < S[l] and S[r] < S[l]:
                S[now], S[l] = S[l], S[now]
                now = l
            elif S[now] < S[r] and S[l] < S[r]:
                S[now], S[r] = S[r], S[now]
                now = r
        else:
            break

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    lines.pop()

    S = []
    for line in lines:
        if line[0] == "i":
            insert(S, int(line[7:]))
        else:
            extract(S)

### FIXED CODE ###

import sys

def insert(k):
    global S, last
    S[last] = k
    idx = last
    while True:
        p = (idx + 1) / 2 - 1
        if S[idx] <= S[p]:
            break
        else:
            S[idx], S[p] = S[p], S[idx]
            idx = p
    last += 1

def maxHeapify(i):
    global S, last
    l = 2 * i + 1
    r = 2 * i + 2

    if l < last and S[l] > S[i]:
        largest = l
    else:
        largest = i

    if r < last and S[r] > S[largest]:
        largest = r

    if largest != i:
        S[i], S[largest] = S[largest], S[i]
        maxHeapify(largest)

def extract():
    global S, last
    print S[0]
    last -= 1
    S[0], S[last] = S[last], 0
    maxHeapify(0)

lines = sys.stdin.readlines()
lines.pop()

S = [0] * 2000001
S[2000000] = 2000000000
last = 0
for line in lines:
    if line[0] == "i":
        insert(int(line[7:]))
    else:
        extract()
### BUGGY CODE ###

n = int(input())
p = 1
i = 1
while i < n or i == n:
  p = p*i
  i +=1
x = 10**9
print(p%(x+7))

### FIXED CODE ###

import math
n = int(input())
i = 1
j = math.factorial(n)
x = 10**9
print(j%(x+7))
### BUGGY CODE ###

S = input()
Q = int(input())
# Q_lst = []
# for i in range(Q):
#     Q_lst.append(input().split())
# for i in range(len(Q_lst)):
#     if Q_lst[i] == ["1"]: #T == 1
#         S = S[::-1]
#     elif Q_lst[i][1] == "1":    #T == 2, F == 1
#         S = Q_lst[i][2] + S
#     else:   #F == 2
#         S = S + Q_lst[i][2]
reverse = 1
for i in range(Q):
    a = input().split()
    if a == ["1"]:
        reverse *= -1
    elif a[1] == "1":
        if reverse == 1:
            S = a[2] + S
        else:
            S = S + a[2]
    else:
        if reverse == 1:
            S = S + a[2]
        else:
            S = a[2] + S
if reverse == -1:
    S = S[::-1]
print(S)

### FIXED CODE ###

S = input()
Q = int(input())
reverse = 1
head = ""
tail = ""
for i in range(Q):
    a = input().split()
    if a[0] == "1":
        reverse *= -1
    elif a[1] == "1":
        if reverse == 1:
            head += a[2]
        else:
            tail += a[2]
    else:
        if reverse == 1:
            tail += a[2]
        else:
            head += a[2]
# for i in range(Q):
#     a = input().split()
#     if a[0] == "1":
#         reverse *= -1
#     elif a[1] == "1":
#         if reverse == 1:
#             S = a[2] + S
#         else:
#             S = S + a[2]
#     else:
#         if reverse == 1:
#             S = S + a[2]
#         else:
#             S = a[2] + S
S = head[::-1] + S + tail
if reverse == -1:
    S = S[::-1]
print(S)
### BUGGY CODE ###

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

dp = {}
dp[0] = 0
dp[1] = abs(h[0] - h[1])

for i in range(2, N):
    tm = []
    for j in range(1, K+1):
        if i-j<0:
            break
        tm.append(dp[i-j] + abs(h[i-j] - h[i]))
    dp[i] = min(tm)

print(dp[N-1])

### FIXED CODE ###

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

dp = {}
dp[0] = 0
dp[1] = abs(h[0] - h[1])

for i in range(2, N):
    tm = []
    for j in range(1, min(K+1, i+1)):
        tm.append(dp[i-j] + abs(h[i-j] - h[i]))
    dp[i] = min(tm)

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

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

import math
mod = 10**9 +7
N = int(input())
X = list(map(int, input().split()))

ans=0
for i in range(1,N):
    ans = (ans*i + (X[-1]-X[i-1])*math.factorial(i-1)) %mod

print(ans)

### FIXED CODE ###

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

mod = 10**9 +7
N = int(input())
X = list(map(int, input().split()))

factorial=[1]
for i in range(1,N):
    factorial.append(factorial[-1] *i %mod)

ans=0
for i in range(1,N):
    ans = (ans*i + (X[-1]-X[i-1])*factorial[i-1]) %mod

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

#!/usr/bin/env python3
N = int(input())

print(0, flush=True)
w1 = input()
if w1 == 'Vacant':
    exit()

l, r = 0, N - 1
while r - l > 1:
    m = (l + r) // 2
    print(m, flush=True)
    w2 = input()
    if w2 == 'Vacant':
        break
    if w1 == w2:
        l, r = (l, m) if (m - l) & 1 else (m + 1, r)
    else:
        l, r = (m + 1, r) if (m - l) & 1 else (l, m)
    w1 = w2
print(l, flush=True)
input()



### FIXED CODE ###

#!/usr/bin/env python3
N = int(input())

print(0, flush=True)
w0 = input()
if w0 == 'Vacant':
    exit()

l, r = 0, N
while True:
    m = (l + r) // 2
    print(m, flush=True)
    w1 = input()
    if w1 == 'Vacant':
        break
    if m % 2 == (w0 != w1):
        l = m
    else:
        r = m
### BUGGY CODE ###


N = int(input())
li = list(map(int, input().split()))
MOD_NUMBER = 10**9+7
ans = 0
for idx in range(len(li)-1):
    ans += li[idx] * sum(li[idx+1:])

print(ans % MOD_NUMBER)


### FIXED CODE ###


N = int(input())
li = list(map(int, input().split()))
MOD_NUMBER = 10**9+7
nizyo_list = [i**2 for i in li]
ans = (sum(li)**2-sum(nizyo_list))//2
print(ans % MOD_NUMBER)
### BUGGY CODE ###

from collections import deque
n = int(input())
A = []
for i in range(n):
    rs  = list(map(int, input().split()))
    rs = [r-1 for r in rs]
    A.append(deque(rs))

listed = [-1] *  n
cnt = 1
while True:
    matched = False
    for i in range(n):
        if listed[i] == -1 and len(A[i]) > 0:
            #i番目のqueueから最新を取り出す
            listed[i] = A[i].popleft() 
    # tmp = []
    for i in range(n):
        aite = listed[i]
        # すでにその日試合していたらout
        if listed[i] == -1:continue
        if i == listed[aite]:
            listed[i] = -1
            listed[aite] = -1
            matched = True
            # tmp.append((i,aite))
    # print(tmp)
    if not matched:
        print(-1)
        exit()
    if all([len(r) == 0 for r in A]):
        break
    cnt += 1
print(cnt)


### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict, deque
n = int(input())
X = 10000
INF = 1 << 50
edges = defaultdict(list)
edges_r = defaultdict(list)
def topological_sort(G):

    cnt_in = defaultdict(int)
    for k in G.keys():
        for v in G[k]:
            cnt_in[v] += 1
    # print(cnt_in)
    res = []
    # 入次数==0
    q = deque([i for i in list(G.keys()) if cnt_in[i]==0])
    while len(q) > 0:
        v = q.popleft()
        res.append(v)
        for next_v in G[v]:
            # 入次数を下げていく
            cnt_in[next_v] -= 1
            # 入次数が0に残ったところを次に追加
            if cnt_in[next_v] == 0:
                q.append(next_v)
    # トポソ不可能！
    if len(G) != len(res):
        print(-1)
        exit()
    return res

for i in range(n):
    r = list(map(int, input().split()))
    # 初期
    mn = min(i, r[0]-1)
    mx = max(i, r[0]-1)
    prev = mn * n + mx
    for e in r[1:]:
        e -= 1
        mn = min(i,e)
        mx = max(i,e)
        now = mn*n+mx
        edges[prev].append(now)
        edges_r[now].append(prev)
        prev = now
vs = topological_sort(edges)

# トポソの順番で経路長を入れていく
used = [0] * n**2
# for V in vs:
#     if used[V]: continue
#     used[V] = 1
#     q = deque([V])
#     while len(q) > 0:
#         v = q.popleft()
#         for u in edges[v]: 
#             if used[u] <= used[v]:
#                 q.append(u)
#                 used[u] = max(used[u], used[v] + 1)

for V in vs:
    if used[V]:continue
    used[V] = 1
    mx = 1
    for b in edges_r[V]:
        mx = max(mx, used[b]+1)
    used[V] = mx
# print(used)
print(max(used))
### BUGGY CODE ###

import sys
N, K = map(int, input().split())
h = [0] + list(map(int, input().split()))
dp = [0]*(N+1) # 足場iにたどり着くまでの最小コスト
for i in range(2,N+1):
  dp[i] = dp[i-1] + abs(h[i]-h[i-1])
  for j in range(1,K+1):
    if i-j > 0:
      dp[i] = min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
print(dp[-1])

### FIXED CODE ###

N, K = map(int,input().split())
h = list(map(int,input().split()))
dp = [-1]*N
 
def rec_dp(i,K,dp):
    minArray = []
    if i == 0:
        minArray = [0]
    for j in range(K):
        if i - (j+1) >= 0:
            stepMin = dp[i-(j+1)] + abs(h[i] - h[i-(j+1)])
            minArray.append(stepMin)
    return min(minArray)
 
for i in range(N):
    dp[i] = rec_dp(i,K,dp)
 
print(dp[N-1])
### BUGGY CODE ###

N, Q = map(int, input().split())
S = list(input())
ans_lst = []
# cumulative = [S[:i] for i in range(N)]
for i in range(Q):
    l, r = map(int, input().split())
    s = S[l-1:r]
    num = 0
    for j in range(len(s)-1):
        if "".join(s[j:j+2]) == "AC":
            num += 1
    ans_lst.append(num)

for ans in ans_lst:
    print(ans)


### FIXED CODE ###

N, Q = map(int, input().split())
S = list(input())
ans_lst = []
cum = []
tmp = 0
for i in range(1, N):
    if (S[i-1] == "A" and S[i] == "C"):
        tmp += 1
    cum.append(tmp)

# cum = [1 if (S[i] == "A" and S[i+1] == "C") else 0 for i in range(N-1)]
for i in range(Q):
    l, r = map(int, input().split())
    if l != 1:
        num = cum[r-2] - cum[l-2]
    else:
        num = cum[r-2]
    ans_lst.append(num)

for ans in ans_lst:
    print(ans)
### BUGGY CODE ###

k, s = map(int, input().split())
ans = []
for i in range(k+1):
    for j in range(k+1):
        for h in range(k+1):
            if i + j + h == s:
                ans.append([i, j, h])
print(len(ans))
                

### FIXED CODE ###

k, s = map(int, input().split())
cnt = 0
for i in range(k+1):
    for j in range(min(k+1,s-i+1)):
        h = s- i- j
        if 0<= h <= k:
            cnt += 1
print(cnt)
### BUGGY CODE ###

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

array = []

for t in range(10 ** 100):
    if len(array) >= n:
        break
    for p in range(a):
        array.append('blue')
    for q in range(b):
        array.append('red')

x = 0

for i in range(n):
    if array[i] == 'blue':
        x += 1

print(x)

### FIXED CODE ###

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

f = n // (a+b)
g = n % (a+b)

if g <= a:
    print(a * f + g)
    
else:
    print(a * (f+1))