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

# 早くなるおまじない
import sys
input = sys.stdin.buffer.readline

# 再帰関数の呼び出し制限
sys.setrecursionlimit(10**6)

n,q = map(int,input().split())

dic = {}
for i in range(n-1):
    aa, bb = map(int,input().split())

    if aa not in dic:
        dic[aa] = set()
        dic[aa].add(bb)
    else:
        dic[aa].add(bb)

    if bb not in dic:
        dic[bb] = set()
        dic[bb].add(aa)
    else:
        dic[bb].add(aa)


p = []
x = []
for _ in range(q):
    s, t = map(int,input().split())
    p.append(s)
    x.append(t)

res = [0]*n
for i in range(q):
    res[p[i]-1] += x[i]

visited = set()

# 深さが一つ前のやつのresの値を足す
# dfsはおk，ここで累積和を使う発想が出てこなかった
def dfs(node, prev):
    visited.add(node)
    if prev != 0:
        res[node-1] += res[prev-1]
    for i in dic[node]:
        if i not in visited:
            prev = node
            dfs(i, prev)

dfs(1, 0)
print(*res, sep=" ")

### FIXED CODE ###

# 早くなるおまじない
import sys
input = sys.stdin.buffer.readline

# 再帰関数の呼び出し制限
sys.setrecursionlimit(3 * 10 ** 5)

# 深さが一つ前のやつのresの値を足す
# dfsはおk，ここで累積和を使う発想が出てこなかった
# def dfs(node, prev):
#     visited.add(node)
#     if prev != 0:
#         res[node-1] += res[prev-1]
#     for i in dic[node]:
#         if i not in visited:
#             prev = node
#             dfs(i, prev)

def dfs(node, prev, visited, res, dic):
    visited.add(node)
    if prev != 0:
        res[node-1] += res[prev-1]
    for i in dic[node]:
        if i not in visited:
            prev = node
            dfs(i, prev, visited, res, dic)


def main():
    n,q = map(int,input().split())

    dic = {}
    for i in range(n-1):
        aa, bb = map(int,input().split())

        if aa not in dic:
            dic[aa] = set()
            dic[aa].add(bb)
        else:
            dic[aa].add(bb)

        if bb not in dic:
            dic[bb] = set()
            dic[bb].add(aa)
        else:
            dic[bb].add(aa)


    p = []
    x = []
    for _ in range(q):
        s, t = map(int,input().split())
        p.append(s)
        x.append(t)

    res = [0]*n
    for i in range(q):
        res[p[i]-1] += x[i]

    visited = set()

    dfs(1, 0, visited, res, dic)
    print(*res, sep=" ")

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

N, K = map(int, input().split())
S = []
for i in range(K):
    L, R = map(int, input().split())
    S += list(range(L, R+1))

dp = [0] * N
dp[0] = 1

S.sort()

for i in range(1, N):
    for s in S:
        if i - s < 0:break
        dp[i] += dp[i - s]

print(dp[-1] % 998244353)


### FIXED CODE ###

mod = 998244353
N, K = map(int, input().split())

S = []
for i in range(K):
    L, R = map(int, input().split())
    S.append((L, R))

dp = [0] * (N+1)
dpsum = [0] * (N+1)
dp[1] = 1
dpsum[1] = 1

for i in range(2, N+1):
    for s in S:
        l = i - s[1]
        r = i - s[0]
        if r < 1:continue
        l = max(1, l)

        dp[i] += dpsum[r] - dpsum[l-1]
        dp[i] %= mod

    dpsum[i] = (dpsum[i-1] + dp[i]) % mod

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

import math
from functools import reduce

def gcd(*numbers):
  return reduce(math.gcd, numbers)

n,ans=int(input()),0
for i in range(1,n+1):
  for j in range(1,n+1):
    for k in range(1,n+1):
      ans+=gcd(i,j,k) 
print(ans)

### FIXED CODE ###

import math
 
n,ans=int(input()),0
for i in range(1,n+1):
  for j in range(1,n+1):
    g=math.gcd(i,j)
    for k in range(1,n+1):
      ans+=math.gcd(g,k) 
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
note = sorted([list(map(int,input().split())) for i in range(N)])
note = sorted(note,key=lambda x:(x[0],-x[1]))
cnt = 0
head = []
remain = []
for i in range(N):
    if note[i][0] > cnt:
        cnt = note[i][0]
        head.append(note[i][1])
    else:
        remain.append(note[i][1])
