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

import sys
sys.setrecursionlimit(10**6)


def DFS(point,left,right,cnt):
    global ans
    if point<=k:
        if cnt>ans:
            ans=cnt

    if left<n and point<=k:DFS(point+A[left],left+1,right,cnt+1)
    if right<m and point<=k:DFS(point+B[right],left,right+1,cnt+1)


n,m,k=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
ans=0
DFS(0,0,0,0)
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]+A[i]
for i in range(1,m+1):
    B[i]=B[i-1]+B[i]

ans,j=0,m
for i in range(n+1):
    if A[i]>k:break
    while B[j]>k-A[i]:
        j -=1
    ans=max(ans,i+j)
print(ans)
### BUGGY CODE ###


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

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

ans = 1
for i in range(N):
    ans *= A[i]

if ans <= 10**18:
    print(ans)
else:
    print(-1)


### FIXED CODE ###


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

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

if A.count(0) > 0:
    print(0)
    exit()

ans = 1
for i in range(N):
    ans *= A[i]
    if ans > 10**18:
        print(-1)
        exit()

if ans <= 10**18:
    print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
cnt = [0, 0, 0, 0]
for ai in list(map(int, input().split())):
    cnt[ai] += 1
p, q, r = cnt[1], cnt[2], cnt[3]

dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]

for k in range(r + 1):
    for j in range(r + q + 1):
        for i in range(n + 1):
            if not (0 < i + j + k <= n):
                continue
            tmp = 0
            if i > 0:
                tmp += dp[i - 1][j][k] * i
            if j > 0:
                tmp += dp[i + 1][j - 1][k] * j
            if k > 0:
                tmp += dp[i][j + 1][k - 1] * k
            tmp += n
            dp[i][j][k] = tmp / (i + j + k)

print(dp[p][q][r])


### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
a = [0,0,0]
for x in LI():
    a[x-1] += 1
dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

for k in range(a[2]+1):
    for j in range(a[1]+a[2]+1):
        for i in range(N+1):
            if not (0 < i+j+k <= N): continue
            x = 0.0
            if i > 0: x += dp[i-1][j][k] * (i/N)
            if j > 0: x += dp[i+1][j-1][k] * (j/N)
            if k > 0: x += dp[i][j+1][k-1] * (k/N)
            x += 1.0
            x *= N / (i+j+k)
            dp[i][j][k] = x
print(dp[a[0]][a[1]][a[2]])
### BUGGY CODE ###

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

a.sort()

count = 0

while a:
    k = a.pop(0)
    k_count = 1
    while (len(a) > 0) and (a[0] == k):
        a.pop(0)
        k_count += 1
    if k_count < k:
        count += k_count
    else:
        count += k_count - k
print(count)


### FIXED CODE ###

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

a.sort()

count = 0

while a:
    k = a.pop(-1)
    k_count = 1
    while (len(a) > 0) and (a[-1] == k):
        a.pop(-1)
        k_count += 1
    if k_count < k:
        count += k_count
    else:
        count += k_count - k
print(count)
### BUGGY CODE ###

def main():
    N, Q = map(int, input().split())
    S = input()
    ans = []
    for _ in range(Q):
        l, r = map(int, input().split())
        ans.append(S[l-1:r].count('AC'))

    for i in range(Q):
        print(ans[i])
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N, Q = map(int, input().split())
    S = list(input())

    templist = [0]
    for i in range(N-1):
        if S[i] == 'A' and S[i+1] == 'C':
            S[i] = 'a'
            templist.append(templist[-1]+1)
        else:
            templist.append(templist[-1])
    templist.append(templist[-1])

    ans = []
    for i in range(Q):
        l, r = map(int, input().split())
        ans.append(templist[r-1] - templist[l-1])
    for a in ans:
        print(a)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import copy

H, W = map(int, input().split())
state = []
for i in range(H):
    row_list = list(input())
    state.append(row_list)


def light(row, col, state):
    col1 = copy.copy(col)
    next = '.'
    while next == '.':
        state[row][col1] = '+'
        col1 += 1
        if col1 >= W:
            break
        next = state[row][col1]
    
    col2 = copy.copy(col)
    next = '.'
    while next == '.':
        state[row][col2] = '+'
        col2 -= 1
        if col2 < 0:
            break
        next = state[row][col2]
    
    row1 = copy.copy(row)
    next = '.'
    while next == '.':
        state[row1][col] = '+'
        row1 += 1
        if row1 >= H:
            break
        next = state[row1][col]
    
    row2 = copy.copy(row)
    next = '.'
    while next == '.':
        state[row2][col] = '+'
        row2 -= 1
        if row2 < 0:
            break
        next = state[row2][col]
    
    return state


