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

x, y, z, k = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

AB = []
for a in A:
    for b in B:
        AB.append(a+b)
        
AB.sort(reverse=True)
AB = AB[:k]

ABC = []
for ab in AB:
    for c in C:
        ABC.append(ab+c)

ABC.sort(reverse=True)
ABC = ABC[:k]

for abc in ABC:
    print(abc)

### FIXED CODE ###

x, y, z, k = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

ABC = []
for x, a in enumerate(A):
    if x+1 > 3000:
        break
        
    for y, b in enumerate(B):
        if (x+1)*(y+1) > 3000:
            break
    
        for z, c in enumerate(C):
            if (x+1)*(y+1)*(z+1) > 3000:
                break
            
            ABC.append(a+b+c)
            
ABC.sort(reverse=True)
ABC = ABC[:k]

for abc in ABC:
    print(abc)
### BUGGY CODE ###

import math
A,B,N=map(int,input().split())
start=0
for i in range(1,N+1):
    K=math.floor(((i/B)-(i//B))*A)
    if start<=K:
        start=K
print(start)

### FIXED CODE ###

import math
A,B,N=map(int,input().split())
start=0
i=min(B-1,N)
K=math.floor((A*i)/B)-A*(math.floor(i/B))
if start<=K:
    start=K
print(start)
### BUGGY CODE ###

number = int(input())
answer = 0
for i in range(number):
  print(i)
  target=0
  while i%2==0:
    target+=1
    answer=max(target,answer)
print(answer) 

### FIXED CODE ###

N=int(input())
ans=list()

for i in range(1,N+1):
  count = 0
  while i%2==0:
    i=i//2
    count+=1
  ans.append(count)

answer=ans.index(max(ans))
print(answer+1)
### BUGGY CODE ###

from math import gcd
from functools import reduce
N = int(input())
*A, = map(int, input().split())


MAX_N = 1000_000

primes = [1]*(MAX_N+1)
primes[1] = 1
for i in range(2, int(MAX_N**0.5)+1):
    if primes[i] > 1:
        continue
    for j in range(i, MAX_N+1, i):
        primes[j] = i

gcd_set = reduce(gcd, A)


b = {}

def prime_fact(n):
    ret = {}
    while n > 1:
        p = primes[n]
        if p in ret:
            ret[p] += 1
        else:
            ret[p] = 1
        n //= p


    for p in ret.keys():
        if p in b:
            return False
        else:
            b[p] = 1
    return True

for a in A:
    if not prime_fact(a):
        if gcd_set == 1:
            print('setwise coprime')
        else:
            print('not coprime')
        exit()

print('pairwise coprime')   




### FIXED CODE ###

from math import gcd
from functools import reduce
N = int(input())
*A, = map(int, input().split())

MAX_N = max(A)+5
primes = list(range(MAX_N+1))
for i in range(2, int(MAX_N**0.5)+1):
    if primes[i] < i:
        continue
    for j in range(2*i, MAX_N+1, i):
        primes[j] = i


def check():
    S = set()
    for a in A:
        T = set()
        while True:
            p = primes[a]
            if p != 1 and p in S:
                return False
            T.add(p)
            if p == a:
                break
            a //= p
        S |= T
    return True


if check() or all(a == 1 for a in A):
    print('pairwise coprime')
elif reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

n=int(input())
i=1
while(True):
  if (i+1)**2<=n:
    i+=1
print(i**2)

### FIXED CODE ###

n=int(input())
i=1
while(True):
  if (i+1)**2<=n:
    i+=1
  else:
    break
print(i**2)
### BUGGY CODE ###

#!/usr/bin/env python3
def main():
    import sys

    sys.setrecursionlimit(10 ** 6)

    def dfs(now: int, depth: int):
        """深度を記録しながらDFS"""
        if temp_dis[now] < depth:
            return
        temp_dis[now] = min(temp_dis[now], depth)
        for next in G[now]:
            dfs(next, depth + 1)
        
    N, X, Y = map(int, input().split())

    G = [[1]] + [[x - 1, x + 1] for x in range(1, N - 1)] + [[N - 2]]
    G[X - 1].append(Y - 1)
    G[Y - 1].append(X - 1)
    # print(G)

    distance = [set() for _ in [0] * N]
    for i in range(N):
        temp_dis = [N] * N
        dfs(i, 0)
        # print(i, temp_dis)
        for j in range(N):
            distance[temp_dis[j]].add((i, j) if i <= j else (j, i))
    
    for ans in distance[1:]:
        print(len(ans))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
def main():
    from collections import deque
        
    N, X, Y = map(int, input().split())

    G = [[1]] + [[x - 1, x + 1] for x in range(1, N - 1)] + [[N - 2]]
    G[X - 1].append(Y - 1)
    G[Y - 1].append(X - 1)

    dist = [[-1] * N for _ in [0] * N]
    for s in range(N):
        q = deque([s])
        dist[s][s] = 0
        while q:
            v = q.popleft()
            for nv in G[v]:
                if dist[s][nv] == -1:
                    dist[s][nv] = dist[s][v] + 1
                    q.append(nv)
    res = [0] * N
    for i in range(N):
        for j in range(i + 1, N):
            res[dist[i][j]] += 1
    for d in range(1, N):
        print(res[d])


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

def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N, M = LI()
    A = [[]for _ in range(M)]
    C = [0]*M
    for i in range(M):
        A[i], b = LI()
        c = LI()
        for j in range(b):
            C[i] += 2**(c[j]-1)
    loop = 2**N
    dp = [[inf]*loop for _ in range(M+1)]
    dp[0][0] = 0
    for i in range(M):
        for l in range(loop):
            dp[i + 1][l] = min(dp[i + 1][l],dp[i][l])
            next = l|C[i]
            if next==l:
                continue
            dp[i+1][next] = min(dp[i+1][next],dp[i][l] + A[i])
    ans = dp[M][loop-1]
    if ans==inf:
        print(-1)
    else:
        print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

"""

"""

### FIXED CODE ###

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N, M = LI()
a = [0]*M; b = [0]*M; c = [0]*(M)
for i in range(M):
    a[i], b[i] = LI()
    C = LI()
    for j in range(b[i]):
        c[i] += 2**(C[j]-1)
cou = int(0)
#print(c)
dp = [[0]*(2**N) for _ in range(N)]
dp = [inf]*(2**N)
dp[0] = 0

for i in range(2**N):
    for k in range(M):
        if i^c[k]!=i-c[k]:
            dp[i|c[k]] = min(dp[i|c[k]],dp[i]+a[k])

ans = dp[2**N-1]
if ans==inf:
    ans = -1
print(ans)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

N = int(input())
S = input().strip()

dic = {}
ans = 0

for i in range(N-2):
    dic['R'] = S[i+1:].count('R')
    dic['G'] = S[i+1:].count('G')
    dic['B'] = S[i+1:].count('B')
    for j in range(i+1, N-1):
        dic[S[j]] -= 1
        arr = ['R', 'G', 'B']
        if S[i] != S[j]:
            arr.remove(S[i])
            arr.remove(S[j])
            ans += dic[arr[0]]
            if j+j-i <= N-1 and S[j+j-i] == arr[0]:
                ans -= 1

print(ans)

### FIXED CODE ###

import sys

input = sys.stdin.readline

N = int(input())
S = input().strip()

dic = {}
ans = 0

for i in range(N-2):
    dic['R'] = S[i+1:].count('R')
    dic['G'] = S[i+1:].count('G')
    dic['B'] = S[i+1:].count('B')
    for j in range(i+1, N-1):
        dic[S[j]] -= 1
        arr = ['R', 'G', 'B']
        if S[i] != S[j]:
            arr.remove(S[i])
            arr.remove(S[j])
            ans += dic[arr[0]]
            if j+j-i <= N-1 and S[j+j-i] == arr[0]:
                ans -= 1

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

import numpy as np

def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    table = sorted(table)
    return table

def make_prime(U):
    is_prime = np.zeros(U,np.bool)
    is_prime[2] = 1
    is_prime[3::2] = 1
    M = int(U**.5)+1
    for p in range(3,M,2):
        if is_prime[p]:
            is_prime[p*p::p+p] = 0
    return is_prime, is_prime.nonzero()[0]
A, B = map(int, input().split())

A_list = set(divisor(A))
B_list = set(divisor(B))

list = A_list & B_list

_, primes = make_prime(10**9)

cnt = 1

for i in list:
    if i in primes:
        cnt += 1

print(cnt)

### FIXED CODE ###

import numpy as np

def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    table = sorted(table)
    return table

def make_prime(U):
    is_prime = np.zeros(U,np.bool)
    is_prime[2] = 1
    is_prime[3::2] = 1
    M = int(U**.5)+1
    for p in range(3,M,2):
        if is_prime[p]:
            is_prime[p*p::p+p] = 0
    return is_prime, is_prime.nonzero()[0]
A, B = map(int, input().split())

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

A_list = set(divisor(A))
B_list = set(divisor(B))

list = A_list & B_list

#_, primes = make_prime(10**8)

cnt = 1

for i in list:
    if is_prime(i):
        cnt += 1

print(cnt)
### BUGGY CODE ###

def main():
    n,k=map(int,input().split())
    arr = []
    for _ in range(n):
        a,b=map(int,input().split())
        arr.extend([a]*b)
    arr.sort()
    print(arr[k-1])
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n,k=map(int,input().split())
    arr = []
    for _ in range(n):
        a,b=map(int,input().split())
        arr.append((a, b))
    arr.sort()
    for x, c in arr:
        if k <= c:
            print(x)
            break
        else:
            k -= c
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n,m = map(int ,input().split())
a = list(set([int(input()) for _ in range(m)]))

mod = 10**9+7
ans = [0]*(n+1)
ans [0] = 1
if 1 not in a: ans[1] = 1

for i in range(2,n+1):
  if i in a: continue
  ans[i] = ans[i-1] + ans[i-2]
print(ans[-1]%mod)

### FIXED CODE ###

n,m = map(int, input().split())
a = set([int(input()) for _ in range(m)])
inf = 1000000007

dp = [0] * (n + 1)
dp[0] = 1
if 1 not in a:
  dp[1] = 1
else:
  dp[1] = 0
  
for i in range(2, n+1):
  if i in a:
    continue
  dp[i] = dp[i - 1] + dp[i - 2]
  dp[i] %= inf
  
print(dp[n])
### BUGGY CODE ###

import sys

def findminsum(lst,K,N):
    inf=10**10
    dp=[[inf]*N for s in range(K+1)]
    for s in range(K+1):
        for j in range(N):
            if j==0 and s<=lst[j]:
                dp[s][j]=lst[0]
            elif s>lst[j] and j>0:
                dp[s][j]=min(dp[s-lst[j]][j-1]+lst[j], dp[s][j-1])
            elif s<=lst[j] and j>0:
                dp[s][j]=min(lst[j],dp[s][j-1])
    # print(lst)
    # print(dp[0][:])
    # print(dp[1][:])
    # print(dp[K][:])
    return dp[K][N-1]

def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    cards=list(map(int,sys.stdin.readline().strip().split()))
    cards.sort()
    nn=0
    for i in range(N):
        if cards[i]<K:
            c=cards[i]
            cards[i]=0
            if findminsum(cards,K-c,N)>=K:
                nn+=1
            cards[i]=c
        else:
            break
    print(nn)

if __name__=='__main__':
    main()


### FIXED CODE ###

#4 9
#1 3 5 6
#の時に1（正解は0）と出力されるがACになる

N, K = map(int, input().split())
a=list(map(int, input().split()))
a.sort()
ans = N
t = 0
for i in range(N-1, -1, -1) :
  if t+a[i] < K:
    t += a[i]
  else:
    ans = min(ans, i)
print(ans)
### BUGGY CODE ###

import numpy as np
from collections import deque
 
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
 
dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
visited = np.zeros((h, w))
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#': continue
        q = deque()
        q.append((i, j, 0))
        visited[:, :] = 0
        while q:
            x, y, z = q.popleft()
            for dx, dy in dirr:
                nx, ny = x + dx, y + dy
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx, ny] and s[nx][ny] == '.':
                        q.append((nx, ny, z + 1))
                        if z + 1 > ans: ans = z + 1
                        visited[x, y] = 1
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
from collections import deque

h, w = [int(item) for item in input().split()]
field = []
field.append("#" * (w + 2))
for i in range(h):
    field.append("#" + input().rstrip() + "#")
field.append("#" * (w + 2))


ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if field[i][j] == "#":
            continue
        dist = [[-1] * (w + 2) for _ in range(h + 2)]
        dist[i][j] = 0
        dq = deque()
        dq.append((i, j, 0))
        while dq:
            x, y, d = dq.popleft()
            if field[x+1][y] == "." and dist[x+1][y] == -1:
                dist[x+1][y] = d+1
                dq.append((x+1, y, d+1))
            if field[x][y+1] == "." and dist[x][y+1] == -1:
                dist[x][y+1] = d+1
                dq.append((x, y+1, d+1))
            if field[x-1][y] == "." and dist[x-1][y] == -1:
                dist[x-1][y] = d+1
                dq.append((x-1, y, d+1))
            if field[x][y-1] == "." and dist[x][y-1] == -1:
                dist[x][y-1] = d+1
                dq.append((x, y-1, d+1))
        for line in dist:
            ans = max(ans, max(line))
        
print(ans)
### BUGGY CODE ###

# なんだか釈然としていないが解説の通りに
from collections import deque
import sys

def MI(): return map(int, sys.stdin.readline().split())

class water:
    def __init__(self, t, v):
        self.v = v
        self.tv = v * t

    def __le__(self, other):
        return self.v * other.tv - self.tv * other.v >= 0

    def __isub__(self, other):
        t = self.tv / self.v
        self.v -= other
        self.tv = t * self.v
        return self

    def __iadd__(self, other):
        self.v+=other.v
        self.tv+=other.tv
        return self

def main():
    n, l = MI()
    dam = deque()
    t, v = MI()
    print(t)
    dam.append(water(t, v))
    # stvはtvの合計（vがlのときのvt）
    stv = t * v
    for _ in range(n-1):
        t, v = MI()
        # 朝に水をもらう
        dam.appendleft(water(t, v))
        over = v
        stv += t * v
        # 増えた分の水を古い方から捨てる
        # ベクトルごと削除できるもの
        while dam[-1].v <= over:
            w = dam.pop()
            over -= w.v
            stv -= w.tv
        # 最後のはみ出しているベクトルは縮める
        stv -= dam[-1].tv  # 一度合計から取り出して
        dam[-1] -= over  # 縮めて
        stv += dam[-1].tv  # 元に戻す
        # その日の水温を出力
        print(stv / l)
        # グラフの左側が凹んでいたらベクトルを合成して凸に直す
        while len(dam)>1 and dam[0] <= dam[1]:
            w = dam.popleft()
            dam[0] += w

main()


### FIXED CODE ###

# なんだか釈然としていないが解説の通りに
from collections import deque
import sys

def MI(): return map(int, sys.stdin.readline().split())

class water:
    def __init__(self, t, v):
        self.v = v
        self.tv = v * t

    def __le__(self, other):
        return self.v * other.tv - self.tv * other.v >= 0

    def __isub__(self, other):
        t = self.tv / self.v
        self.v -= other
        self.tv = t * self.v
        return self

    def __iadd__(self, other):
        self.v+=other.v
        self.tv+=other.tv
        return self

def main():
    n, l = MI()
    dam = deque()
    t, v = MI()
    print(t)
    dam.append(water(t, v))
    # stvはtvの合計（vがlのときのvt）
    stv = t * v
    for _ in range(n-1):
        t, v = MI()
        # 朝に水をもらう
        dam.appendleft(water(t, v))
        over = v
        stv += t * v
        # 増えた分の水を古い方から捨てる
        # ベクトルごと削除できるもの
        while dam[-1].v <= over:
            w = dam.pop()
            over -= w.v
            stv -= w.tv
        # 最後のはみ出しているベクトルは縮める
        stv -= dam[-1].tv  # 一度合計から取り出して
        dam[-1] -= over  # 縮めて
        stv += dam[-1].tv  # 元に戻す
        # その日の水温を出力
        print(stv / l)
        # グラフの左側が凹んでいたらベクトルを合成して凸に直す
        while len(dam)>1 and dam[0] <= dam[1]:
            w = dam.popleft()
            dam[0] += w

main()
### BUGGY CODE ###

import math
import sys
N, P = list(map(int, input().split()))
M = math.ceil(P ** (1 / N))
for i in range(M, 0, -1):
    if P % (i ** N) == 0:
        print(i)
        sys.exit()


### FIXED CODE ###

import sys
N, P = list(map(int, input().split()))
M = int(P ** (1 / N) + 1.0E-7)
for i in range(M, 0, -1):
    if P % (i ** N) == 0:
        print(i)
        sys.exit()
### BUGGY CODE ###

import sys
imput=sys.stdin.readline
import heapq 
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    l[i][0],l[i][1]=-l[i][0],-l[i][1]
heapq.heapify(l)
ans=0
for i in range(n):
    ans-=l[0][0]*((-1)**i)
    minimum=heapq.heappop(l)
    for j in range(n-i-1):
        l[j][0],l[j][1]=l[j][1],l[j][0]
    #print(l)
print(ans)

### FIXED CODE ###

n=int(input())
l=[]
c=0
for i in range(n):
    a,b=map(int,input().split())
    c-=b
    l.append(a+b)
l.sort()
l=l[::-1]
for i in range(0,n,2):
    c+=l[i]
print(c)
### BUGGY CODE ###

N=int(input())
A=[int(x) for x in input().split()]
S=[0]*60

for i,a in enumerate(A):
  c=0
  while a>0:
    if a&1!=0:
      S[c]+=1
    a>>=1
    c+=1

s,c=0,0
while c<60:
  s+=S[c]*(N-S[c])*((2**c)%(10**9+7))
  c+=1

print(s%(10**9+7))


### FIXED CODE ###

N=int(input())
A=[int(x) for x in input().split()]

s=0
for c in range(60):
  m=1<<c
  bc=len([1 for x in A if x&m])
  s+=bc*(N-bc)*m
  s%=10**9+7
  
print(s)
### BUGGY CODE ###

import sys

h, w = list(map(int, input().split()))
field = [line.rstrip() for line in sys.stdin]

l = [[0] * (w + 2) for _ in [0] * (h + 2)]
r = [[0] * (w + 2) for _ in [0] * (h + 2)]
u = [[0] * (w + 2) for _ in [0] * (h + 2)]
d = [[0] * (w + 2) for _ in [0] * (h + 2)]

for i in range(1, h + 1):
    fi = field[i - 1]
    li = l[i]
    for j in range(1, w + 1):
        c = fi[j - 1]
        u[i][j] = u[i - 1][j] + 1 if c == '.' else 0
        li[j] = li[j - 1] + 1 if c == '.' else 0
for i in range(h, 0, -1):
    fi = field[i - 1]
    ri = r[i]
    for j in range(w, 0, -1):
        c = fi[j - 1]
        d[i][j] = d[i + 1][j] + 1 if c == '.' else 0
        ri[j] = ri[j + 1] + 1 if c == '.' else 0

ans = 0
for ll, rr, uu, dd in zip(l, r, u, d):
    ans = max(ans, max(map(sum, zip(ll, rr, uu, dd))))
print(ans - 3)


### FIXED CODE ###

import sys

h, w = list(map(int, input().split()))
field = [line.rstrip() for line in sys.stdin]

l = [[0] * (w + 2) for _ in [0] * (h + 2)]
r = [[0] * (w + 2) for _ in [0] * (h + 2)]
u = [[0] * (w + 2) for _ in [0] * (h + 2)]
d = [[0] * (w + 2) for _ in [0] * (h + 2)]

for i in range(1, h + 1):
    fi = field[i - 1]
    li = l[i]
    for j in range(1, w + 1):
        c = fi[j - 1]
        u[i][j] = u[i - 1][j] + 1 if c == '.' else 0
        li[j] = li[j - 1] + 1 if c == '.' else 0
for i in range(h, 0, -1):
    fi = field[i - 1]
    ri = r[i]
    for j in range(w, 0, -1):
        c = fi[j - 1]
        d[i][j] = d[i + 1][j] + 1 if c == '.' else 0
        ri[j] = ri[j + 1] + 1 if c == '.' else 0

ans = 0
for i in range(1, h + 1):
    li, ri, ui, di = l[i], r[i], u[i], d[i]
    ans = max(ans, max(li[j] + ri[j] + ui[j] + di[j] for j in range(1, w + 1)))
print(ans - 3)
### BUGGY CODE ###

n,p=map(int,input().split())
t=int(p**(1/n))
x=1
for i in range(t+1,0,-1):
  if p%(i**n)==0:
    x=i
    break
print(x)

### FIXED CODE ###

n,p=map(int,input().split())
t=int(p**(1/n))
x=1
if n<50:
  for i in range(t+1,0,-1):
    if p%(i**n)==0:
      x=i
      break
  print(x)
else:
  print(1)
### BUGGY CODE ###

B, W = list(map(int, input().split()))

MOD = 10**9+7
def MakeCombList(n,r, MOD): #iCrをi=0...nまで
    ret = []
    for i in range(n):
        if i < r:
            ret = ret+[0]
        elif i == r:
            ret = ret+[1]
        else:
            ret = ret+[ int(ret[-1]*(i)/(i-r)) % MOD]
    return ret
combB1 = MakeCombList(B+W, B-1, MOD)
combW1 = MakeCombList(B+W, W-1, MOD)

pow2list = [1]
y_pi = 0 #i回目までにBを食べ尽くした確率piの分子
y_qi = 0 #i回目までにWを食べ尽くした確率qiの分子
for i in range(B+W):
    pow2list += [pow2list[-1]*2 %MOD]
    y_pi = 0 if i < B else 2*y_pi + combB1[i-1] 
    y_qi = 0 if i < W else 2*y_qi + combW1[i-1]
    xi = pow2list[i+1]
    yi = (pow2list[i]-y_pi+y_qi) % MOD
    z = yi*pow(xi, MOD-2, MOD) % MOD
    #print("{}/{}: {}".format(yi,xi,z))
    print(z)

### FIXED CODE ###

B, W = list(map(int, input().split()))

MOD = 10**9+7

facts = [1,1] #階乗
invs = [1,1] #整数の逆元
invfacts = [1,1] #階乗の逆元
for ind in range(1, B+W):
    i = ind+1
    facts.append(facts[-1]*i % MOD)
    invs.append( -(MOD//i)*invs[MOD%i] % MOD )
    invfacts.append( invfacts[-1]*invs[i] % MOD )

def Comb(n, r, MOD=MOD):
    if n < r:
        return 0
    return facts[n]*invfacts[n-r]*invfacts[r] % MOD

y_pi = 0 #i回目までにBを食べ尽くした確率piの分子
y_qi = 0 #i回目までにWを食べ尽くした確率qiの分子
pow2 = 1
invxi = 1
inv2 = invs[2]
for i in range(B+W):
    #y_pi = 0 if i < B else 2*y_pi + ((facts[i-1]*invfacts[i-B] % MOD)*invfacts[B-1] % MOD)
    y_pi = (2*y_pi + Comb(i-1, B-1))%MOD
    #y_qi = 0 if i < W else 2*y_qi + ((facts[i-1]*invfacts[i-W] % MOD)*invfacts[W-1] % MOD)
    y_qi = (2*y_qi + Comb(i-1, W-1))%MOD
    invxi = invxi * inv2 % MOD
    yi = (pow2-y_pi+y_qi) % MOD
    z = yi*invxi % MOD
    print(z)
    pow2 = pow2*2 %MOD
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
n, q = [int(i) for i in sys.stdin.readline().split()]
graph = {i : [] for i in range(n)}
ct = [0 for i in range(n)]
inp = sys.stdin.readlines()
a_b = inp[:n-1]
p_x = inp[n-1:]
for i in a_b:
    a, b = [int(j) for j in i.split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

for i in p_x:
    p, x = [int(j) for j in i.split()]
    p -= 1
    ct[p] += x
already = {0}
que = [(0, ct[0])]
res = [0 for i in range(n)]
while len(que) > 0:
    cur, cost = que.pop(0)
    res[cur] = cost
    for _next in graph[cur]:
        if _next in already:
            continue
        next_cost = ct[_next]
        que.append((_next, cost + next_cost))
        already.add(cur)
print(" ".join([str(r) for r in res]))

### FIXED CODE ###

import sys

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

N, Q = map(int, input().split())
V = {i: [] for i in range(1, N + 1)}
for _ in range(N - 1):
    a, b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)

C = {i: 0 for i in range(1, N + 1)}

for _ in range(Q):
    p, x = map(int, input().split())
    C[p] += x


def propagate(u, p):
    for v in V[u]:
        if v == p:
            continue
        C[v] += C[u]
        propagate(v, u)


propagate(1, 0)

print(' '.join(str(C[i]) for i in range(1, N + 1)))
### BUGGY CODE ###

# -*- coding:utf-8 -*-
import math
n, k = list(map(int, input().split()))
nums = list(map(int, input().split()))
one_index = nums.index(1)
min = n
for i in range(k):
    left = one_index - i
    right = len(nums[one_index+1:]) + i
    if left + right > n-1:
        continue
    else:
        min_tmp = math.ceil(left/(k-1))+math.ceil(right/(k-1))
        if min > min_tmp:
            min = min_tmp
print(min)


### FIXED CODE ###

# -*- coding:utf-8 -*-
import math
n, k = list(map(int, input().split()))
nums = list(map(int, input().split()))
one_index = nums.index(1)
if k == len(nums):
    print(1)
else:
    print(math.ceil((n-1)/(k-1)))