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

s = input()
X, Y = map(int, input().split())
fs = s.split("T")
nsx = list(map(len, fs[0::2]))
nsy = list(map(len, fs[1::2]))
xs = set()
q = [(nsx[0], 1)]
while q:
  x, i = q.pop()
  if i == len(nsx):
    xs.add(x)
  else:
    q.append((x+nsx[i], i+1))
    q.append((x-nsx[i], i+1))
ys = set()
q = [(0, 0)]
while q:
  y, i = q.pop()
  if i == len(nsy):
    ys.add(y)
  else:
    q.append((y+nsy[i], i+1))
    q.append((y-nsy[i], i+1))
#print(xs, ys)
if X in xs and Y in ys:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

s = input()
X, Y = map(int, input().split())
fs = s.split("T")
nsx = list(map(len, fs[0::2]))
nsy = list(map(len, fs[1::2]))
ssx = []
ssx.append({ 0 })
ssx.append({ nsx[0] })
for i in range(1, len(nsx)):
  s = ssx[i]
  n = nsx[i]
  s2 = set()
  for x in s:
    s2.add(x+n)
    s2.add(x-n)
  ssx.append(s2)
#print(ssx)
ssy = [{ 0 }]
for i in range(0, len(nsy)):
  s = ssy[i]
  n = nsy[i]
  s2 = set()
  for y in s:
    s2.add(y+n)
    s2.add(y-n)
  ssy.append(s2)
#print(ssy)
if X in ssx[-1] and Y in ssy[-1]:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

N,M=map(int,input().split())
import math
a=[]
ans=1
def calc(n):#nの素因数分解
    for i in range(2,int(n**0.5)+10):
        count=0
        while n%i==0:
            n//=i
            count+=1
        if count>=1:
            a.append([i,count])
    if n!=1:
        a.append([n,1])
def conb(n,k):
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
calc(M)
for i in range(len(a)):
    ans*=conb(a[i][1]+N-1,a[i][1])
print(ans%(10**9+7))

### FIXED CODE ###

N,M=map(int,input().split())
a=[]
ans=1
def calc(n):#nの素因数分解
    for i in range(2,int(n**0.5)+10):
        count=0
        while n%i==0:
            n//=i
            count+=1
        if count>=1:
            a.append([i,count])
    if n!=1:
        a.append([n,1])
calc(M)
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
for i in range(len(a)):
    ans*=cmb(a[i][1]+N-1,a[i][1])
print(ans%(10**9+7))
### BUGGY CODE ###

A,B,C=map(int,input().split())
K=int(input())
while K>0:
  while B<=A:
    B*=2
    K-=1
  while C<=B:
    C*=2
    K-=1
if K>=0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

A,B,C=map(int,input().split())
K=int(input())
while B<=A:
  B*=2
  K-=1
while C<=B:
  C*=2
  K-=1
if K>=0:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

import itertools

N = input().split()
N = [int(i) for i in N]
num = [i for i in range(N[0]+1)]

count = 0

#1
for i in range(N[0]+1):
    if(3*i == N[1]):
        count += 1

l2 = list(itertools.combinations(num, 2))
l3 = list(itertools.combinations(num, 3))
#print(num)
#print(l2)

#2
for i in range(len(l2)):
    if((l2[i][0] + 2*l2[i][1]) == N[1]):
        count += 1*3
    if((l2[i][0]*2 + l2[i][1]) == N[1]):
        count += 1*3

#3
for i in range(len(l3)):
    if((l3[i][0] + l3[i][1] + l3[i][2]) == N[1]):
        count += 1*6

print(count)


### FIXED CODE ###

N = input().split()
N = [int(i) for i in N]
count = 0
for i in range(N[0]+1):
    for j in range(N[0]+1):
        k = N[1] - i - j
        if((k <= N[0])and(k>=0)):
            count += 1
print(count)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
ref = 1

for i in range(k):
    ref *= a[i]

for i in range(n - k):
    ref2 = ref*a[i + k]/a[i]
    if ref2 > ref:
        print("Yes")
    else:
        print("No")
    ref = ref2

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))