def lighted_fun(state):
    blank_list = []
    for h in range(H):
        for w in range(W):
            if state[h][w] == '+':
                blank_list.append([h, w])
    return blank_list


def blank_fun(state):
    blank_list = []
    for h in range(H):
        for w in range(W):
            if state[h][w] == '.':
                blank_list.append([h, w])
    return blank_list


blank_list = blank_fun(state)
blank_count = 0
for blank in blank_list:
    row = blank[0]
    col = blank[1]
    c_state = copy.deepcopy(state)
    lighted_state = light(row, col, c_state)
    blank_count_now = len(lighted_fun(lighted_state))
    if blank_count_now > blank_count:
        blank_count = blank_count_now


print(blank_count)






### FIXED CODE ###

import copy
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
S = [[1 if a == '.' else 0 for a in list(input())]  for _ in range(H)]

def main():
    R = copy.deepcopy(S)
    for h in range(H):
        s = 0
        for w in range(W):
            if R[h][w] == 1:
                s += 1
                R[h][w] = s
            else:
                s = 0
        l = 0
        for w in range(W-1, -1, -1):
            if R[h][w] > 0:
                l = max(l, R[h][w])
                R[h][w] = l
            else:
                l = 0

    L = copy.deepcopy(S)
    for w in range(W):
        s = 0
        for h in range(H):
            if L[h][w] == 1:
                s += 1
                L[h][w] = s
            else:
                s = 0
        l = 0
        for h in range(H-1, -1, -1):
            if L[h][w] > 0:
                l = max(l, L[h][w])
                L[h][w] = l
            else:
                l = 0
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, L[h][w]+R[h][w]-1)
    print(ans)

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

#累積和＋煮豚ん
N = int(input())
A = list(map(int, input().split()))
cumsum = [0]
cumsumx = [0]
for i in range(N):
  cumsum.append(cumsum[i] + A[i])
  cumsumx.append(cumsumx[i] ^ A[i])
res = 0
"""
for i in range(1, N + 1):
  for j in range(i, N + 1):
    #print(i, j, cumsum[j - 1] - cumsum[i], cumsumx[j] ^ cumsumx[i - 1])
    if cumsum[j] - cumsum[i - 1] == cumsumx[j] ^ cumsumx[i - 1]:
      res += 1
"""   
for i in range(1, N + 1):
  l = i
  r = N
  j = (l + r) / 2

  while True:
    j = (l + r) // 2
    if r - l < 2:
      #print(i, j, l, r)
      break
    if cumsum[j] - cumsum[i - 1] == cumsumx[j] ^ cumsumx[i - 1]:
      l = j
    else:
      r = j
  #print(i, j)
  if j < N:
    if cumsum[j + 1] - cumsum[i - 1] == cumsumx[j + 1] ^ cumsumx[i - 1]:
        j += 1
  res += j - i + 1
    
print(res)
#print(cumsum)
#print(cumsumx)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
cumsum = [0]
cumsumx = [0]
for i in range(N):
  cumsum.append(cumsum[i] + A[i])
  cumsumx.append(cumsumx[i] ^ A[i])
res = 0
"""
for i in range(1, N + 1):
  for j in range(i, N + 1):
    #print(i, j, cumsum[j - 1] - cumsum[i], cumsumx[j] ^ cumsumx[i - 1])
    if cumsum[j] - cumsum[i - 1] == cumsumx[j] ^ cumsumx[i - 1]:
      res += 1
"""   
for i in range(1, N + 1):
  l = i
  r = N
  j = (l + r) / 2

  while True:
    j = (l + r) // 2
    if r - l < 2:
      #print(i, j, l, r)
      break
    if cumsum[j] - cumsum[i - 1] == cumsumx[j] ^ cumsumx[i - 1]:
      l = j
    else:
      r = j
  #print(i, j)
  if j < N:
    if cumsum[j + 1] - cumsum[i - 1] == cumsumx[j + 1] ^ cumsumx[i - 1]:
        j += 1
  res += j - i + 1
    
print(res)
#print(cumsum)
#print(cumsumx)
### BUGGY CODE ###

def solve():
    N, K = map(int,input().split())
    A = list(map(int,input().split()))

    for k in range(K):
        imos = [0] * (N+1)
        for i in range(N):
            imos[min(N,i+A[i]+1)] -= 1
            imos[max(0,i-A[i])] += 1
        
        A[0] = imos[0]
        for i in range(1,N):
            A[i] = A[i-1] + imos[i]
    
    print(*A)

