Harryxun/stf_run huggingface dataset:
n = int(input())

spoken_words = []
for i in range(9):
    word = input()
    if i >= 1:
        if word in spoken_words or spoken_words[-1][-1] != word[0]:
            print("No")
            exit()
    spoken_words.append(word)
print("Yes")

### FIXED CODE ###

n = int(input())

spoken_words = []
for i in range(n):
    word = input()
    if i >= 1:
        if word in spoken_words or spoken_words[-1][-1] != word[0]:
            print("No")
            exit()
    spoken_words.append(word)
print("Yes")
def selectionsort(A, N):
	count = 0
	for i in range(N):
		min_a = min(A[i:])
		min_index = A.index(min_a)
		A[i], A[min_index] = min_a, A[i]
		if (A[i] != A[min_index]): count += 1
	return count

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

	c = selectionsort2(data, n)
	print(*data)
	print(c)

if __name__ == "__main__":
	main()

### FIXED CODE ###

def selectionsort(A, N):
	count = 0
	for i in range(N):
		minj = i
		for j in range(i, N):
			if A[j] < A[minj]:
				minj = j
		A[i], A[minj] = A[minj], A[i]
		if (A[i] != A[minj]):
			count += 1
	return count

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

	c = selectionsort(data, n)
	print(*data)
	print(c)

if __name__ == "__main__":
	main()
import math
A,B,C,D = map(int,input().split())
lcm = int( C*D / math.gcd(C,D)  )

first_c = int( ( A - 1) / C)
first_d = int( ( A - 1) / D)
first_cd = int( ( A - 1) / lcm )
first = ( A - 1 ) - ( first_c + first_d - first_cd )

end_c = int( B / C)
end_d = int( B / D)
end_cd = int( B / lcm )
end = B - ( end_c + end_d - end_cd )

print(end - first)

### FIXED CODE ###

A,B,C,D = map(int,input().split())
import fractions
lcm = int( C*D / ( fractions.gcd(C,D) ) )

first_c = ( A - 1) // C
first_d = ( A - 1) // D
first_cd = ( A - 1) // lcm 
first = ( A - 1 ) - ( first_c + first_d - first_cd )

end_c = B // C
end_d = B // D
end_cd = B // lcm 
end_ = B - ( end_c + end_d - end_cd )

print(end_ - first)
N, = input().split()
A = input().split() 
ans = [0] * 200000
for i in range(int(N) - 1):
    ans[int(A[i])] += 1
for i in range(1, int(N)+1):
    print(ans[i])

### FIXED CODE ###

N, = input().split()
A = input().split() 
ans = [0] * 2000001
for i in range(int(N) - 1):
    ans[int(A[i])] += 1
for i in range(1, int(N)+1):
    print(ans[i])
A,B = map(int,input().split())
if 1 in A or 1 in B:
    if A==1 and B==1:
        print("Draw")
    elif A==1:
        print("Alice")
    else:
        print("Bob")
else:
    if A>B:
        print("Alice")
    elif B>A:
        print("Bob")
    else:
        print("Draw")

### FIXED CODE ###

A,B = map(int,input().split())
if A == 1 or B == 1:
    if A==1 and B==1:
        print("Draw")
    elif A==1:
        print("Alice")
    else:
        print("Bob")
else:
    if A>B:
        print("Alice")
    elif B>A:
        print("Bob")
    else:
        print("Draw")
s = input()
if s = "SUN":
  print(0)
if s = "MON":
  print(6)
if s = "TUE":
  print(5)
if s = "WED":
  print(4)
if s = "THU":
  print(3)
if s = "FRI":
  print(2)
if s = "SUT":
  print(1)
  

### FIXED CODE ###

s = input()
if s == "SUN":
  print(7)
if s == "MON":
  print(6)
if s == "TUE":
  print(5)
if s == "WED":
  print(4)
if s == "THU":
  print(3)
if s == "FRI":
  print(2)
if s == "SAT":
  print(1)