for i in range(n - k):
    if a[i + k] > a[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n = int(input())
x = input()

x0 = int('0b'+x,0)

ceil = 2*10**5+2
ppc = [0]*(ceil)

def popcount(n):    
  if n == 0:
    return 0
  if ppc[n] != 0:
    return ppc[n]
    
  b = bin(n).count('1')  
  tmp = n%b
  ppc[n] = popcount(tmp) + 1
  return ppc[n]

c1 = bin(x0).count('1')  
p = 1
ans = []
for i in range(n):  
  if x[n-i-1] == '1':    
    tmp = x0 - p
    if c1-1 == 0:
      tmp = 0
    else:
      tmp2 = tmp % (c1 - 1)
  else:
    tmp = x0 + p  
    tmp2 = tmp % (c1 + 1)
    
  if tmp > ceil:      
    ans.append(popcount(tmp2)+1)    
  else:
    ans.append(popcount(tmp))    
  p *= 2
  

for i in range(n):
  print(ans[-1-i])

### FIXED CODE ###

n = int(input())
X = input()

def goes_to_zero(n):
  cnt = 0
  while(n > 0):
    n %= bin(n).count('1')
    cnt += 1
  return cnt
  
c1 = X.count('1')
xint = int(X,2)
xtp = xint % (c1 + 1)
if (c1 - 1) == 0:  
  xtm = 0
else:
  xtm = xint % (c1 - 1)
  
for i in range(n)  :
  if X[i] == '0':
    print(goes_to_zero( (xtp + pow(2,n-1-i,(c1+1))) % (c1+1) ) + 1)
  else:
    if (c1-1) == 0:
      print(0)
    else:
      print(goes_to_zero( (xtm - pow(2,n-1-i,(c1-1)) ) % (c1-1) ) +1)
### BUGGY CODE ###

N, u, v = map(int, input().split())
u, v = u-1, v-1
AB = [list(map(int, input().split())) for a in range(N-1)]

G = [[0 for b in range(N)] for a in range(N)]
D = [[0 for b in range(N)] for a in range(N)]

for ab in AB:
  G[ab[0]-1][ab[1]-1] = 1
  G[ab[1]-1][ab[0]-1] = 1

def dfs(current, goal, distance, prev):
  if current == goal:
    return distance
  if 0 < D[current][goal] :
    return D[current][goal]
  if 0 < D[goal][current] :
    return D[goal][current]
  dists = [0]
  for i in range(N):
    if G[current][i] == 1 and i != prev and i != current:
      dists.append(dfs(i, goal, distance + 1, current))
  D[goal][current] = max(dists)
  D[current][goal] = D[goal][current]
  return D[current][goal]

distances = [0]
for i in range(N):
  count = 0
  for j in range(N):
    if G[i][j] == 1:
      count += 1
  if count == 1:
    aoki = dfs(i, v, 0, -1)
    takahashi = dfs(i, u, 0, -1)
    if aoki > takahashi:
      distances.append(dfs(i, v, 0, -1))

print(max(distances)-1)


### FIXED CODE ###

from collections import deque
N, u, v = map(int, input().split())
u, v = u-1, v-1
AB = [list(map(int, input().split())) for a in range(N-1)]

G = [[] for a in range(N)]

for ab in AB:
  G[ab[0]-1].append(ab[1]-1)
  G[ab[1]-1].append(ab[0]-1)

qA = deque([v])
qT = deque([u])
costsA = [0 for a in range(N)]
doneA = [0 for a in range(N)]
costsT = [0 for a in range(N)]
doneT = [0 for a in range(N)]

doneA[v] = 1
doneT[u] = 1

def bfs(q, costs, done):
  while q:
    start = q.popleft()
    for i in G[start]:
      if done[i] == 0:
        q.append(i)
        costs[i] = costs[start] + 1
        done[i] = 1

bfs(qA, costsA, doneA)
bfs(qT, costsT, doneT)

distances = [0]
for i in range(N):
  if costsA[i] > costsT[i]:
    distances.append(costsA[i])

print(max(distances)-1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys

def main():
	Q = int(input())
	maps = []
	r_max = 0
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		maps.append((l, r))
		if r_max < r:
			r_max = r
			
	marix = getPrimeNumList(r_max)
	tergets = []
	for i in marix:
		if (i+1) % 2 == 0:
			tmp = (i+1) / 2
			if tmp in marix:
				tergets.append(i)
				
	base = [0] * (r_max+1)
	counts = 0
	for i in range(r_max+1):
		if i == 0:
			continue
		if i in marix and (i+1) % 2 == 0:
			tmp = (i+1) / 2
			if tmp in marix:
				counts += 1
		base[i] = counts
			
	
	for i in maps:
		l, r = i
		#print(base)
		print(base[r] - base[l-1])
			
				
		
def getPrimeNumList(n):
	is_prime = [True] * (n + 1)
	is_prime[0] = False
	is_prime[1] = False
	for i in range(2, int(n**0.5) + 1):
		if not is_prime[i]:
			continue
		for j in range(i * 2, n + 1, i):
			is_prime[j] = False
	return [i for i in range(n + 1) if is_prime[i]]
	
if __name__ == "__main__":
	main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import random

def main():
	Q = int(input())
	maps = []
	r_max = 0
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		maps.append((l, r))
		if r_max < r:
			r_max = r
			
	#marix = getPrimeNumList(r_max)
				
	base = [0] * (r_max+1)
	counts = 0
	for i in range(r_max+1):
		if i == 0 or i == 1:
			continue
		if (i+1) % 2 == 0 and is_prime(i) == True:
			tmp = (i+1) / 2
			if is_prime(tmp) == True:
				counts += 1
		base[i] = counts
			
	
	for i in maps:
		l, r = i
		print(base[r] - base[l-1])
			
		
def getPrimeNumList(n):
	is_prime = [True] * (n + 1)
	is_prime[0] = False
	is_prime[1] = False
	for i in range(2, int(n**0.5) + 1):
		if not is_prime[i]:
			continue
		for j in range(i * 2, n + 1, i):
			is_prime[j] = False
	return [i for i in range(n + 1) if is_prime[i]]
	
def is_prime(n): 
  i = 2
  while i * i <=n:
    if n % i == 0:
      return False
    i += 1
  return True
	
if __name__ == "__main__":
	main()
### BUGGY CODE ###




import fractions


mod = 1000000007

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def modpower(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def powerX(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 
    else            : return power(x, y//2)**2 * x

def power(x,y):
    return x ** y


def div(a, b):
    return mul(a, modpower(b, mod-2))

H,W,T = map(int,input().split())

htgcd = fractions.gcd(H,T)
wtgcd = fractions.gcd(W,T)
n = htgcd * wtgcd

p = ( power(2, ( H // htgcd)) + power(2, (W // wtgcd)) - 3)
p += power(2 , fractions.gcd( H // htgcd , W // wtgcd))

#print (p,n)

ans = modpower(p , n)

print (ans)


### FIXED CODE ###




import fractions


mod = 1000000007

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def modpower(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def powerX(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 
    else            : return power(x, y//2)**2 * x

def power(x,y):
    return x ** y


def div(a, b):
    return mul(a, modpower(b, mod-2))

H,W,T = map(int,input().split())

htgcd = fractions.gcd(H,T)
wtgcd = fractions.gcd(W,T)
n = htgcd * wtgcd

p = pow( 2, ( H // htgcd) ,mod ) +pow( 2, (W // wtgcd) , mod) - 3
p += pow(2,fractions.gcd( H // htgcd , W // wtgcd),mod)

#print (p,n)

ans = pow( p , n , mod )

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

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

AA = { i: a for i, a in enumerate(A)}

def f(i):
    total = 0
    for j in range(N):
        total += AA[(i + j) % N] * (1 if j % 2 == 0 else -1)
    return total

B = [f(i) for i in range(N)]

print(*B)

# A[0] = B[0] // 2 + B[1] // 2
# A[1] = B[1] // 2 + B[2] // 2
# A[2] = B[2] // 2 + B[3] // 2
# A[3] = B[3] // 2 + B[4] // 2
# A[4] = B[4] // 2 + B[0] // 2

# A[0] - A[1] = (B[0] - B[2]) // 2
# A[1] - A[2] = (B[1] - B[3]) // 2
# A[2] - A[3] = (B[2] - B[4]) // 2
# A[3] - A[4] = (B[3] - B[0]) // 2
# A[4] - A[0] - (B[4] - B[1]) // 2

# A[0] - A[1] + A[2] - A[3] + A[4] = B[0]
# A[1] - A[2] + A[3] - A[4] + A[0] = B[1]
# A[2] - A[3] + A[4] - A[0] + A[1] = B[2]
# A[3] - A[4] + A[0] - A[1] + A[2] = B[3]


### FIXED CODE ###

from functools import lru_cache
N = int(input())
A = list(map(int, input().split()))

@lru_cache(maxsize=N)
def f(i):
    if i >= 2:
        return f(i - 2) + 2 * A[i - 1] - 2 * A[i - 2]
    total = 0
    for j in range(N):
        if j % 2 == 0:
            total += A[(i + j) % N]
        else:
            total -= A[(i + j) % N]
    return total

B = (f(i) for i in range(N))

print(*B)
### BUGGY CODE ###

# D
import math
S = input()
SS = list(S)
index_num_kugiri = [-1]
index_num_soko = []
for i in range(len(SS) - 1):
    if SS[i] == 'L' and SS[i+1] == 'R':
        index_num_kugiri.append(i)
    if SS[i] == 'R' and SS[i+1] == 'L':
        index_num_soko.append(i)
index_num_kugiri.append(len(S)- 1)
ans = []
for k in range(0, len(index_num_soko)):
    if index_num_soko[k] % 2 == index_num_kugiri[k+1]  % 2:
        tmp1 = math.ceil((index_num_kugiri[k+1] - index_num_kugiri[k] ) / 2)
        tmp2 = index_num_kugiri[k+1] - index_num_kugiri[k]  - tmp1
    else:
        tmp1 = math.floor((index_num_kugiri[k+1] - index_num_kugiri[k] ) / 2)
        tmp2 = index_num_kugiri[k+1] - index_num_kugiri[k]  - tmp1
    ans.append([index_num_soko[k], tmp1])
    ans.append([index_num_soko[k], tmp2])
tugi = False
tmp = 0
final_ans = []
for i in range(len(S)):
    if tugi:
        tugi = False
        final_ans.append(ans[tmp][1])
        tmp += 1
        continue
    if i in index_num_soko:
        final_ans.append(ans[tmp][1])
        tmp += 1
        tugi = True
        continue
    else:
        final_ans.append(0)
        
print(' '.join(map(str, final_ans)))

### FIXED CODE ###

# D
import math
S = input()
SS = list(S)
index_num_kugiri = [-1]
index_num_soko = []
for i in range(len(SS) - 1):
    if SS[i] == 'L' and SS[i+1] == 'R':
        index_num_kugiri.append(i)
    if SS[i] == 'R' and SS[i+1] == 'L':
        index_num_soko.append(i)
index_num_kugiri.append(len(S)- 1)
ans = []
for k in range(0, len(index_num_soko)):
    if index_num_soko[k] % 2 == index_num_kugiri[k]  % 2:
        tmp1 = math.floor((index_num_kugiri[k+1] - index_num_kugiri[k] ) / 2)
        tmp2 = index_num_kugiri[k+1] - index_num_kugiri[k]  - tmp1
    else:
        tmp1 = math.ceil((index_num_kugiri[k+1] - index_num_kugiri[k] ) / 2)
        tmp2 = index_num_kugiri[k+1] - index_num_kugiri[k]  - tmp1
    ans.append([index_num_soko[k], tmp1])
    ans.append([index_num_soko[k], tmp2])
tugi = False
tmp = 0
final_ans = []
for i in range(len(S)):
    if tugi:
        tugi = False
        final_ans.append(ans[tmp][1])
        tmp += 1
        continue
    if i in index_num_soko:
        final_ans.append(ans[tmp][1])
        tmp += 1
        tugi = True
        continue
    else:
        final_ans.append(0)
        
print(' '.join(map(str, final_ans)))
### BUGGY CODE ###

s=input()
q=int(input())
for c in range(q):
    l=input()
    if l=="1":
        s=s[::-1]
    else:
        if l[2]=="1":
            s=l[4:]+s
        else:
            s=s+l[4:]
print(s)

### FIXED CODE ###

s=input()
q=int(input())
l=[]
for c in range(q):
    i=input().split()
    if i==["1"]:
        l.append([1,0,0])
    else:
        l.append([2,int(i[1]),i[2]])
d=0
for c in range(1,q+1):
    if l[-c][0]==1:
        d=d+1
    else:
        l[-c][1]+=d%2
a=""
for c in range(1,q+1):
    if l[-c][0]==2 and l[-c][1]%2==1:
        a=a+l[-c][2]
if d%2==0:
    a=a+s
else:
    a=a+s[::-1]
for c in range(q):
    if l[c][0]==2 and l[c][1]%2==0:
        a=a+l[c][2]
print(a)
### BUGGY CODE ###

n=int(input())
s=input()
count=0
import itertools
for i in range(1,n+1):
    combs=list(itertools.combinations(s,i))
    for comb in combs:
        if len(comb)==len(set(comb)):
            count+=1
print(count%(10**9+7))

### FIXED CODE ###

n=int(input())
s=input()

abc = "abcdefghijklmnopqrstuvwxyz"

ans = 1
for i in abc:
    ans *= s.count(i)+1
print((ans-1)%(10**9+7))
### BUGGY CODE ###

import bisect
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort()
b.sort()
c.sort()

ab=[]
bc=[]
for i in range(n):
    ab.append(bisect.bisect_left(a, b[i]))
    bc.append(bisect.bisect_left(b, c[i]))

ans=0
for i in bc:
    ans+=sum(ab[:i])

print(ans)

### FIXED CODE ###

import bisect
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort()
c.sort()

ans=0
for i in b:
    up=bisect.bisect_left(a, i)
    dn=n-bisect.bisect_right(c, i)
    ans+=up*dn

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

n,m= map(int,input().split())
A = list(map(int,input().split()))
B = []
for _ in range(m):
  b,c = map(int,input().split())
  B += [c]*b
A.sort()
B.sort(reverse=True)
B += [0]*n
c = 0
for i in range(n):
  c += max(A[i],B[i])
print(c)

### FIXED CODE ###

n,m= map(int,input().split())
AA = list(map(int,input().split()))
A = [(AA[i],1) for i in range(n)]
for _ in range(m):
  b,c = map(int,input().split())
  A += [(c,b)]
A.sort()
A.reverse()
rest = n
score = 0
for (cc,bb) in A:
  use = min(bb,rest)
  rest -= use
  score += use*cc
print(score)
### BUGGY CODE ###

N,W = map(int,input().split())
array = [[0] * (W+1) for i in range((N+1))]
for i in range(N):
  wei,V = map(int,input().split())
  for j in range(W):
    if(wei<=j+1):
      if(array[i][j] < array[i][j-wei+1]+V):
        array[i+1][j+1]=array[i][j-wei+1]+V
      else:
        array[i+1][j+1]=array[i][j+1]
    else:
      array[i+1][j+1]=array[i][j+1]
print(array[N][W])

### FIXED CODE ###

N,W = map(int,input().split())
array = [[0] * (W+1) for i in range((N+1))]
for i in range(N):
  wei,V = map(int,input().split())
  for j in range(W):
    if(wei<=j+1):
      if(array[i][j] < array[i][j-wei+1]+V):
        array[i+1][j+1]=array[i][j-wei+1]+V
      else:
        array[i+1][j+1]=array[i][j+1]
    else:
      array[i+1][j+1]=array[i][j+1]
print(array[N][W])
### BUGGY CODE ###

from heapq import heappop, heappush
mod = 10**9+7
n, k = map(int, input().split())
a = [int(x) for x in input().split()]

pl = []
mn = []
zr = []

tmp = 1
cnt = 0

for x in a:
    if x > 0:
        pl.append(x)
    elif x < 0:
        mn.append(-x)
    else:
        zr.append(x)

pl = sorted(pl, reverse=True)
mn = sorted(mn, reverse=True)

ans = 0

if len(mn) >= k and k % 2:
    tmp = 1
    for i in range(1, k+1):
        tmp *= mn[-i]
    ans = -tmp

if len(zr) > 0:
    ans = max(0, ans)

pl_cum = [1]
for i, x in enumerate(pl):
    pl_cum.append(pl_cum[-1]*x)

mn_cum = [1]
for i, x in enumerate(mn):
    mn_cum.append(mn_cum[-1]*x)

for p in range(0, k+1, 2):
    if len(mn) < p:
        break
    if len(pl) >= k-p:
        ans = max(pl_cum[k-p]*mn_cum[p], ans)

print(ans % mod)


### FIXED CODE ###

from heapq import heappop, heappush
mod = 10**9+7
n, k = map(int, input().split())
a = [int(x) for x in input().split()]


def sgn(x):
    if x >= 0:
        return 0
    elif x < 0:
        return 1


pl = []
mn = []

for x in a:
    if x >= 0:
        pl.append(x)
    elif x < 0:
        mn.append(-x)

pl = sorted(pl, reverse=True)
mn = sorted(mn, reverse=True)


b = [(abs(a[i]), sgn(a[i])) for i in range(n)]
b = sorted(b, reverse=True)

c = [0, 0]
for i in range(k):
    c[b[i][1]] += 1


def solve(c):
    ans = 1
    for i in range(c[0]):
        ans *= pl[i]
        ans %= mod
    for i in range(c[1]):
        ans *= mn[i]
        ans %= mod
    if c[1] % 2:
        ans = (-ans) % mod
    return ans


if c[1] % 2 == 0:
    print(solve(c))
    exit()

if len(mn) == n and k % 2:
    tmp = 1
    for i in range(k):
        tmp *= mn[-i-1]
        tmp %= mod
    ans = -tmp
    print(ans % mod)
    exit()

ans = 0

chk1 = False
chk2 = False

if c[0] <= len(pl) - 1:
    chk1 = True

if 0 < c[0] and c[1] <= len(mn)-1:
    chk2 = True

if chk1 and chk2:
    tmp1 = pl[c[0]]*pl[c[0]-1]
    tmp2 = mn[c[1]]*mn[c[1]-1]
    if tmp1 > tmp2:
        c[0] += 1
        c[1] -= 1
        print(solve(c))
    else:
        c[0] -= 1
        c[1] += 1
        print(solve(c))
elif chk1:
    c[0] += 1
    c[1] -= 1
    print(solve(c))
elif chk2:
    c[0] -= 1
    c[1] += 1
    print(solve(c))
else:
    print(solve(c))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import numpy as np

N = int(input())

A = list(map(int,input().split()))
B = A
ct = 0

for i in range(N):
    j = N-i-1
    if(j+1>N/2):
        B[j] = A[j]
        if(B[j]==1):
            ct = ct + 1
    else:
        for k in range(j+1,N):
            sum = 0
            if(k%(j+1)==0 and k!=j):
                sum = sum + B[k];
        if(sum%2==0):
            B[j] = A[j]
            if(B[j]==1):
                ct = ct + 1
        else:
            B[j] = 1 - A[j]
            if(B[j]==1):
                ct = ct + 1

print(ct)
C = []

for i in range(N):
    if(B[i]==1):
        C.append(i+1)
print(*C)



### FIXED CODE ###

# coding: utf-8
# Your code here!
import numpy as np

N = int(input())

A = list(map(int,input().split()))
B = A
ct = 0

for i in range(N):
    j = N-i-1
    if(j+1>N/2):
        B[j] = A[j]
        
        if(B[j]==1):
            ct = ct + 1
    else:
        sum = 0
        for k in range(j+1,N+1,j+1):
            if(k%(j+1)==0 and k!=j+1):
                
                sum = sum + B[k-1]
        if(sum%2==0):
            B[j] = A[j]
            if(B[j]==1):
                ct = ct + 1
        else:
            B[j] = 1 - A[j]
            
            if(B[j]==1):
                ct = ct + 1
        

print(ct)
C = []

for i in range(N):
    if(B[i]==1):
        C.append(i+1)
print(*C)
### BUGGY CODE ###

k=0
s=0
combi = 0

def nyu():
    num1,num2 = input().split()
    k = int(num1)
    s = int(num2)
    return k,s

def calc(l_k,l_s):
    l_combi = 0
    
    for x in range(l_k):
        for y in range(l_k):
            for z in range(l_k):
     #           print("x=",x,"y=",y,"z=",z)
                sum = x+y+z
                if l_s == sum:
                    l_combi +=1
                    
    return l_combi

k,s=nyu()
print(calc(k+1,s))









### FIXED CODE ###

k=0
s=0
combi = 0

def nyu():
    num1,num2 = input().split()
    k = int(num1)
    s = int(num2)
    return k,s

def calc(l_k,l_s):
    l_combi = 0
    for x in range(l_k):
#        check_tmp =0
#        check_tmp =check1(x,l_s,l_k)
#        if check_tmp == 1:
#            break
#        elif check_tmp  == 2:
#            continue
        for y in range(l_k):
#            check_tmp =check2(x,y,l_s,l_k)
#            if check_tmp == 1:
#                break
#            elif check_tmp  == 2:
#                continue2
#            sum = x+y+l_k 
            sum = l_s- x-y 
            if 0<=sum and sum <= k:
#                print("x=",x,"y="   ,y) 
                l_combi +=1
    return l_combi

def check1(x,s,k):
    if s<x:
        return 1
    if x+(k-1)*2 < s:
        return 2
    return 0

def check2(x,y,s,k):
    sum = x+y
    if s<sum:
        return 1
    if x+y+k-1 < s:
       return 2
    return 0

def check3(x,y,z,s):
    sum = x+y+z
    if s<sum:
        return 1
    return 0    

def check_ini(k,s):
    if k*3 < s:
        return True
    return False


k,s=nyu()
if check_ini == True:
    print("0")
else :
    print(calc(k+1,s))
### BUGGY CODE ###

import sys
sys.stdin.readline

def digitsum(b, n):
    ans = 0
    while n:
        n, m = divmod(n, b)
        ans += m
    return ans

def main():
    n = int(input())
    s = int(input())
    if s == n:
        print(n+1)
        return
    if s > n:
        print(-1)
        return
    for b in range(2, int(n**.5)+1):
        if digitsum(b, n) == s:
            print(b)
            return
    ans = float("inf")
    for d in range(1, int(n**.5)+1):
        b = (n - s) // d + 1
        if digitsum(b, n) == s:
            ans = min(ans, b)
    if ans == float("inf"):
        ans = -1
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.stdin.readline
INF = float("inf")

def digitsum(b, n):
    ans = 0
    while n:
        n, m = divmod(n, b)
        ans += m
    return ans

def solve():
    n = int(input())
    s = int(input())
    if s == n: return n+1
    if s > n: return -1
    for b in range(2, int(n**.5)+1):
        if digitsum(b, n) == s: return b
    ans = INF
    for d in range(1, int(n**.5)+1):
        b = (n - s) // d + 1
        if b < 2: continue
        if digitsum(b, n) == s:
            ans = min(ans, b)
    if ans == INF:
        ans = -1
    return ans

if __name__ == "__main__":
    print(solve())