if __name__ == '__main__':
    solve()

### FIXED CODE ###

def solve():
    N, K = map(int,input().split())
    A = list(map(int,input().split()))

    for k in range(K):
        imos = [0] * (N+1)
        for i in range(N):
            imos[min(N,i+A[i]+1)] -= 1
            imos[max(0,i-A[i])] += 1
        
        A[0] = imos[0]
        all_N = True
        for i in range(1,N):
            A[i] = A[i-1] + imos[i]
            if A[i] != N:
                all_N = False
        
        if all_N:
            break

    print(*A)

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
C = []
for i in range(M):
  b, c = map(int, input().split())
  for i in range(b):
    C.append(c)

A.sort()
C.sort(reverse=True)
j = 0
while (j < len(C)) and (A[j] < C[j]):
  A[j] = C[j]
  j += 1
  
print(sum(A))


### FIXED CODE ###

import sys
from operator import itemgetter

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = [int(a) for a in input().split()]
    A.sort()
    change = [[int(i) for i in input().split()] for _ in range(M)]
    change.sort(key = itemgetter(1), reverse = True)

    ai = 0
    for i in range(M):
        cb, c = change[i]
        if ai >= N or c < A[ai]: break
        for _ in range(cb):
            if ai >= N: break
            if A[ai] <= c:
                A[ai] = c
                ai += 1
            else: break
    print(sum(A))
    return 0

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

S = input()

# 1以上の同じ色の石の列は1つに集約できる
T = S[0]
for s in S[1:]:
    if T[-1] != s:
        T += s

print(len(T) - 1)


### FIXED CODE ###

S = input()

# 1以上の同じ色の石の列は1つに集約できる
cnt = 1
prev = S[0]
for s in S[1:]:
    if prev != s:
        cnt += 1
        prev = s

print(cnt - 1)
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]
for i in range(n-1):
    cnt = float("inf")
    for j in range(k):
        if i-j < 0: continue
        cnt = min(dp[-1-j] + abs(h[i-j]-h[i+1]), cnt)
        #print("i =",i,"j =",j,"i-j =",i-j,"i+j =",i+j,"cnt =",cnt)
    dp.append(cnt)
print(dp[-1])

### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]
for i in range(n-1):
    cnt = float("inf")
    for j in range(k):
        if i-j < 0: continue
        cnt = min(dp[-1-j] + abs(h[i-j]-h[i+1]), cnt)
        #print("i =",i,"j =",j,"i-j =",i-j,"i+j =",i+j,"cnt =",cnt)
    dp.append(cnt)
print(dp[-1])
### BUGGY CODE ###