N, M, X = map(int, input().splist())
list=list(map(int, input().splist()))
a, b = 0,0
for i in list:
    if i<X:
        a+=1
    else:
        b+=1
print(min(a, b))

### FIXED CODE ###

N, M, X=map(int, input().split())
sum=sum(int(i)<X for i in input().split())
print(min(sum, M-sum))
cases = int(input())

account = {'AC': 0, 'WA' : 0, 'TLE':0, 'RE':0}

while --cases > 0:
  ++account[input()]
  
print('AC x '+ account['AC'])
print('WA x '+ account['WA'])
print('TLE x '+ account['TLE'])
print('RE x '+ account['RE'])

### FIXED CODE ###

import sys
input = sys.stdin.readline

cases = int(input())
account = {'AC': 0, 'WA' : 0, 'TLE':0, 'RE':0}

while cases > 0:
  account[input().split()[0]] += 1
  cases -= 1
  
print('AC x '+ str(account['AC']))
print('WA x '+ str(account['WA']))
print('TLE x '+ str(account['TLE']))
print('RE x '+ str(account['RE']))
n=int(input())
print((k//2)*((k+1)//2))

### FIXED CODE ###

n=int(input())
o=int(n/2)
e=int((n+1)/2)
print(o*e)
n = int(input())
a = int(input())
b = int(input())
x = max(a, b)
y = a+b-n
if y < 0:
    y = 0
print(x, y)

### FIXED CODE ###

n,a,b = (int(i) for i in input().split())
x=min(a,b)
y=a+b-n
if y < 0:
    y=0
print(x,y)
x = raw_input()
print(x**3)

### FIXED CODE ###

x = input()
print(x**3)
#EDPC L

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

#dp[l][r]:=区間[l,r]が残っている時の(直後の人の最終的な得点-そうじゃない方の最終的な得点）

dp=[[-1]*N for _ in range(N)]


#for i in range(N-1):
#    for j in range()
def rec(l,r):
    if dp[l][r]!=-1:
        return dp[l][r]
    
    if l==r:
        dp[l][r]=a[l]
        return dp[l][r]
    
    dp[l][r]=max(a[l]-rec(l+1,r),a[r]-rec(l,r-1))

    return dp[l][r]


print(rec(0,N-1))

### FIXED CODE ###

#EDPC L メモ化再帰じゃTLEで通らないのでやり直し

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

#dp[l][r]:=区間[l,r]が残っている時の(直後の人の最終的な得点-そうじゃない方の最終的な得点）

dp=[[-1]*N for _ in range(N)]

for k in range(N):
    dp[k][k]=a[k]

for r in range(1,N):
    for l in reversed(range(r)):
        dp[l][r]=max(a[l]-dp[l+1][r],a[r]-dp[l][r-1])

print(dp[0][N-1])
N=int(input())
H=list(map(int,input().split()))

list=[]
count=0

for i in range(N-1):
    if  H[i]>=H[i+1]:
      count+=1
    else:
      list.append(count)
      count=0
print(max(list))

### FIXED CODE ###

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

count_list = []
count = 0

for i in range(N-1):
  if H[i] >= H[i+1]:
    count += 1
  else:
    count_list.append(count)
    count = 0
else:
  count_list.append(count)
    
print(max(count_list))
n = int(input())
list = list(map(int, input().split(" ")))
sum = sum(list)
num = int(input())
for x in range(num):
    a = list(map(int, input().split()))
    ans = sum + a[1] - list[a[0]-1]
    print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split(" ")))
s = sum(l)
num = int(input())
for x in range(num):
    a = list(map(int, input().split()))
    ans = s + a[1] - l[a[0]-1]
    print(ans)
n,m = map(int,input().split())
l,r = 1,N
for i in range(m):
  L,R = map(int,input().split())
  L = max(l,L)
  R = min(r,R)
print(max(0,L-R+1))

### FIXED CODE ###

