Masha really loves algebra. On the last lesson, her strict teacher Dvastan gave she new exercise.

You are given geometric progression b defined by two integers b_1 and q. Remind that a geometric progression is a sequence of integers b_1, b_2, b_3, ..., where for each i > 1 the respective term satisfies the condition b_{i} = b_{i} - 1·q, where q is called the common ratio of the progression. Progressions in Uzhlyandia are unusual: both b_1 and q can equal 0. Also, Dvastan gave Masha m "bad" integers a_1, a_2, ..., a_{m}, and an integer l.

Masha writes all progression terms one by one onto the board (including repetitive) while condition |b_{i}| ≤ l is satisfied (|x| means absolute value of x). There is an exception: if a term equals one of the "bad" integers, Masha skips it (doesn't write onto the board) and moves forward to the next term.

But the lesson is going to end soon, so Masha has to calculate how many integers will be written on the board. In order not to get into depression, Masha asked you for help: help her calculate how many numbers she will write, or print "inf" in case she needs to write infinitely many integers.


-----Input-----

The first line of input contains four integers b_1, q, l, m (-10^9 ≤ b_1, q ≤ 10^9, 1 ≤ l ≤ 10^9, 1 ≤ m ≤ 10^5) — the initial term and the common ratio of progression, absolute value of maximal number that can be written on the board and the number of "bad" integers, respectively.

The second line contains m distinct integers a_1, a_2, ..., a_{m} (-10^9 ≤ a_{i} ≤ 10^9) — numbers that will never be written on the board.


-----Output-----

Print the only integer, meaning the number of progression terms that will be written on the board if it is finite, or "inf" (without quotes) otherwise.


-----Examples-----
Input
3 2 30 4
6 14 25 48

Output
3
Input
123 1 2143435 4
123 11 -5453 141245

Output
0
Input
123 1 2143435 4
54343 -13 6 124

Output
inf


-----Note-----

In the first sample case, Masha will write integers 3, 12, 24. Progression term 6 will be skipped because it is a "bad" integer. Terms bigger than 24 won't be written because they exceed l by absolute value.

In the second case, Masha won't write any number because all terms are equal 123 and this is a "bad" integer.

In the third case, Masha will write infinitely integers 123.

Difficulty: interview

Starter code:

Solutions:
def main():
    (b1, q, l, m) = list(map(int, input().split()))
    a = set(map(int, input().split()))
    if abs(b1) > l:
        print(0)
    else:
        if b1 == 0:
            if 0 in a:
                print(0)
            else:
                print("inf")
        elif q == 0:
            if 0 not in a:
                print("inf")
            elif b1 in a:
                print(0)
            else:
                print(1)
        elif q == 1:
            if b1 in a:
                print(0)
            else:
                print("inf")
        elif q == -1:
            if (b1 in a) and ((-b1) in a):
                print(0)
            else:
                print("inf")
        else:
            ans = 0
            b = b1
            for i in range(100):
                if b in a:
                    b *= q
                    if abs(b) > l:
                        break
                    continue
                ans += 1
                b *= q
                if abs(b) > l:
                    break
            print(ans)

def __starting_point():
    main()

__starting_point()

from sys import stdin, stdout

b, q, l, n = map(int, stdin.readline().split())
a = set(list(map(int, stdin.readline().split())))
ans = 0
ind = 0

while abs(b) <= l and ind < 100:
    if not b in a:
        ans += 1
            
    b *= q
    ind += 1
    
if ans > 40:
    stdout.write('inf')
else:
    stdout.write(str(ans))

b1, q, l, m = [int(i) for i in input().split()]

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

ans = 0

if abs(b1) > l:
    ans = 0
elif b1 == 0:
    ans = "inf" if 0 not in a else 0
else:
    ans = int(b1 not in a)
    if q == 0:
        if 0 not in a : ans = "inf"
    elif q == 1:
        if ans > 0 : ans = "inf"
    elif q == -1:
        if ans > 0 or -b1 not in a: ans = "inf"
    else:
        while 1:
            b1 *= q
            if abs(b1) > l: break
            ans += b1 not in a

print(ans)


import sys

def solve():
    b1, q, L, m = map(int, input().split())
    a = [int(i) for i in input().split()]

    a = set(a)

    if b1 == 0:
        print(0 if b1 in a else 'inf')
        return

    if q == 1:
        if abs(b1) > L or b1 in a:
            print(0)
        else:
            print('inf')
    elif q == -1:
        if abs(b1) > L or (b1 in a and -b1 in a):
            print(0)
        else:
            print('inf')
    elif q == 0:
        if abs(b1) > L:
            print(0)
        elif 0 in a:
            print(0 if b1 in a else 1)
        else:
            print('inf')
    else:
        b = b1
        ans = 0

        while abs(b) <= L:
            if b not in a:
                ans += 1
            b *= q

        print(ans)

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def __starting_point():
    solve()
__starting_point()


s, r, m, n = list(map(int, input().split()))
bad = set(map(int, input().split()))

cnt = 0

if abs(s) > m:
    print(0)
elif s == 0:
    if 0 in bad:
        print(0)
    else:
        print('inf')
elif r == 0 and s != 0:
    if 0 in bad or m < 0:
        if s in bad:
            print(0)
        else:
            print(1)
    else:
        print('inf')
elif r == 1:
    if s in bad:
        print(0)
    else:
        print('inf')
elif r == -1:
    if (s in bad) and (-s in bad):
        print(0)
    else:
        print('inf')
elif -1 <= r <= 1 and r != 0:
    print('inf')
else:
    while abs(s) <= m:
        if s not in bad:
            cnt += 1
        s *= r
    print(cnt)


b, q, l, m = list(map(int, input().split()))
A = set(map(int, input().split()))

ans = 0
for _ in range(100):
    if abs(b) > l:
        break
    if b not in A:
        ans += 1
    b *= q
if ans > 40:
    print("inf")
else:
    print(ans)


b1,q,l,m = [int(i) for i in input().split()]
bad = [int(i) for i in input().split()]
if abs(q) > 1 and b1 != 0:
	b2 = b1
	count = 0
	while abs(b2) <= l:
		count += 1
		if b2 in bad:
			count-=1
		b2 *= q
		'''
	for u in bad:
		i = u

		while (i%q == 0):
			i = i / q
			a = i == b1
			if a:
				break
		a = i == b1

		if (a and abs(u)<=l) or u == b1:
			count-=1
	'''
	print(count)
else:
	'''
	if abs(b1)<=l:
		if q == 1:
			if b1 in bad:
				print("0")
			else:
				print("inf")
		elif q == 0:
			if 0 in bad:
				if b1 in bad:
					print("0")
				else:
					print("1")
			else:
				print("inf")
		elif q == -1:
			if (b1 in bad) and (b2 in bad):
				print("0")
			else:
				print("inf")

	else:
		print("0")
	'''
	a1 = b1 * q
	if abs(b1) <= l:
		if b1 == 0:
			if b1 in bad:
				print("0")
			else:
				print("inf")
		elif a1 in bad:
			if b1 in bad:
				print("0")
			else:
				if a1 == 0:
					print("1")
				else:
					print("inf")
		else:
			print("inf")
	else:
		print("0")

B1, Q, L, M = list(map(int, input().split()))
As = set(map(int, input().split()))

Bs = []
tmp = B1
cnt = 0
while abs(tmp) <= L and cnt < 100:
    if tmp not in As:
        Bs.append(tmp)
    tmp *= Q
    cnt += 1
if 32 < len(Bs):
    print('inf')
else:
    print(len(Bs))


a,r,l,m = list(map(int,input().split()))
_l = list(map(int,input().split()))
s = set(_l)
if(abs(a)>l):
    print(0)
    return
if(a==0):
    if(0 in s):
        print(0)
        return
    else:
        print("inf")
        return
if(r==0):
    if(a==0):
        if(0 in s):
            print(0)
            return
        else:
            print("inf")
            return
    else:
        if(a not in s):
            if(abs(a)<=l):
                if(0 in s):
                    print(1)
                    return
                else:
                    print("inf")
                    return
            else:
                print(0)
                return
        else:
            if(0 in s):
                print(0)
                return
            else:
                print("inf")
                return
if(r==1):
    if(a in s or abs(a)>l):
        print(0)
        return
    else:
        print("inf")
        return
if(r==-1):
    if(a in s):
        if(0-a in s):
            print(0)
            return
        else:
            if(abs(a)<=l):
                print("inf")
                return
            else:
                print(0)
                return
    else:
        if(abs(a)<=l):
            print("inf")
            return
        else:
            print(0)
            return
tot = 0
while(abs(a)<=l):
    if(a not in s):
        tot+=1
    a*=r
print(tot)


        



b1, q, l, m = map(int, input().split())
num1 = list(map(int, input().split()))
num = set(num1) 
if q == 1 and abs(b1) <= l: 
    if b1 in num: 
        print(0) 
    else:
        print("inf")
    return 
    
if q == -1 and abs(b1) <= l:
    if b1 in num: 
        if -b1 in num:
            print(0)
        else: 
            print("inf")
        return 
    print("inf")
    return
        
if q == 0 and abs(b1) <= l:
    if b1 in num:
        if 0 in num: 
            print(0)
        else: 
            print("inf") 
        return
    if 0 in num:
        print(1)
    else: 
        print("inf")
    return

if b1 == 0 and b1 <= l:
    if 0 in num: 
        print(0)
    else:
        print("inf") 
    return 
if b1 == 1 and (q == 1) and b1 <= l: 
    if 1 in num: 
        print(0)
    else:
        print("inf")
    return
if b1 == -1 and q == 1 and b1 <= l:
    if -1 in num: 
            print(0)
    else:
        print("inf")
    return    
if b1 == 1 and q == -1  and b1 <= l: 
    if 1 in num:
        if -1 in num: 
            print(0)
        else: 
            print("inf")
    else: 
        print("inf")
    return
if b1 == -1 and q == -1 and b1 <= l:
    if -1 in num:
        if 1 in num: 
            print(0)
        else: 
            print("inf")
    else: 
        print("inf")
        return    
ans = 0
while l >= abs(b1): 
    if b1 not in num: 
        ans += 1 
    b1 *= q
print(ans)

def solve():
    b1, q, l, m = map(int, input().split())
    bads = set(map(int, input().split()))
    
    terms = set()
    
    if b1 == 0:
        if 0 not in bads:
            print("inf")
        else:
            print(0)
    elif q == 0:
        if abs(b1) > l:
            print(0)
        else:
            if 0 not in bads:
                print("inf")
            else:
                if b1 not in bads:
                    print(1)
                else:
                    print(0)
    elif q == 1:
        if abs(b1) <= l:
            if b1 not in bads:
                print("inf")
            else:
                print(0)
        else:
            print(0)
    elif q == -1:
        if abs(b1) <= l:
            if b1 not in bads or -b1 not in bads:
                print("inf")
            else:
                print(0)
        else:
            print(0)
    else:
        b = b1
        while abs(b) <= l:
            terms.add(b)
            b *= q
        print(len(terms) - len(terms.intersection(bads)))

solve()

b, q, l, m = list(map(int, input().split()))
a = set(list(map(int, input().split())))
ans = 0
boo = False
i = 0
while (i < 34) and (abs(b) <= l):
    if (b not in a):
        ans += 1
        if i > 31:
            boo = True
    b *= q
    i += 1
if boo:
    print('inf')
else:
    print(ans)

a=input().split()
b=int(a[0])
q=int(a[1])
l=int(a[2])
m=int(a[3])
a=input().split()
t=0
if(b==0):
    if('0' in a):print(0)
    else:print("inf")
    
elif(abs(b)>l):print(0)
elif(abs(q)<=1 and q!=-1 and q!=0):
    if(str(b) in a):print(0)
    else:print("inf")
elif(q==(-1)):
    if(str(b) in a and str(-b) in a):print(0)
    else:print("inf")
elif(q==0):
    t=1
    if(str(b) in a):t=0;
    if(str(0) in a):print(t)
    else:print("inf")
else:
    t=0
    while(abs(b)<=l):
       if(not(str(b) in a)):t+=1
       b*=q
    print(t)
    


from sys import stdin

B1, Q, L, M = list(map(int, stdin.readline().split()))
bad = set(map(int, stdin.readline().split()))

if B1 == 0:
    if 0 in bad:
        print(0)
    else:
        print("inf")
elif abs(B1) <= L and abs(Q) <= 1:
    # inf or 0
    if Q == 0: # B1, 0, 0, ...
        if B1 in bad and 0 in bad:
            print(0)
        elif B1 in bad:
            print("inf")
        elif 0 in bad:
            print(1)
        else:
            print("inf")
    elif Q == 1: # B1, B1, B1, ...
        if B1 in bad:
            print(0)
        else:
            print("inf")
    else: # B1, -B1, B1, ...
        if B1 in bad and -B1 in bad:
            print(0)
        else:
            print("inf")
else:
    # finite
    count = 0
    b = B1
    while abs(b) <= L:
        if b not in bad:
            count += 1

        b *= Q

    print(count)


b, q, l, m = list(map(int, input().split()))
bad = set(map(int, input().split()))

cnt = 0

if abs(b) > l:
    print(0)
elif q == 0 or b == 0:
    if b not in bad:
        cnt += 1
    if 0 in bad:
        print(cnt)
    else:
        print("inf")
elif abs(q) == 1:
    if b in bad and (q == 1 or -b in bad):
        print(0)
    else:
        print("inf")
else:
    while abs(b) <= l:
        if b not in bad:
            cnt += 1
        b *= q
    print(cnt)


R=lambda:list(map(int,input().split()))
b,q,i,m=R()
a=set(R())
c=0
for _ in range(99):
  if abs(b)>i: break
  if b not in a: c+=1
  b*=q
print(c if c<32 else'inf')


miis = lambda:list(map(int,input().split()))
b,q,l,m = miis()
*a, = miis()
c = 0
for _ in ' '*100:
    if abs(b)>l: break
    if b not in a: c+=1
    b*=q
if c<35:
    print (c)
else:
    print ('inf')


def solve():
    b1, q, L, m = map(int, input().split())
    a = set(int(i) for i in input().split())

    if abs(b1) > L:
        print(0)
        return

    if b1 == 0:
        print(0 if b1 in a else 'inf')
        return

    if q == 0:
        if 0 in a:
            print(0 if b1 in a else 1)
        else:
            print('inf')

        return

    if q == 1:
        print(0 if b1 in a else 'inf')
        return

    if q == -1:
        print(0 if (b1 in a and -b1 in a) else 'inf')
        return

    b = b1
    ans = 0

    while abs(b) <= L:
        if b not in a:
            ans += 1
        b *= q

    print(ans)


def __starting_point():
    solve()
__starting_point()

b, q, l, m = [int(a_temp) for a_temp in input().strip().split()]
a = [int(a_temp) for a_temp in input().strip().split()]
d = {}
for e in a:
    d[e]=True
if abs(b)>l:
    print(0)
elif q==0:
    if 0 not in d:
        print("inf")
    elif b not in d:
        print(1)
    else:
        print(0)
elif b==0:
    if 0 not in d:
        print("inf")
    else:
        print(0)
elif q==1:
    if b in d or abs(b)>l:
        print(0)
    else:
        print("inf")
elif q==-1:
    if abs(b)>l:
        print(0)
    elif b not in d:
        print("inf")
    elif -1*b not in d:
        print("inf")
    else:
        print(0)
else:
    count = 0
    t = b
    while(abs(t)<=l):
        if t not in d:
            count+=1
        t*=q
    print(count)

b1 , q , l , m = list(map(int, input().split()))
s = set(map(int , input().split()))
ans = 0
cnt = 0
while abs(b1) <= l:
    if b1 not in s:
        ans += 1
    cnt += 1
    if cnt == 100000:
        break
    b1 *= q
    
if ans >= 50000:
    print('inf')
else:
    print(ans)


x = list(map(int, input().split()))
init_term = x[0]
ratio = x[1]
abs_max = x[2]
num_bad = x[3]

bad_list = list(map(int, input().split()))

curr_val = 0
curr_val += init_term
num_to_write = 0

if abs(init_term) > abs_max:
	print("0")
else:
	if init_term == 0:
		if init_term in bad_list:
			print("0")
		else:
			print("inf") # minimum abs_max can be is 1.
	else:
		if ratio == 1:
			if (curr_val * ratio in bad_list):
				print("0")
			else:
				print("inf")

		elif ratio == 0:
			if (0 in bad_list and init_term in bad_list):
				print("0")
			elif 0 in bad_list:
				print("1")
			else:
				print("inf")

		elif ratio == -1:
			if (init_term in bad_list and -init_term in bad_list):
				print("0")
		
			else:
				print("inf")
	
		else:
			while (abs(curr_val) <= abs_max):
				if curr_val not in bad_list:
					num_to_write += 1
				curr_val *= ratio

			print(num_to_write)



B, Q, L, M = list(map( int, input().split() ))
A = set( map( int, input().split() ) )
ans = 0
for _ in range( 100 ):
  if abs( B ) > L:
    break
  if B not in A:
    ans += 1
  B *= Q
print( ans if ans < 32 else "inf" )


b, q, l, m = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
if abs(b) > l:
    c = 0
elif b == 0:
    if 0 in a: c = 0
    else: c = "inf"
elif q == 1:
    if b in a: c = 0
    else: c = "inf"
elif q == -1:
    if b in a and -b in a: c = 0
    else: c = "inf"
elif q == 0:
    if 0 not in a: c = "inf"
    elif b in a: c = 0
    else: c = 1
else:
    c = 0
    while abs(b) <= l:
        if b not in a: c += 1
        b *= q
print(c)

b, q, l, m = [int(x) for x in input().split()]
seq = [int(x) for x in input().split()]

wyn = 0
while abs(b) <= l:
    if b == 0 or q == 0:
        if 0 not in seq:
            print("inf")
        elif b != 0 and b not in seq:
            print(1)
        elif b == 0 or b !=0 and b in seq:
            print(0)
        return

    if q == 1:
        if b in seq:
            print(0)
        else:
            print("inf")
        return

    if q == -1:
        if b in seq and b*-1 in seq:
            print(0)
        else:
            print("inf")
        return

    if b not in seq:
        wyn += 1
    b *= q
print(wyn)