head = sorted(head,reverse = True)
remain = sorted(remain,reverse = True)
ans = 0
for i in range(1,min(K,len(head))+1):
    if K - i > len(remain):
        continue
    deli = sum(head[:i]) + sum(remain[:K-i])
    kind = i**2
    res = deli + kind
    if res > ans:
        ans = res
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
note = [list(map(int,input().split())) for i in range(N)]
note = sorted(note,key=lambda x:(x[0],-x[1]))
cnt = 0
head = []
remain = []
for i in range(N):
    if note[i][0] > cnt:
        cnt = note[i][0]
        head.append(note[i][1])
    else:
        remain.append(note[i][1])
head = sorted(head,reverse = True)
remain = sorted(remain,reverse = True)
ans = 0
acc_head = [0]
acc_remain = [0]
tmp_head = 0
tmp_remain = 0
for i in range(len(head)):
    tmp_head += head[i]
    acc_head.append(tmp_head)
for i in range(len(remain)):
    tmp_remain += remain[i]
    acc_remain.append(tmp_remain)
for i in range(max(0,K-len(remain)),min(K,len(head))+1):
    deli = acc_head[i] + acc_remain[K-i]
    kind = i**2
    res = deli + kind
    if res > ans:
        ans = res
print(ans)
### BUGGY CODE ###

n=int(input())
# a,b,c=map(int,input().split())
cnt=0
def gcd(a,b):
    if a==0: return b
    else: return gcd(b%a,a)
# print(gcd(a,b))

def gcd_3(a,b,c):
    if gcd(a,b)==0: return c
    else: return gcd(c % gcd(a,b),gcd(a,b))

for i in range(1,n+1):
    for j in range ( 1 , n + 1 ):
        for k in range ( 1 , n + 1 ):
            # print(i,j,k)
            cnt+=gcd_3(i,j,k)
print(cnt)

### FIXED CODE ###

n=int(input())
# a,b,c=map(int,input().split())
cnt=0
def gcd(a,b):
    if a==0: return b
    else: return gcd(b%a,a)
# print(gcd(a,b))

def gcd_3(a,b,c):
    if gcd(a,b)==0: return c
    else: return gcd(c % gcd(a,b),gcd(a,b))

for i in range(1,n+1):
    for j in range ( 1 , n + 1 ):
        for k in range ( 1 , n + 1 ):
            # print(i,j,k)
            cnt+=gcd_3(i,j,k)
print(cnt)
### BUGGY CODE ###

N = int(input())
inputs = [int(i) for i in input().split()]

sorted_inputs = inputs[:]
sorted_inputs.sort()