n,m = map(int,input().split())
l,r = 1,n
for i in range(m):
  L,R = map(int,input().split())
  l = max(l,L)
  r = min(r,R)
print(max(0,r-l+1))
H,W = map(int,input().split())
grid = []
for i in range(H):
    a,b,c,d = input()
    l = [a,b,c,d]
    grid.append(l)
delete = []
grid_1 = []
for i,job in enumerate(grid):
    count = 0
    for j in job:
        if(j == "."):
            count += 1
    if(count != W):
        grid_1.append(job)
count = 0
for i in delete:
    grid.pop(i-count)
    count += 1
grid_3 = []
for Row in zip(*grid_1):
    w = len(Row)
    count = 0
    for j in Row:
        if(j == "."):
            count += 1
    if(count != w):
        grid_3.append(Row)
for Row in zip(*grid_3):
    ans = ""
    for j in Row:
        ans += j
    print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
grid = []
for i in range(H):
    a = input()
    l = []
    for i in a:
        l.append(i)
    grid.append(l)
grid_1 = []
delete = []
for i,job in enumerate(grid):
    count = 0
    for j in job:
        if(j == "."):
            count += 1
    if(count != W):
        grid_1.append(job)
count = 0
for i in delete:
    grid.pop(i-count)
    count += 1
grid_3 = []
for Row in zip(*grid_1):
    w = len(Row)
    count = 0
    for j in Row:
        if(j == "."):
            count += 1
    if(count != w):
        grid_3.append(Row)
for Row in zip(*grid_3):
    ans = ""
    for j in Row:
        ans += j
    print(ans)
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

inf = 10**30
N,X,D = II()

if D<0:
    X,D = -X,-D

