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

import sys
sys.setrecursionlimit(2*10**6)
input = sys.stdin.readline
N, M = map(int, input().split())
G = [[] for _ in [0]*N]

for _ in [0]*M:
    a, b, d = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append((b, d))
    G[b].append((a, -d))

X = [None]*N

def dfs(i, x=0):
    X[i] = x
    for j, d in G[i]:
        if X[j] is not None:
            if X[j] != x+d:
                print('No')
                exit()
            else:
                continue
        dfs(j, x+d)


for i in range(N):
    if X[i] is not None:
        continue
    dfs(i)
print('Yes')

### FIXED CODE ###

import sys
sys.setrecursionlimit(2*10**6)
input = sys.stdin.readline
N, M = map(int, input().split())
G = [[] for _ in [0]*N]
for _ in [0]*M:
    a, b, d = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append((b, d))
    G[b].append((a, -d))

X = [None]*N

def dfs(i, x=0):
    for j, d in G[i]:
        if X[j] is None:
            X[j] = x+d
            dfs(j, x+d)
        elif X[j] != x+d:
            print('No')
            exit()

for i in range(N):
    if X[i] is not None:
        continue
    X[i] = 0
    dfs(i)
print('Yes')
### BUGGY CODE ###

#!/usr/bin/env python3
h,w,k = map(int,input().split())
b =[]
for i in range(h):
    s = input()
    b.append(s)