import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache, reduce
from operator import xor
from heapq import heappush, heappop
INF = float("inf")
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy4, dx4 = [0, -1, 0, 1], [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def ceil(a, b): return (a + b - 1) // b
YES = "Yes"
NO = "No"



memo = {}
def ok(i, l, now, target):
    if i >= len(l):
        return now == target
    key = (i, now)
    if key in memo:
        return memo[key]

    memo[key] = ok(i + 1, l, now + l[i], target) or ok(i + 1, l, now - l[i], target)
    return memo[key]


def solve(s, x, y):
    ss = [(k, len(list(g))) for k, g in groupby(s)]
    if ss[0][0] == "F":
        x -= ss[0][1]
        ss.pop(0)

    h, v = [], []
    now = 0
    for t, n in ss:
        if t == "F":
            if now == 0:
                h.append(n)
            else:
                v.append(n)
        else:
            if n % 2 != 0:
                now = (now + 1) % 2

    memo.clear()
    ans = ok(0, h, 0, x)
    memo.clear()
    ans &= ok(0, v, 0, y)
    return YES if ans else NO


def main():
    s = input()
    x, y = map(int, input().split())

    print(solve(s, x, y))

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache, reduce
from operator import xor
from heapq import heappush, heappop
INF = float("inf")
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy4, dx4 = [0, -1, 0, 1], [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def ceil(a, b): return (a + b - 1) // b

YES = "Yes"
NO = "No"


def check(x, nums):
    x = abs(x)
    dp = [False] * (x + 1)
    dp[0] = True
    for y in nums:
        tmp = [False] * (x + 1)
        for i in range(len(dp)):
            if i + y < len(tmp):
                tmp[i + y] |= dp[i]
            if i - y >= 0:
                tmp[i - y] |= dp[i]
        dp = tmp
    return dp[x]


def solve(s, x, y):
    type_num = [(k, len(list(g))) for k, g in groupby(s)]
    if s[0] == "F":
        x -= type_num[0][1]
        type_num.pop(0)

    h, v = [], []
    now = 0
    for t, n in type_num:
        if t == "F":
            if now == 0:
                h.append(n)
            else:
                v.append(n)
        else:
            if n % 2 != 0:
                now = (now + 1) % 2
    return YES if check(x, h) and check(y, v) else NO


def main():
    s = input()
    x, y = map(int, input().split())

    print(solve(s, x, y))

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

N, K = map(int,input().split())
S = input()

aaaa = False

# K >= 14ぐらいでSは辞書順最小の文字で埋め尽くされる。

# あまり意味はないが計算結果が大きすぎてバグっても嫌なので上限を作っておく
if K >= 15:
    aaaa = True
elif 2 ** K >= N:
    aaaa = True

# 最小の文字だけで埋め尽くされる場合
if aaaa:
    print(min(S)*N)
    exit()


def get_reverce_dict(s_str):
    U = s_str + s_str[::-1]
    minindex = 0
    for p in range(1, N + 1):
        if check_reverce_dict(U, minindex, p):
            minindex = p
    return U[minindex:minindex+N]


def check_reverce_dict(u, pointer1, pointer2):
    for i in range(N - 1, -1, -1):
        if u[i + pointer1] < u[i + pointer2]:
            return False
        elif u[i + pointer1] > u[i + pointer2]:
            return True
    return False


for _ in range(K - 1):
    S = get_reverce_dict(S)


def get_last_dict(s_str):
    U = s_str + s_str[::-1]
    c = min(s_str)
    p = U.index(c)
    minindex = p
    p += 1
    while p <= N:
        if U[p] == c:
            if check_normal_dict(U, minindex, p):
                minindex = p
        p += 1
    return U[minindex:minindex+N]


def check_normal_dict(u, pointer1, pointer2):
    for i in range(N):
        if u[pointer1 + i] > u[pointer2 + i]:
            return True
        elif u[pointer1 + i] < u[pointer2 + i]:
            return False
    return False


S = get_last_dict(S)
print(S)

### FIXED CODE ###

N, K = map(int,input().split())
S = input()

aaaa = False

# K >= 14ぐらいでSは辞書順最小の文字で埋め尽くされる。

# あまり意味はないが計算結果が大きすぎてバグっても嫌なので上限を作っておく
if K >= 15:
    aaaa = True
elif 2 ** K >= N:
    aaaa = True

# 最小の文字だけで埋め尽くされる場合
if aaaa:
    print(min(S)*N)
    exit()

def get_last_dict(s_str):
    U = s_str + s_str[::-1]
    c = min(s_str)
    p = U.index(c)
    minindex = p
    p += 1
    while p <= N:
        if U[p] == c:
            if check_normal_dict(U, minindex, p):
                minindex = p
        p += 1
    return U[minindex:minindex+N]


def check_normal_dict(u, pointer1, pointer2):
    for i in range(N):
        if u[pointer1 + i] > u[pointer2 + i]:
            return True
        elif u[pointer1 + i] < u[pointer2 + i]:
            return False
    return False

S = get_last_dict(S)

if K == 1:
    print(S)
else:
    count = 0
    for c in S:
        if c == S[0]:
            count += 1
        else:
            break
    if count * (2 ** (K - 1)) >= N:
        print(S[0] * N)
    else:
        S = S[0] * (count * ((2 ** (K - 1)) - 1)) + S
        print(S[0:N])
### BUGGY CODE ###

import sys
input=sys.stdin.readline

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors


tmp = [0]*(N+1)
b = [0]*N
ball_num = 0
ball_box = []
for i in reversed(range(N)):
    if a[i] == 0:
        if (tmp[i+1]%2) == 0:
            continue
        else:
            ball_box.append(i+1)
            ball_num += 1
            val = make_divisors(i+1)
            for elms in val:
                tmp[elms] += 1
    elif a[i] == 1:
        if (tmp[i+1]%2) == 0:
            ball_box.append(i+1)
            ball_num += 1
            val = make_divisors(i+1)
            for elms in val:
                tmp[elms] += 1
        else:
            continue

print(ball_num)
if ball_num != 0:
    print(*ball_box)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
 
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
 
 
tmp = [0]*(N+1)
b = [0]*N
ball_num = 0
ball_box = []
for i in reversed(range(N)):
    if a[i] == 0:
        if (tmp[i+1]%2) == 0:
            continue
        else:
            ball_box.append(i+1)
            ball_num += 1
            val = make_divisors(i+1)
            for elms in val:
                tmp[elms] += 1
    elif a[i] == 1:
        if (tmp[i+1]%2) == 0:
            ball_box.append(i+1)
            ball_num += 1
            val = make_divisors(i+1)
            for elms in val:
                tmp[elms] += 1
        else:
            continue
 
print(ball_num)
if ball_num != 0:
    print(*ball_box)
### BUGGY CODE ###

import copy
import math
N, K = map(int, input().split())
A = list(map(int, input().split()))
A2 = [0]*N
for i in range(K):
    for j in range(N):
        g = math.ceil(j+1-A[j]-0.5)
        if g<1:
            g=1
        h = math.floor(j+1+A[j]+0.5)
        if h>N:
            h=N
        for x in range(g,h+1):
            A2[x-1]+=1
    A=copy.copy(A2)
    A2 = [0]*N

print(*A)

### FIXED CODE ###

import math
N, K = map(int, input().split())
A = list(map(int, input().split()))
A2 = [0]*(N+1)
for i in range(K):
    for j in range(N):
        g = math.ceil(j+1-A[j]-0.5)
        if g<1:
            g=1
        h = math.floor(j+1+A[j]+0.5)
        if h>N:
            h=N
        A2[g-1]+=1
        A2[h]-=1
    A[0]=A2[0]
    for j in range(1, N):
        A[j]=A[j-1]+A2[j]
    A2 = [0]*(N+1)
    c = 0
    for p in range(N):
        c+=A[p]
    if c >= N*N:
        break

print(*A)
### BUGGY CODE ###

X = input()
while ("ST" in X):
  X = X.replace("ST","")
print(len(X))

### FIXED CODE ###

X = input()
l = []
for x in X:
  if x == "S":
    l.append(x)
  else:
    if l == [] or l[-1] == "T":
      l.append(x)
    elif l[-1] == "S":
      l.pop(-1)
print(len(l))
### BUGGY CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
C = []
for i in range(N):
  a = A[i]
  A[i] = 0
  B = Counter(A)
  for v in B.values():
    if v != 1:
      C.append(v*(v-1)//2)
  print(sum(C))
  C.clear()
  A[i] = a

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
c = Counter(A)
cnt = [0]*N
for k,v in c.items():
    cnt[k-1] = v*(v-1)//2
num = sum(cnt)
ans = 0
for a in A:
   print(num-c[a]+1)
### BUGGY CODE ###


from fractions import gcd

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_
        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
    #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))



### 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))
### BUGGY CODE ###

#coding:utf-8
n,k  = map(int,input().split())
ls_a  = list(map(int,input().split()))
target = int(k*(k+1)/2)
ls_target = []
i = 1
while(1):
    for j in range(i):
        temp = ls_a[j:(len(ls_a)-i+j+1)]
        ls_target.append(temp)
    if len(ls_target)>=k*10:
    #if i==n:
        break
    i+=1

def check(num):
    for i in range(100):
        if (num < 2**i):
            return i-1, 2**(i-1)
mx = sum(ls_target[0])
digit, mx_bin = check(mx)
ans = 0
for d in range(digit+1):
#    print (mx_bin)
#    print (ls_target)
    new_idx = []
    cnt = 0
    for idx,ls in enumerate(ls_target):
        if sum(ls) & mx_bin > 0:
            cnt += 1
            new_idx.append(idx)
    if cnt >= k:
        ls_target = [ls_target[i] for i in new_idx]
        ans += mx_bin
    mx_bin = int(mx_bin/2)
print (ans)

### FIXED CODE ###

#coding:utf-8
n,k  = map(int,input().split())
ls_a  = list(map(int,input().split()))
target = int(k*(k+1)/2)
ls_target = []
i = 1
while(1):
    for j in range(i):
        temp = ls_a[j:(len(ls_a)-i+j+1)]
        ls_target.append(sum(temp))
    if i==n:
        break
    i+=1

def check(num):
    for i in range(50):
        if (num < 2**i):
            return i-1, 2**(i-1)
mx = ls_target[0]
digit, mx_bin = check(mx)
ans = 0
for d in range(digit+1):
#    print (mx_bin)
#    print (ls_target)
    new_idx = []
    cnt = 0
    for idx,ls in enumerate(ls_target):
        if ls & mx_bin > 0:
            cnt += 1
            new_idx.append(idx)
    if cnt >= k:
        ls_target = [ls_target[i] for i in new_idx]
        ans += mx_bin
    mx_bin = int(mx_bin/2)
print (ans)