kukan = []
for i in range(N+1):
    kukan.append([i*X+(i*(i-1)//2)*D, i*X+(N*(N-1)//2-(N-i)*(N-i-1)//2)*D, (i*X)%D])
kukan.sort(key=lambda x:(x[2],x[0]))

div,d_min,d_max = inf,inf,inf
ans = 0
for k in kukan:
    if k[2]!=div:
        if d_min!=inf:
            ans += (d_max-d_min)//D + 1
        d_min,d_max,div = k[0],k[1],k[2]
    else:
        if k[0]>d_max:
            ans += (d_max-d_min)//D + 1
            d_min,d_max = k[0],k[1]
        else:
            d_max = k[1]
ans += (d_max-d_min)//D + 1

print(ans)

### FIXED CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

inf = 10**30
N,X,D = II()

if D==0:
    if X==0:
        print(1)
    else:
        print(N+1)
    exit()
if D<0:
    X,D = -X,-D

kukan = []
for i in range(N+1):
    kukan.append([i*X+(i*(i-1)//2)*D, i*X+(N*(N-1)//2-(N-i)*(N-i-1)//2)*D, (i*X)%D])
kukan.sort(key=lambda x:(x[2],x[0]))

div,d_min,d_max = inf,inf,inf
ans = 0
for k in kukan:
    if k[2]!=div:
        if d_min!=inf:
            ans += (d_max-d_min)//D + 1
        d_min,d_max,div = k[0],k[1],k[2]
    else:
        if k[0]>d_max:
            ans += (d_max-d_min)//D + 1
            d_min,d_max = k[0],k[1]
        else:
            d_max = max(d_max,k[1])
ans += (d_max-d_min)//D + 1

print(ans)
from sys import stdin
import math
columns = int(stdin.readline().rstrip())
datas = [stdin.readline().rstrip().split() for _ in range(columns)]
for data in datas:
    A = int(data[0])
    B = int(data[1])
    C = int(data[2])
    D = int(data[3])
    if A < B:
        print("No")
        continue
    if D < B:
        print("No")
        continue
    if C > B:
        print("Yes")
        continue
    g = math.gcd(B,D)
    if (B - g + A % g) >C :
        print("No")
    else:
        print("Yes")     
    


### FIXED CODE ###

from sys import stdin
data = [stdin.readline().rstrip().split() for _ in range(2)]
count = 0
i = 0
while i + count+ 1 < int(data[0][0]):
    if (data[1][i + count+ 1] == data[1][i + count]):
        count = count + 1
    i = i + 1
print(count)
n, d = map(int, input().split())
points = [[]] * n
for i in range(n):
  points[i] = list(map(int, input().split()))

def helper(a, b):
  s = 0
  for i in range(n):
    s += (a[i] - b[i]) ** 2
  a = int(0.5 + (s ** 0.5))
  if a * a == s:
    return 1
  return 0

ans = 0
for i in range(n):
	for j in range(i + 1, n):
		ans += helper(points[i], points[j])
print(ans)

### FIXED CODE ###

n, d = map(int, input().split())
points = [[]] * n
for i in range(n):
  points[i] = list(map(int, input().split()))
 
def helper(a, b):
  s = 0
  for i in range(d):
    s += (a[i] - b[i]) ** 2
  a = int(0.5 + (s ** 0.5))
  if a * a == s:
    return 1
  return 0
 
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        ans += helper(points[i], points[j])
print(ans)
import sys
sys.setrecursionlimit(1000000)

H = int(input())
ls = [-1]*(H+1)
ls[0] = 0
ls[1] = 1
def battle(h):
  if ls[h] != -1:
    return ls[h]
  else:
    tmp = 2*battle(h//2)
    ls[h] = tmp+1
    return ls[h]
print(battle(H))



### FIXED CODE ###

H = int(input())

def battle(h):
  if h == 1:
    return 1
  else:
    return 2*battle(h//2)+1
print(battle(H))
# list: ソート済配列
# n: 参照番号
@profile
def gcd(list, n):
    if n == 0:
        return list[0]
    else:
        a, b = list[n-1], list[n]
        
        while list[n]:
            list[n-1], list[n] = list[n], list[n-1] % list[n]

        list[n-1] = (a*b)/list[n-1]
        return gcd(list, n-1)

N = int(input())
T = [int(input()) for i in range(N)]
T.sort(reverse=True)
print(int(gcd(T, N-1)))



### FIXED CODE ###

# list: ソート済配列
# n: 参照番号
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a*b//gcd(a, b)

N = int(input())
T = [int(input()) for i in range(N)]
ans = 1

for i in range(N):
    ans = lcm(ans, T[i])

print(ans)
n,a,b,c,d=map(int,input().split())
s=input()
for i in range(a-1:c-1):
  if s[i:i+2]=='##':
    print('No')
    exit()
for i in range(b-1:d-1):
  if s[i:i+2]=='##':
    print('No')
    exit()
if c<d:
  print('Yes')
else:
  for i in range(b-1:c-1):
    if s[i:i+3]=='...':
      print('Yes')
      exit()
  print('No')


### FIXED CODE ###

n,a,b,c,d=map(int,input().split())
s=input()
for i in range(a-1,c-1):
  if s[i:i+2]=='##':
    print('No')
    exit()
for i in range(b-1,d-1):
  if s[i:i+2]=='##':
    print('No')
    exit()
if c<d:
  print('Yes')
else:
  for i in range(b-2,d-1):
    if s[i:i+3]=='...':
      print('Yes')
      exit()
  print('No')
st=input().split()
H=int(st[0]);W=int(st[1])
c=[[0 for i in range(10)] for i in range(10)]
A=[[0 for i in range(W)]for i in range(H)]
for i in range(10):
    st=input().split()
    for j in range(10):
        c[i][j]=int(st[j])
for i in range(H):
    st=input().split()
    for j in range(W):
        A[i][j]=int(st[j])
import math
def Dijkstra(s):
#    import pdb;pdb.set_trace()
    d=[math.inf]*10
    d[s]=0
    Q=set(range(10))
    V=set(range(10))
    while(len(Q)>0):
        u=list(Q)[0]
        for i in Q:
            if d[i]<d[u]:
                u=i
        Q-={u}
        for v in V-{u}:
            if (d[v]>d[u]+c[u][v]):
                d[v]=d[u]+c[u][v]
    return d[1]
result=0
DD=[0]*10
for i in range(10):
    DD[i]=Dijkstra(i)
for i in range(H):
    for j in range(W):
        if A[i][j]!=-1:
            result+=DD[A[i][j]]
print(result)


### FIXED CODE ###

import math
st=input().split()
H=int(st[0]);W=int(st[1])
c=[[0 for i in range(10)] for i in range(10)]
A=[[0 for i in range(W)]for i in range(H)]
for i in range(10):
    st=input().split()
    for j in range(10):
        c[i][j]=int(st[j])
for i in range(H):
    st=input().split()
    for j in range(W):
        A[i][j]=int(st[j])
def Dijkstra(s):
    d=[10000]*10
    d[s]=0
    Q=set(range(10))
    V=set(range(10))
    while(len(Q)>0):
        u=list(Q)[0]
        for i in Q:
            if d[i]<d[u]:
                u=i
        Q-={u}
        for v in V-{u}:
            if (d[v]>d[u]+c[u][v]):
                d[v]=d[u]+c[u][v]
    return d[1]
result=0
DD=[0]*10
for i in range(10):
    DD[i]=Dijkstra(i)
for i in range(H):
    for j in range(W):
        if A[i][j]!=-1:
            result+=DD[A[i][j]]
print(result)
N, K = map(int, input().split())
A = list(map(int, input().split()))

K = min(K, 50)
for _ in range(K):
    B = [0 for _ in range(N)]
    for i in range(N):
        l = max(0, i - A[i])
        r = min(N - 1, i + A[i])
        B[l] += 1
        if r+1 < N:
            B[r+1] -= 1
    
    for i in range(1, N):
        B[i] += B[i-1]
    
    A = B.copy()

print(" ".join(map(str, A)))

### FIXED CODE ###

S = input()
print(S[:3])
N,L=map(int, input().split())
if N+L-1<=0:
  print(int(L*(N-1)+N*(N-1)/2-N+1))
elif L>=0:
  print(int(L*(N-1)+N*(N+1)/2-1-N+1))
else :
  print(int(L*N+N*(N+1)/2-N))

### FIXED CODE ###

s=int(input())
a=s//1000
b=(s-a*1000)//100
c=(s-a*1000-b*100)//10
d=s-a*1000-b*100-c*10
if a==b :
    print("Bad")
elif b==c:
    print("Bad")
elif c==d:
    print("Bad")
else:
    print("Good")
S = input()
K = int(input())

if len(S) <= K :
    print(S)
else :
    print(S[:K] + "...")

### FIXED CODE ###

n = int(input()) % 10

if n in [2,4,5,7,9] :
    print("hon")
elif n in [0,1,6,8] :
    print("pon")
else  :
    print("bon")
N = int(input())
Ai = input()
Ai = Ai.split(' ')
ans = 'APPROVED'
for moji in Ai:
    if moji % 2 != 0:
        pass
    else:
        if (moji % 3 == 0) or (moji % 5 == 0):
            pass
        else:
            ans = 'DENIED'
            break
print(ans)


### FIXED CODE ###

N = int(input())
Ai = input()
Ai = Ai.split(' ')
ans = 'APPROVED'
for moji in Ai:
    moji = int(moji)
    if moji % 2 != 0:
        pass
    else:
        if (moji % 3 == 0) or (moji % 5 == 0):
            pass
        else:
            ans = 'DENIED'
            break
print(ans)
N = 23
B = "00110111001011011001110"

B_array = np.array(list(map(int, list(B))))
B_1 = B_array.sum()
mod_list_m1 = []
mod_list = []
mod_list_p1 = []
for i in range(N):
    mod_list.append((2**i) % (B_1))
    mod_list_m1.append((2**i) % (B_1-1))
    mod_list_p1.append((2**i) % (B_1+1))
mod_list = np.array(mod_list)[::-1]
mod_list_m1 = np.array(mod_list_m1)[::-1]
mod_list_p1 = np.array(mod_list_p1)[::-1]

def calc_small(n, iter):
    
    iter += 1
    mod = n % bin(n).count("1")
    if mod == 0:
        return iter
    else:
        return calc_small(mod, iter)

for i in range(N):
    Z_array = B_array.copy()
    Z_array[i] = 1 if B_array[i] == 0 else 0
    if Z_array.sum() == 0:
        print(1)
        continue
    mod = Z_array.dot(mod_list_p1) % (B_1+1) if B_array[i] == 0 else Z_array.dot(mod_list_m1) % (B_1-1)
    iter = 1
    if mod == 0:
        print(iter)
    else:
        print(calc_small(mod, iter))
    



### FIXED CODE ###

N = int(input())
B = input()

B_1 = B.count("1")
mod_p1 = int(B,2) % (B_1+1)
if B_1 != 1:
    mod_m1 = int(B,2) % (B_1-1)

def calc_small(n, iter):
    iter += 1
    mod = n % bin(n).count("1")

    if mod == 0:
        return iter
    else:
        return calc_small(mod, iter)

for i in range(N):
    if B_1 == 1 and int(B[i]) == 1:
        print(0)
        continue
    mod = (mod_m1 - pow(2,N-i-1,B_1-1)) % (B_1-1) if int(B[i]) == 1 else (mod_p1 + pow(2,N-i-1,B_1+1)) % (B_1+1)
    iter = 1
    if mod == 0:
        print(iter)
    else:
        print(calc_small(mod, iter))
S=input()
if S.count("o")+(15-len(S)>=8:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

S=input()
if S.count("o")+(15-len(S))>=8:
  print("YES")
else:
  print("NO")
n = int(input())

graph = [[] for i in range(n)]
for i in range(1,n):
    a,b = map(int,input().split())
    graph[a-1].append([b,i])


ans = [0]*(n-1)

def col(now,color):
    c = 1
    for [b,j] in graph[now-1]:
        if c == color:
            c += 1
        ans[j-1] = c
        col(b,c)
        c += 1  

col(1,0)
print(max(ans))
for i in range(1,n):
    print(ans[i-1])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

n = int(input())

graph = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    graph[a].append([b,i])

    
ans = [0]*(n-1)

def col(now,color):
    c = 1
    for (b,j) in graph[now]:
        if c == color:
            c += 1
        ans[j] = c
        col(b,c)
        c += 1

col(0,0)
print(max(ans))
for a in ans:
    print(a)
N = int(input())
A = map(int,input().split())
for a in A:
  if a % 2 == 0 and A % 3 != 0 and A % 5 != 0:
    print('DENIED')
    exit()
print('APPROVED')

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
for i in range(N):
    if(A[i] % 2 == 0 and A[i] % 3 != 0 and A[i] % 5 != 0):
        print('DENIED')
        exit()
print('APPROVED')
# -*- coding: utf-8 -*-

def dfs(num, dem, k, cur_num, prd, p, q, a, n):

    #print num, dem, k, cur_num, prd
    #time.sleep(0.5)
    if num == 0:
        #print "result: " + str(result)
        return 1

    result = 0


    while prd * i <= a:
        #print i, num, dem, k, cur_num, prd
        if (n - k) * dem < num * i:
            break
        # if num * i < dem:
        #     i += 1
        #     continue

        result += dfs((num * i) - dem, dem * i, k + 1, i, prd * i, p, q, a, n)
        i += 1

    return result

def func():
    while True:

        p, q, a, n = map(int, raw_input().split())

        if p == 0 and q == 0 and a == 0 and n == 0:
            break

        print dfs(p, q, 0, 1, 1, p, q, a, n)
        
    return None

if __name__ == '__main__':
    func()
    

### FIXED CODE ###

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

def dfs(num, dem, k, cur_num, prd, p, q, a, n):

    #print num, dem, k, cur_num, prd
    #time.sleep(0.5)
    if num == 0:
        #print "result: " + str(result)
        return 1

    result = 0

    i = cur_num
    while prd * i <= a:
        #print i, num, dem, k, cur_num, prd
        if (n - k) * dem < num * i:
            break
        if num * i < dem:
            i += 1
            continue

        result += dfs((num * i) - dem, dem * i, k + 1, i, prd * i, p, q, a, n)
        i += 1

    return result

def func():
    while True:

        p, q, a, n = map(int, raw_input().split())

        if p == 0 and q == 0 and a == 0 and n == 0:
            break

        print dfs(p, q, 0, 1, 1, p, q, a, n)
        
    return None

if __name__ == '__main__':
    func()
s = list(input())
for i in range(len(s)):
    if s[i] == "C":
        c = True
    elif c and s[i] == "F":
        print("Yes")
        exit()
print("No")

### FIXED CODE ###

s = list(input())
c = False
for i in range(len(s)):
    if s[i] == "C":
        c = True
    elif c and s[i] == "F":
        print("Yes")
        exit()
print("No")
import sys 
cnt =1
while 1:
    x = sys.stdin.readline().strip()
    if x == "0":
        break:
    print("Case %d: %s"%(cnt,x))
    cnt+=1

### FIXED CODE ###

import sys 

cnt =1

while 1:
    x = sys.stdin.readline().strip()
    if x == "0":
        break

    print("Case %d: %s"%(cnt,x))
    cnt+=1
import sys; readline = sys.stdin.readline
from collections import deque

t1, t2 = map(int, readline().split())
a1, a2 = map(int, readline().split())
b1, b2 = map(int, readline().split())

T = t1 + t2

avgA = t1 * a1 + t2 * a2
avgB = t1 * b1 + t2 * b2
if avgA == avgB :
    print('infinity')
    exit(0)

if avgA < avgB:
    a1, a2, b1, b2 = b1, b2, a1, a2
    avgA, avgB = avgB, avgA

d1 = a1 - b1
d2 = a2 - b2

if d1 > 0:
    print(0)
    exit(1)

y0 =  -d1 * t1
dy = (avgA - avgB)

n = y0 // dy

if y0 % dy == 0:
    print((n + 1) * 2 - 2)
else:
    print((n + 1) * 2 - 1)

### FIXED CODE ###

import sys; readline = sys.stdin.readline
from collections import deque

t1, t2 = map(int, readline().split())
a1, a2 = map(int, readline().split())
b1, b2 = map(int, readline().split())

T = t1 + t2

avgA = t1 * a1 + t2 * a2
avgB = t1 * b1 + t2 * b2
if avgA == avgB:
    print('infinity')
    exit(0)

if avgA < avgB:
    a1, a2, b1, b2 = b1, b2, a1, a2
    avgA, avgB = avgB, avgA

d1 = a1 - b1
d2 = a2 - b2

if d1 > 0:
    print(0)
    exit(0)

y0 =  -d1 * t1
dy = (avgA - avgB)

n = y0 // dy

if y0 % dy == 0:
    print((n + 1) * 2 - 2)
else:
    print((n + 1) * 2 - 1)
n = int(input())
A = list(map(int, input().split()))
R = [0 for i in range(9)]
for i in range(n):
    R[A[i]//400] += 1
mi = 0
for i in range(8):
    if R[i] > 0: mi += 1
if mi == 0 and R[8] > 0:
    print(mi+1, min(8, mi+R[8]))
else:
    print(mi, min(8, mi+R[8]))

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
R = [0 for i in range(9)]
for i in range(n):
    if A[i] < 3200: R[A[i]//400] += 1
    else: R[8] += 1
mi = 0
for i in range(8):
    if R[i] > 0: mi += 1
if mi == 0 and R[8] > 0:
    print(mi+1, mi+R[8])
else:
    print(mi, mi+R[8])