for item in inputs:
    index = sorted_inputs.index(item)
    if index <= N // 2 - 1:
        print(sorted_inputs[N//2])
    else:
        print(sorted_inputs[N//2-1])


### FIXED CODE ###

N = int(input())
inputs = [int(i) for i in input().split()]

sorted_inputs = inputs[:]
sorted_inputs.sort()
left = sorted_inputs[N//2-1]
right = sorted_inputs[N//2]

for item in inputs:
    if item <= left:
        print(right)
    else:
        print(left)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

N, T = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x: x[1]//x[0], reverse=True)

def dfs(i, sum, time, remain):
    global answer
    if i == min(N, 1000):
        if time < T and len(remain) >= 1:
            sum += AB[min(remain)][1]
        if sum > answer:
            answer = sum
    else:
        dfs(i+1, sum, time, remain)
        if time < T:
            dfs(i+1, sum + AB[i][1], time + AB[i][0], remain-{i})

answer = 0
dfs(0, 0, 0, set(range(N)))
print(answer)

### FIXED CODE ###

import sys
import numpy as np

n, t = map(int, input().split())
knapsack = np.zeros(t, dtype=np.int64)
cuisines = [tuple(map(int, line.split())) for line in sys.stdin]
cuisines.sort()
tmp_ans = 0
for a, b in cuisines:
    tmp_ans = max(tmp_ans, knapsack.max() + b)
    knapsack[a:] = np.maximum(knapsack[a:], knapsack[:-a] + b)
print(tmp_ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""

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

dp=[0]*(W+1)
for i in range(1,N+1):
    #print(dp)
    w,v=map(int,input().split())
    A=dp[:w]
    A.extend([max(dp[j],dp[j-w]+v) for j in range(w,W+1)])
    dp=A
   
print(max(dp))


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""


N,W=map(int,input().split())
dp=[0]*(W+1)
L = sorted([list(map(int,input().split())) for i in range(N)])
s=0

for w, v in L:
    s+=w
    for j in range(min(W,s),w-1,-1):
        if dp[j-w]+v > dp[j]: dp[j]=dp[j-w]+v
    
print(max(dp))
### BUGGY CODE ###

from itertools import combinations


def main():
    N = int(input())
    edges = [int(i) for i in input().split()]

    ans = set()
    edges.sort()
    for a in range(N - 2):
        for b, c in combinations(range(a + 1, N), 2):
            if edges[a] < edges[b] + edges[c] and edges[b] < edges[c] + edges[a] and edges[c] < edges[a] + edges[b]:
                ans.add((a, b, c))
    print(len(ans))


if __name__ == "__main__":
    main()

### FIXED CODE ###

import bisect


def main():
    N = int(input())
    edges = [int(i) for i in input().split()]
    edges.sort()
    ans = 0
    for a in range(N - 2):
        for b in range(a + 1, N - 1):
            ans += bisect.bisect_left(edges, edges[a] + edges[b])-b-1

    print(ans)


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

a, b, k = map(int, input().split())
numlist = []

for i in range(a, b+1):
    if i <= a + k - 1:
        numlist.append(i)
for j in reversed(range(a, b+1)):
    if j >= b - k + 1:
        numlist.append(j)

numSet = set(numlist)
numlist = list(numSet)
numlist.sort()
 
for l in range(len(numlist)):
    print(numlist[l])

### FIXED CODE ###

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

if (b-a+1)/2 < k:
    for i in range(a, b+1):
        print(i)
else:
    for j in range(a, a+k):
        print(j)
    for k in range(b-k+1, b+1):
        print(k)
### BUGGY CODE ###

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

A = []
for _ in range(M):
    A.append(int(input()))

step = [0 for _ in range(N+1)]

step[0] = 1
if 1 not in A:
    step[1] = 1

for i in range(2, N+1):
    if i in A:
        pass
    else:
        step[i] = step[i-1] + step[i-2]


print(step[N] % (10**9+7))


### FIXED CODE ###

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

A = []
for _ in range(M):
    A.append(int(input()))

step = [0 for _ in range(N+1)]

ptr = 0

step[0] = 1
step[1] = 1
if ptr < M and A[ptr] == 1:
    step[1] = 0
    ptr += 1

for i in range(2, N+1):
    if ptr < M and i == A[ptr]:
        ptr += 1
    else:
        step[i] = step[i-1] + step[i-2]


print(step[N] % (10**9+7))
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
tmp = ''
kesu = ''
ans = 0
LR = []
for i in range(Q):
    array = list(map(int, input().strip().split(' ')))
    LR.append(array)
    
for i in range(Q): # 問iを解く
    ans = 0
    tmp = S[LR[i][0]-1:LR[i][1]]
    kesu = tmp.replace('AC', '')
    ans = (LR[i][1]-LR[i][0]+1-len(kesu))/2
    print(int(ans))

### FIXED CODE ###

# 答案
N,Q = map(int,input().split())
S = input()
l,r = 0,0
csum = [0]*(N+1)

# 累積和
for ctr in range(N):
    if ctr == (N-1):
        csum[ctr+1] = csum[ctr]
    elif S[ctr]=='A' and S[ctr+1]=='C':
        csum[ctr+1] = csum[ctr] + 1
    else:
        csum[ctr+1] = csum[ctr]

# 出力
for ctr in range(Q):
    l,r=map(int,input().split())
    print(csum[r-1] - csum[l-1])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
bc = [map(int, input().split()) for _ in range(Q)]
b, c = [list(i) for i in zip(*bc)]

mydict = {}
for i in A:
    if i in mydict:
        score = mydict[i]
        mydict[i] = score + 1
    else:
        mydict[i] = 1


    
for i in range(Q):
    if b[i] in mydict:
        if c[i] in mydict:
            score1 = mydict[b[i]]
            score2 = mydict[c[i]]
            del mydict[b[i]]
            mydict[c[i]] = score1 + score2
        else:
            mydict[c[i]] = mydict[b[i]]
            del mydict[b[i]]
            
    count = 0
    for k, v in mydict.items():
        count = count + k*v
    
    print(count)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
bc = [map(int, input().split()) for _ in range(Q)]
b, c = [list(i) for i in zip(*bc)]

mydict = {}
for i in A:
    if i in mydict:
        score = mydict[i]
        mydict[i] = score + 1
    else:
        mydict[i] = 1


count = 0
for k, v in mydict.items():
    count = count + k*v
    
for i in range(Q):
    if b[i] in mydict:
        if c[i] in mydict:
            score1 = mydict[b[i]]
            score2 = mydict[c[i]]
            
            count1 = score1* b[i]
            count2 = score1* c[i]
            del mydict[b[i]]
            mydict[c[i]] = score1 + score2
            count = count - count1 + count2

            
        else:
            count = count - b[i] * mydict[b[i]] + c[i] * mydict[b[i]]
            mydict[c[i]] = mydict[b[i]]
            del mydict[b[i]]
            

    
    print(count)
### BUGGY CODE ###

s = input()
n = len(s)
d = [s[0]]
for i in range(1,n):
  if s[i]=="C" and s[i-1]=='B':
    d.pop()
    d.append("x")
  else:
    d.append(s[i])
q = "".join(d)
cou = 0
while "Ax" in q:
  cou += q.count("Ax")
  q = q.replace("Ax","xA")
#  print(q)
print(cou)

### FIXED CODE ###

s = input()
n = len(s)
d = [s[0]]
for i in range(1,n):
  if s[i]=="C" and s[i-1]=='B':
    d.pop()
    d.append("x")
  else:
    d.append(s[i])
q = "".join(d)
cou = 0
cou_a = 0
l = len(q)
for i in range(l):
  if q[i]=="A":
    cou_a += 1
  elif q[i]=="x":
    cou +=  cou_a
  else:
    cou_a = 0
print(cou)
### BUGGY CODE ###

n,m = map(int, input().split())
a = list(map(int,input().split()))
for _ in range(m):
    b,c = map(int, input().split())
    a += [c]*b
a.sort()
print(sum(a[-n:]))


### FIXED CODE ###

from heapq import heappop, heappush


n,m = map(int,input().split())
A = list(map(int,input().split()))
pq = []
ans = 0

for a in A:
    heappush(pq, [-a, 1])
    
for _ in range(m):
    b,c = map(int,input().split())
    heappush(pq, [-c, b])

for i in range(n):
    c,b = heappop(pq)
    c = -c
    ans += c
    if b > 1:
        b -= 1
        heappush(pq, [-c, b])
        
print(ans)
### BUGGY CODE ###

from itertools import accumulate
def main():
    N=int(input())
    line = list(input())
    ans=[]

    for i in range(N+1):
        a=line[:i].count("#")
        b=line[i:].count(".")
        ans.append(a+b)
    return min(ans)

print(main())

### FIXED CODE ###

n = int(input())
s = input()
ans = s.count('.')
num = ans
for c in s:
  if c == '.':
    num -= 1
  else:
    num += 1
  
  ans = min(ans,num)

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

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

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

aloop = 0
bloop = 0

if len(set(A)) != len(A) or len(set(B)) != len(B):
    C = 0

else:
    for k in range(N * M, 0, -1):
        if C == 0:
            break
        if aloop < N and bloop < M and k == A[aloop] and k == B[bloop]:
            aloop += 1
            bloop += 1
        elif aloop < N and k == A[aloop]:
            C *= bloop
            aloop += 1
        elif bloop < M and k == B[bloop]:
            C *= aloop
            bloop += 1
        else:
            C *= (aloop*bloop-(N*M-k))

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

### FIXED CODE ###

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

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

aloop = 0
bloop = 0

if len(set(A)) != len(A) or len(set(B)) != len(B):
    C = 0

else:
    for k in range(N * M, 0, -1):
        if aloop < N and bloop < M and k == A[aloop] and k == B[bloop]:
            aloop += 1
            bloop += 1
        elif aloop < N and k == A[aloop]:
            C *= bloop
            aloop += 1
        elif bloop < M and k == B[bloop]:
            C *= aloop
            bloop += 1
        else:
            C *= (aloop * bloop - (N * M - k))

        C = C % (10**9+7)
print(C)
### BUGGY CODE ###

N = int(input())
TA = [list(map(int, input().split())) for i in range(N)]


t_votes = TA[0][0]
a_votes = TA[0][1]
for n in range(1, N):
    coeff = 1
    while True:
        if TA[n][0] * coeff >= t_votes and TA[n][1] * coeff >= a_votes:
            break
        coeff += 1
    t_votes = coeff * TA[n][0]
    a_votes = coeff * TA[n][1]

print(t_votes + a_votes)

### FIXED CODE ###

N = int(input())
TA = [list(map(int, input().split())) for i in range(N)]


t_votes = TA[0][0]
a_votes = TA[0][1]
for n in range(1, N):
    t_ratio = TA[n][0]
    a_ratio = TA[n][1]
    # coeff = 1
    # while TA[n][0] * coeff < t_votes or TA[n][1] * coeff < a_votes:
    #     coeff += 1
    # ↓
    coeff = max((t_ratio + t_votes - 1) // t_ratio,
                (a_ratio + a_votes - 1) // a_ratio)

    t_votes = coeff * t_ratio
    a_votes = coeff * a_ratio

print(t_votes + a_votes)
### BUGGY CODE ###

import sys

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

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    bb = list(map(int, input().split()))
    ans = 0
    for k in range(29):
        t = 1 << k
        t2 = t << 1
        am = list(map(lambda x: x % t2, aa))
        bm = list(map(lambda x: x % t2, bb))
        am.sort(reverse=True)
        bm.sort()
        #print(am)
        #print(bm)
        cnt = n % 2
        for tk in range(t, t * 4, t):
            j = 0
            for a in am:
                while j < n and a + bm[j] < tk:
                    j += 1
                cnt += j
        if cnt % 2:
            ans += t
    print(ans)

main()


### FIXED CODE ###

import sys
import numpy as np

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

def main():
    n = int(input())
    aa = np.array(list(map(int, input().split())), dtype="i8")
    bb = np.array(list(map(int, input().split())), dtype="i8")
    ans = 0
    for k in range(29):
        t = 1 << k
        t2 = t << 1
        am = aa % t2
        bm = bb % t2
        # am.sort(reverse=True)
        bm.sort()
        # print(am)
        # print(bm)
        cnt = n % 2
        for tk in range(t, t * 4, t):
            cnt += np.sum(np.searchsorted(bm, tk - am))
        if cnt % 2:
            ans += t
    print(ans)

main()
### BUGGY CODE ###

from itertools import accumulate
from collections import defaultdict


def main():
    n = int(input())
    prime_counter = defaultdict(int)  # key ^ value
    acc = tuple(accumulate(range(1, 42)))  # because 10^12 < 2^39

    def facs(n):
        yield 2
        for x in range(3, int(n ** 0.5) + 1, 2):
            yield x
        yield n

    for fac in facs(n):
        while n % fac == 0:
            n //= fac
            prime_counter[fac] += 1
            # ここで if fac * fac > n: braek を入れると，
            # 計算量の少ないケースでは早く，多いケースでは遅くなる。
    if n != 1:
        prime_counter[n] += 1

    ans = 0
    for c in prime_counter.values():
        for i, x in enumerate(acc):
            if c < x:
                tmp = i
                break
        ans += tmp
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter
from itertools import accumulate


def prime_factorize(n):
    """素因数分解し，ユニークな素因数のsetを返す。"""
    ans = []
    ans_add = ans.append
    while n % 2 == 0:
        ans_add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            ans_add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        ans_add(n)
    return ans


def main():
    n = int(input())
    primes = prime_factorize(n)
    acc = tuple(accumulate(range(1, 42)))
    counted = Counter(primes)
    ans = 0

    for c in counted.values():
        for i, x in enumerate(acc):
            if c >= x:
                tmp = i + 1
            else:
                break
        ans += tmp

    print(ans)


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

N,H = map(int,input().split())
A = []
B = []
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
C = 0
Ma = max(A)
while H > 0:
    if B == []:
        C += int(-(-H//Ma))
        H = 0
    else:
        Mb = max(B)
        if Ma > Mb:
            C += int(-(-H//Ma))
            H = 0
        else:
            C += 1
            H -= Mb
            B.remove(Mb)
print(C)

### FIXED CODE ###

N,H = map(int,input().split())
Ma = 1
B = []
for i in range(N):
    a,b = map(int,input().split())
    B.append(b)
    if a > Ma:
        Ma = a
B.sort()
B.reverse()
i = 0
Mb = B[0]
while Mb > Ma and H > 0:
  i += 1
  H -= Mb
  if i == N:
    Mb = 0
  else:
    Mb = B[i]
if H <= 0:
  print(i)
else:
  print(i+int(-(-H//Ma)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = [None] * n

    for i in range(1, n+1):
        res[i-1] = a_list.index(i)+1

    print(*res)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

import numpy as np

def main():
    n = int(input())
    a_list = np.array(list(map(int, input().split())))

    print(*np.argsort(a_list)+1)


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

from functools import lru_cache

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

k = min(n-1, k)

inf = 100000000

dp = [inf for _ in [0]*n]

@lru_cache(maxsize=None)
def cost(i, j):
	return abs(h[i] - h[j])

for i in range(k+1):
	dp[i] = cost(0, i)

for i in range(k+1, n):
	
	dp[i] = min([dp[i-j] + cost(i-j, i) for j in range(1, k+1)])

print(dp[-1])


### FIXED CODE ###

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

k = min(n-1, k)

inf = 100000000

dp = [inf for _ in [0]*n]

def cost(i, j):
	return abs(h[i] - h[j])

for i in range(k+1):
	dp[i] = cost(0, i)

for i in range(k+1, n):
	
	dp[i] = min([dp[i-j] + cost(i-j, i) for j in range(1, k+1)])

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

from fractions import gcd
from functools import lru_cache
@lru_cache(maxsize=None)
def solve(p, q, a, n, l=1):

    if n==1:
        #print(p, q, a, n, l, 1 if p==1 and q<=a and q>=l else 0)
        return 1 if p==1 and q<=a and q>=l else 0
    ans = 1 if p==1 and q<=a and q>=l else 0
    denom = l if p==0 else max(l, int(q/p))
    while n*q >= denom*p and denom <= a:  #n/denom >= p/q:
        p_, q_ = p*denom-q, q*denom
        if p_ <= 0:
            denom += 1
            continue
        gcd_ = gcd(p_, q_)
        p_ //= gcd_
        q_ //= gcd_
        ans += solve(p_, q_, a//denom, n-1, denom)

        denom += 1
    #print(p, q, a, n, l, ans)
    return ans

while True:
    p, q, a, n = map(int, input().split())
    if p==q==a==n==0:
        break
    gcd_ = gcd(p, q)
    p //= gcd_
    q //= gcd_
    print(solve(p, q, a, n))



### FIXED CODE ###

from fractions import gcd

def solve(p, q, a, n, l=1):
    ans = 1 if p==1 and q<=a and q>=l else 0
    denom = max(l, q//p)
    p_denom = denom*p
    while n*q >= p_denom and denom <= a:  #n/denom >= p/q:
        p_, q_ = p_denom-q, q*denom
        if p_ <= 0:
            denom += 1
            p_denom += p
            continue
        gcd_ = gcd(p_, q_)
        p_ //= gcd_
        q_ //= gcd_
        if n==2 and p_==1 and q_*denom<=a and q_>=denom:
            ans += 1
        else:
            ans += solve(p_, q_, a//denom, n-1, denom)
        denom += 1
        p_denom += p
    #print(p, q, a, n, l, ans)
    return ans

while True:
    p, q, a, n = map(int, input().split())
    if p==q==a==n==0:
        break
    gcd_ = gcd(p, q)
    p //= gcd_
    q //= gcd_
    if n==1:
        print(1 if p==1 and q<=a else 0)
    else:
        print(solve(p, q, a, n))