# 縦の切り方を固定すれば、左から見て貪欲に考えることができる。
# どれかの切り方でK+1　以上1 のマスがあれば、そこで切る
if h == 1:
    print(math.ceil(s//k))
    exit()
# リストで現在のそれぞれのブロックの1の数を持つ

# 列の切断が入ったときに全て0に初期化
# bit 全探索は 2 ** h-1 存在する 
ans = h*w #INF
for i in range(2**(h-1)):
    cnt_white = [0] 
    # ループの中で宣言する
    ans_i = 0
    #前処理として、どこに切れ込みがあるかを見て、リストの構成
    for bit in range(h-1):
        if i >> bit & 1:
            cnt_white.append(0)
            ans_i += 1
    #print("i = ",i,cnt_white)
    c = 0
    while c < w:# 左から貪欲
        r_idx = 0
        for r in range(h):
            if b[r][c] == "1":#対応するブロックのcnt+=1
                cnt_white[r_idx] += 1
                #print("col = ",c,cnt_white,r_idx,ans_i)
            if i >> r & 1:#次にブロックが変わるのでidxを増やす
                r_idx += 1
        if max(cnt_white) >= k+1:
            # 戻らないといけない
            ans_i += 1
            c -= 1
            cnt_white = [0]*len(cnt_white)#初期化
            #print("initialize")
        c += 1
    ans = min(ans,ans_i)
print(ans)

    
 

        



### FIXED CODE ###

#!/usr/bin/env python3
h,w,k = map(int,input().split())
b =[]
for i in range(h):
    s = input()
    b.append(s)
# 縦の切り方を固定すれば、左から見て貪欲に考えることができる。
# どれかの切り方でK+1　以上1 のマスがあれば、そこで切る
if h == 1:
    print(math.ceil(s//k))
    exit()
# リストで現在のそれぞれのブロックの1の数を持つ

# 列の切断が入ったときに全て0に初期化
# bit 全探索は 2 ** h-1 存在する 
ans = h*w #INF
for i in range(2**(h-1)):
    cnt_white = [0] 
    # ループの中で宣言する
    ans_i = 0
    #前処理として、どこに切れ込みがあるかを見て、リストの構成
    for bit in range(h-1):
        if i >> bit & 1:
            cnt_white.append(0)
            ans_i += 1
    #print("i = ",i,cnt_white)
    c = 0
    last_div = 0
    while c < w:# 左から貪欲
        r_idx = 0
        
        for r in range(h):
            if b[r][c] == "1":#対応するブロックのcnt+=1
                cnt_white[r_idx] += 1
                #print("col = ",c,cnt_white,r_idx,ans_i)
            if i >> r & 1:#次にブロックが変わるのでidxを増やす
                r_idx += 1
        # 1行だけでmax(cnt_white) >= k+1になるときはその切り方では不可能
        if max(cnt_white) >= k+1:
            # 戻らないといけない
            ans_i += 1
            if c == last_div:
                ans_i = h*w  #INF
                break
            last_div = c
            c -= 1
            cnt_white = [0]*len(cnt_white)#初期化
            #print("initialize",last_div)
        c += 1
    ans = min(ans,ans_i)
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

dp = [10**10]*(n)
dp[0] = 0

for i in range(n):
    for j in range(1,k+1):
        if i+j <n:
            a = dp[i] + abs(h[i]-h[i+j])
            if a < dp[i+j]:
                dp[i+j] = a
        a = dp[i-2] + abs(h[i]-h[i-2])

print(dp[n-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
 
DP = [0]
for i in range(N-1):
    act = float("inf")
    for k in range(K):
        if i-k < 0 : continue
        act = min(DP[-1-k] + abs(h[i-k]-h[i+1]) , act)
    DP += [act]
 
print(DP[-1])
### BUGGY CODE ###

import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
from bisect import bisect_left, bisect_right
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
#print(a)
for i in range(n-1):
    for j in range(i+1, n):
        l = bisect_right(a, max(abs(a[i] - a[j]), a[j]))
        r = bisect_left(a, abs(a[i] + a[j]))
        #print(a[i], a[j], l, r)
        ans = ans - l + r
print(ans)

### FIXED CODE ###

import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
from bisect import bisect_left, bisect_right
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        ans = ans - j - 1 + bisect_left(a, abs(a[i] + a[j]))
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

h,w = MI()
a = [list(input()) for i in range(h)]
d = deque()
dx = [1,-1,0,0]
dy = [0,0,1,-1]
dist = [[-1]*w for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            d.append([i,j])
            dist[i][j] = 0
while d:
    s = d.popleft()
    x= s[0]
    y= s[1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= h or ny >= w:
            continue
        else:
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                ans = max(ans,dist[nx][ny])
                d.append([nx,ny])

print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

h,w = MI()
a = [list(input()) for i in range(h)]
d = deque()
dx = [1,-1,0,0]
dy = [0,0,1,-1]
dist = [[-1]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            d.append([i,j])
            dist[i][j] = 0
while d:
    s = d.popleft()
    x= s[0]
    y= s[1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= h or ny >= w:
            continue
        else:
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                d.append([nx,ny])
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans,dist[i][j])
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
max_a = max(A)
bit_count = {}
for i in range(len(format(max_a, "b"))):
    bit_count[i] = [0, 0]
# 辞書の初期化が完了
max_value = i
zero_ume = "0" + str(len(format(max_a, "b"))) + "b"
for i in range(N):
    for j in reversed(range(len(format(A[i], zero_ume)))):
        if format(A[i], zero_ume)[j] == "0":
            bit_count[max_value-j][0] += 1
        else:
            bit_count[max_value-j][1] += 1
mod = 10**9+7
ans = 0
for k, v in bit_count.items():
    ans += (2**k) * v[0] * v[1] % mod
print(ans % mod)


### FIXED CODE ###

mod = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))
ans = 0
loop_count = len(format(max(A), "b"))

for i in range(loop_count):
    tmp = 0
    for ai in A:
        if ((1 << i) & ai) > 0:
            tmp += 1
    ans += (1 << i) * tmp * (N - tmp) % mod
print(ans % mod)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
nowp = 0
cost = []
for i in range(N):
  cost.append(0)
  for j in range(N):
    if i != j:
      cost[i] += abs(nowp - A[j])
      nowp = A[j]
  cost[i] += abs(nowp)
  nowp = 0

for i in range(N):
  print('%d ' %cost[i])

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
nowp = 0
cost = []
allcost = 0
for i in range(N):
  allcost += abs(nowp - A[i])
  nowp = A[i]
allcost += abs(A[-1])

for i in range(N):
  cost.append(allcost)
  if i != 0 and i != N-1:
    cost[i] += abs(A[i-1]-A[i+1]) - abs(A[i-1]-A[i]) - abs(A[i]-A[i+1])
  elif i == 0:
    cost[i] += abs(0-A[i+1]) - abs(0-A[i]) - abs(A[i]-A[i+1])
  else:
    cost[i] -= abs(A[i-1]-A[i]) + abs(A[i]) - abs(A[i-1])
for i in range(N):
  print('%d ' %cost[i])
### BUGGY CODE ###

from functools import reduce

def gcd_base(x, y):
    if x >= y:
        while y != 0:
            x, y = y, x % y
        return x
    else:
        while x != 0:
            y, x = x, y % x
        return y

def gcd(numbers):
    return reduce(gcd_base, numbers)

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

for i in range(0, N):
    a = A.pop(0)
    GCD.append(gcd(A))
    A.append(a)

GCD.sort()

print(GCD[N-1])

### FIXED CODE ###

def gcd(x, y):
    if x >= y:
        while y != 0:
            x, y = y, x % y
        return x
    else:
        while x != 0:
            y, x = x, y % x
        return y

N = int(input())
A = list(map(int, input().split()))
L = [0, 0]
for ai in A:
    L.append(gcd(L[-1], ai))
 
R = [0, 0]
for ai in A[::-1]:
    R.append(gcd(R[-1], ai))
 
print(max(gcd(l, r) for l, r in zip(L, reversed(R))))
### BUGGY CODE ###

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

for i in range(1, N + 1):
    A[i] += A[i-1]
for i in range(1, M + 1):
    B[i] += B[i-1]

ans = 0
for a_cnt in range(N + 1):
    if A[a_cnt] > K:
        continue
    b_cnt = M
    while A[a_cnt] + B[b_cnt] > K:
        b_cnt -= 1
    ans = max(ans, a_cnt + b_cnt)

print(ans)

### FIXED CODE ###

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

for i in range(1, N + 1):
    A[i] += A[i-1]
for i in range(1, M + 1):
    B[i] += B[i-1]

ans = 0
b_cnt = M
for a_cnt in range(N + 1):
    if A[a_cnt] > K:
        continue
    while A[a_cnt] + B[b_cnt] > K:
        b_cnt -= 1
    ans = max(ans, a_cnt + b_cnt)

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

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

query = []
bridge = [1 for _ in range(N-1)]

for _ in range(M):
    a, b = map(int, input().split())
    query.append((a-1, b-1, b-a))

#街が左にある方を優先
query = sorted(query, key=lambda x: x[1])
#喧嘩する街が近い方を優先
# query = sorted(query, key=lambda x: x[2])

for i, j, _ in query:
    # print(i, j)
    # print(bridge[i:j])
    if sum(bridge[i:j]) == j-i:
        bridge[j-1] = 0
        # print("a", bridge[j-1])

# print(bridge)
print(N-1-sum(bridge))

### FIXED CODE ###

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

query = []
bridge = [1 for _ in range(N-1)]

for _ in range(M):
    a, b = map(int, input().split())
    query.append((a, b))

#街が左にある方を優先
query = sorted(query, key=lambda x: x[1])
#喧嘩する街が近い方を優先
# query = sorted(query, key=lambda x: x[2])

ans = 0
left = 0
for i, j in query:
    if left < i:
        left = j-1
        ans += 1

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

import itertools
n,k=map(int,input().split())
h=[int(input()) for i in range(n)]
com=list(itertools.combinations(h,k))
a=10**9
for i in range(len(com)):
    gap=abs(max(com[i])-min(com[i]))
    if gap<a:
        a=gap
print(a)

### FIXED CODE ###

n,k=map(int,input().split())
h=[int(input()) for i in range(n)]
h.sort()
#for i in range(n-k+1):
print(min(h[i+k-1]-h[i] for i in range(n-k+1)))
### BUGGY CODE ###

n = int(input())
arr = list(map(int,input().split()))
sum = 0
for i in range(n-1):
    for j in range(i+1,n):
        sum += arr[i]*arr[j]
print(sum%(10**9+7))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = a.copy()
for i in range(1,n):
    a[i] += a[i-1]
ans = 0
for i in range(n-1):
    ans += b[i] * (a[-1]-a[i])
mod = 10**9 + 7
print(ans % mod)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
for i,j in enumerate(a):
    if i%2 == 0:
        b.append(str(j))
    else:
        b.insert(0,str(j))
if j%2 != 0:
    b.reverse()
    print(' '.join(b))
else:
    print(' '.join(b))


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
ans1 = a[0::2]
ans2 = a[1::2]
if n%2 == 0:
    ans2.reverse()
    b.extend(ans2)
    b.extend(ans1)
    print(*b)
else:
    ans1.reverse()
    b.extend(ans1)
    b.extend(ans2)
    print(*b)
### BUGGY CODE ###

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

B = []

for i in range(N):
  B.append(A[i])
  B = B[::-1]
    
print(*B)

### FIXED CODE ###

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

from collections import deque

q = deque([])

for i in range(N):
  if i % 2:
    q.appendleft(A[i])
  else:
    q.append(A[i])
    
if N % 2:
  q = list(q)[::-1]
  
print(*q)
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split(" "))
H = [int(i) for i in input().split(" ")]

cost = np.array([0] + [10**9 for _ in range(N-1)])
for i in range(1,N):
    for j in range(min(i, K)):
        cost[i] = np.min([cost[i], cost[i-j-1] + abs(H[i-j-1] - H[i])])

print(cost[-1])

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split(" "))
H = np.array([int(i) for i in input().split(" ")])

cost = np.array([0] + [10**9 for _ in range(N-1)])
for i in range(1,N):
    cost[i] = np.min(cost[max(0,i-K):i] + np.abs(H[max(0,i-K):i] - H[i]))

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

n = int(input())
A = list(map(int,input().split()))
a = [format(i,'b') for i in A]
ans = 0
mod = 10**9+7
for i in range(60):
  cnt = 0
  for v in a:
    if len(v)<i+1:
      continue
    if v[-1-i]=='1':
      cnt += 1
  cnt = cnt*(n-cnt)%mod
  ans += cnt*(2**i)%mod
print(ans%mod)

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
a = [format(i,'b') for i in A]
ans = 0
mod = 10**9+7
for i in range(60):
  cnt = 0
  for v in a:
    if len(v)<i+1:
      continue
    if v[-1-i]=='1':
      cnt += 1
  cnt = cnt*(n-cnt)%mod
  ans += cnt*(2**i)%mod
print(ans%mod)
### BUGGY CODE ###

sizeI, sizeJ = map(int, input().split())
a = [input().strip() for _ in range(sizeI)]
 
rowVal = [[0 for _ in range(sizeJ)] for _ in range(sizeI)]
for i in range(sizeI):
    for j in range(sizeJ):
        if j == 0:
            rowVal[i][j] = 1 if a[i][j] == '.' else 0
        else:
            if a[i][j] == '.':
                rowVal[i][j] = rowVal[i][j - 1] + 1
            else:
                rowVal[i][j] = 0
    for j in range(sizeJ - 2, -1, -1):
        if rowVal[i][j] and rowVal[i][j + 1]:
            rowVal[i][j] = rowVal[i][j + 1]
 
colVal = [[0 for _ in range(sizeJ)] for _ in range(sizeI)]
for j in range(sizeJ):
    for i in range(sizeI):
        if i == 0:
            colVal[i][j] = 1 if a[i][j] == '.' else 0
        else:
            if a[i][j] == '.':
                colVal[i][j] = colVal[i - 1][j] + 1
            else:
                colVal[i][j] = 0
    for i in range(sizeI - 2, -1, -1):
        if colVal[i][j] and colVal[i + 1][j]:
            colVal[i][j] = colVal[i + 1][j]
 
ret = 0
for i in range(sizeI):
    for j in range(sizeJ):
        ret = max(ret, rowVal[i][j] + colVal[i][j] - 1)
print(ret)

### FIXED CODE ###

sizeI, sizeJ = map(int, input().split())
a = [input().strip() for _ in range(sizeI)]

rowVal = [[0 for _ in range(sizeJ)] for _ in range(sizeI)]
for i in range(sizeI):
    for j in range(sizeJ):
        if j == 0:
            rowVal[i][j] = 1 if a[i][j] == '.' else 0
        else:
            if a[i][j] == '.':
                rowVal[i][j] = rowVal[i][j - 1] + 1
            else:
                rowVal[i][j] = 0
    for j in range(sizeJ - 2, -1, -1):
        if rowVal[i][j] and rowVal[i][j + 1]:
            rowVal[i][j] = rowVal[i][j + 1]

colVal = [[0 for _ in range(sizeJ)] for _ in range(sizeI)]
for j in range(sizeJ):
    for i in range(sizeI):
        if i == 0:
            colVal[i][j] = 1 if a[i][j] == '.' else 0
        else:
            if a[i][j] == '.':
                colVal[i][j] = colVal[i - 1][j] + 1
            else:
                colVal[i][j] = 0
    for i in range(sizeI - 2, -1, -1):
        if colVal[i][j] and colVal[i + 1][j]:
            colVal[i][j] = colVal[i + 1][j]

ret = 0
for i in range(sizeI):
    for j in range(sizeJ):
        ret = max(ret, rowVal[i][j] + colVal[i][j] - 1)
print(ret)
### BUGGY CODE ###

h,w,k=map(int,input().split())
a=["0" for _ in range(h)]
c=1
for i in range(h):
  s=input()
  sh=[]
  nc=0
  if s=="."*w:continue
  
  for j in range(w):
    if s[j]=="#" and nc>0:c+=1
    elif s[j]=="#": nc+=1
    sh.append(str(c))
  a[i]=sh[:]
  c+=1

while "0" in a:
  for i in range(h):
    if a[i]=="0" and i==0:
      a[0]=a[1]
    elif a[i]=="0":
      a[i]=a[i-1]
      
for m in a:
  print(*m)

### FIXED CODE ###

h,w,k=map(int,input().split())
a=["x" for _ in range(h)]
c=1
if k==0:
  a=[1 for _ in range(w)]
  for i in range(h):
    print(*a)
  import sys
  sys.exit()

for i in range(h):
  s=input()
  sh=[]
  nc=0
  if s=="."*w:continue
  
  for j in range(w):
    if s[j]=="#" and nc>0:c+=1
    elif s[j]=="#": nc+=1
    sh.append(str(c))
  a[i]=sh[:]
  c+=1
  
if a[0]=="x":
  l=1
  while a[l]=="x":
    l+=1
  a[0]=a[l]
  
while "x" in a:
  for i in range(h):
    if a[i]=="x":
      l=i-1
      while a[l]=="x":
        l-=1
      a[i]=a[l]
      
for m in a:
  print(*m)
### BUGGY CODE ###

from sys import setrecursionlimit
setrecursionlimit(100000)
def rad_reach(b,h,dist,E,rad,ne):
	cnt = 1
	if dist < rad:
		for nxt in E[h]:
			if nxt == b or nxt == ne:
				continue
			cnt += rad_reach(h,nxt,dist+1,E,rad,ne) 
	return cnt
def solve():
	N,K = map(int,raw_input().split())
	pairs = []
	E = [[] for i in xrange(N)]
	for i in xrange(N-1):
		a,b = map(lambda x:int(x)-1,raw_input().split())
		E[a].append(b)
		E[b].append(a)
		pairs.append((a,b))
	ans = N
	rad = K/2
	if K % 2 == 0:
		for c in xrange(N):
			ans = min(ans,N-rad_reach(-1,c,0,E,rad,-1))
	else:
		for c1,c2 in pairs:
			ans = min(ans,N-rad_reach(-1,c1,0,E,rad,c2)-rad_reach(-1,c2,0,E,rad,c1))
	print ans
solve()

### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(1000000)
def calc_dist(b,h,dist,E,D,ne):
	D[dist] += 1
	for nxt in E[h]:
		if nxt == b or nxt == ne:
			continue
		calc_dist(h,nxt,dist+1,E,D,ne) 

def solve():
	N,K = map(int,raw_input().split())
	pairs = []
	E = [[] for i in xrange(N)]
	for i in xrange(N-1):
		a,b = map(lambda x:int(x)-1,raw_input().split())
		E[a].append(b)
		E[b].append(a)
		pairs.append((a,b))
	ans = N
	rad = K/2
	if K % 2 == 0:
		for i in xrange(N):
			D = [0]*N
			calc_dist(-1,i,0,E,D,-1)
			for j in xrange(rad):
				D[rad-j-1] += D[rad-j]
			ans = min(N-D[0],ans)
	else:
		for a,b in pairs:
			D1 = [0]*N
			D2 = [0]*N
			calc_dist(-1,a,0,E,D1,b)
			calc_dist(-1,b,0,E,D2,a)
			for j in xrange(rad):
				D1[rad-j-1] += D1[rad-j]
				D2[rad-j-1] += D2[rad-j]
			ans = min(N-D1[0]-D2[0],ans)
	print ans

solve()
### BUGGY CODE ###

n=int(input())
a= [int(i) for i in input().split()]
for i in range(1,n+1):
    print(a.count(i))

### FIXED CODE ###

n=int(input())
a= [int(i) for i in input().split()]
b=[0]*n
for i in a:
    b[i-1]+=1
for j in range(n):
    print(b[j])
### BUGGY CODE ###

B, W = map(int,input().split())
Mod = 10**9+7
magick = 500000004

DP_1 = [[0 for j in range(B+1)] for i in range(B+W+1)]
DP_1[0][B] = 1
for i in range(B+W):
  for j in range(B+1):
    if j == 0:
      DP_1[i+1][j] = 2*DP_1[i][j]+DP_1[i][j+1]
    elif j == B:
      DP_1[i+1][j] = DP_1[i][j]
    else:
      DP_1[i+1][j] = DP_1[i][j] +DP_1[i][j+1]
      
DP_2 = [[0 for j in range(W+1)] for i in range(B+W+1)]
DP_2[0][W] = 1
for i in range(B+W):
  for j in range(W+1):
    if j == 0:
      DP_2[i+1][j] = 2*DP_2[i][j]+DP_2[i][j+1]
    elif j == W:
      DP_2[i+1][j] = DP_2[i][j]
    else:
      DP_2[i+1][j] = DP_2[i][j] +DP_2[i][j+1]
      
inv = 1
for i in range(B+W):
  print(((-DP_1[i][0]+DP_2[i][0])*inv*magick+ magick)%Mod)
  inv = inv * magick%Mod

### FIXED CODE ###

B, W = map(int,input().split())
Mod = 10**9+7
magick = 500000004

inv_t = [0]+[1]
inv_2 = [0]+[magick]
for i in range(2,B+W+1):
  inv_t += [inv_t[Mod % i] * (Mod - int(Mod / i)) % Mod]
  inv_2 += [inv_2[-1]*magick % Mod]

consts_B, consts_W = [0]*(B-1)+ [1], [0]*(W-1)+[1]
for i in range(B+W):
  if i >= B: consts_B += [consts_B[-1]*(i)*inv_t[i-B+1]%Mod]
  if i >= W: consts_W += [consts_W[-1]*(i)*inv_t[i-W+1]%Mod]

p, q = 0, 0
for i in range(B+W):
  print((1-p+q)*magick%Mod)
  p += consts_B[i]*inv_2[i+1]
  q += consts_W[i]*inv_2[i+1]