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: MEDIUM_HARD
Tags: Mathematics

Implementation

Complete search
Skill types: Complete search

Starter code:

Solutions:
ip = lambda : [int(i) for i in input().split()]
(b, q, l, m) = ip()
bad = set(ip())
ans = 0
iter_count = 0
inf = False
while True:
	if iter_count >= 40:
		inf = True
		break
	if abs(b) > l:
		break
	if b not in bad:
		ans += 1
	b *= q
	iter_count += 1
if inf and ans > 2:
	print('inf')
else:
	print(ans)


import sys
(b, q, l, m) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
if abs(b) > l:
	print(0)
	sys.exit()
if b == 0:
	if 0 in a:
		print(0)
	else:
		print('inf')
elif q == 0:
	if not 0 in a:
		print('inf')
	elif b in a:
		print(0)
	else:
		print(1)
elif q == 1:
	if b in a:
		print(0)
	else:
		print('inf')
elif q == -1:
	if not b in a or not -b in a:
		print('inf')
	else:
		print(0)
else:
	cnt = 0
	bn = b
	while abs(bn) <= l:
		if not bn in a:
			cnt += 1
		bn *= q
	print(cnt)


[b1, q, l, m] = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
if abs(b1) > l:
	print('0')
	exit(0)
if b1 == 0:
	if (b1 in a) == False:
		print('inf')
	else:
		print('0')
	exit(0)
if q == 0:
	if (q in a) == False:
		print('inf')
	elif abs(b1) <= l and (b1 in a) == False:
		print('1')
	else:
		print('0')
	exit(0)
if q == 1:
	if abs(b1) <= l:
		if (b1 in a) == False:
			print('inf')
		else:
			print('0')
		exit(0)
if q == -1:
	if abs(b1) <= l and ((b1 in a) == False or (-b1 in a) == False):
		print('inf')
	elif abs(b1) <= l and (b1 in a) == True and ((-b1 in a) == True):
		print('0')
	exit(0)
cnd = []
b = b1
while abs(b) <= l:
	cnd.append(b)
	b *= q
res = []
for e in cnd:
	if (e in a) == False:
		res.append(e)
print(len(res))


ins = map(int, input().split())
(b1, q, limit, n) = (next(ins), next(ins), next(ins), next(ins))
bads_map = {}
bads = map(int, input().split())
for bad in bads:
	bads_map[bad] = bads_map.get(bad, True)
if abs(b1) > limit:
	print(0)
elif b1 == 0:
	if 0 in bads_map:
		print(0)
	else:
		print('inf')
elif q == 1:
	if b1 in bads_map:
		print(0)
	else:
		print('inf')
elif q == -1:
	if b1 in bads_map and -b1 in bads_map:
		print(0)
	else:
		print('inf')
elif q == 0:
	if 0 not in bads_map:
		print('inf')
	elif b1 in bads_map:
		print(0)
	else:
		print(1)
else:
	ans = 0
	while abs(b1) <= limit:
		if b1 not in bads_map:
			ans += 1
		b1 *= q
	print(ans)


(b, q, l, m) = 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)


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()


(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
	elif a not in s:
		if abs(a) <= l:
			if 0 in s:
				print(1)
				return
			else:
				print('inf')
				return
		else:
			print(0)
			return
	elif 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
		elif abs(a) <= l:
			print('inf')
			return
		else:
			print(0)
			return
	elif 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)


(b, q, l, m) = tuple(map(int, input().split()))
bad = set(map(int, input().split()))
used = set()
ans = 0
inf = False
while abs(b) <= l:
	if b not in bad:
		ans += 1
	if b in used:
		inf = True
		break
	used.add(b)
	b *= q
if (b not in bad or (b * q in used and (not b * q in bad))) and inf:
	print('inf')
else:
	print(ans)


import sys

def ans(n):
	print(n)
	sys.exit()

def check(n):
	global w
	return abs(n) <= l and n not in w
(b1, q, l, m) = map(int, input().split())
w = set(map(int, input().split()))
inf = 'inf'
if b1 == 0:
	if 0 not in w:
		ans(inf)
	else:
		ans(0)
if q == 0:
	if abs(b1) > l:
		ans(0)
	if check(0):
		ans(inf)
	elif check(b1):
		ans(1)
	else:
		ans(0)
if q == 1:
	if check(b1):
		ans(inf)
	else:
		ans(0)
if q == -1:
	if check(b1) or check(-b1):
		ans(inf)
	else:
		ans(0)
cnt = 0
while abs(b1) <= l:
	cnt += check(b1)
	b1 *= q
ans(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)


class CodeforcesTask789BSolution:

	def __init__(self):
		self.result = ''
		self.b_q_l_m = []
		self.bad_numbers = []

	def read_input(self):
		self.b_q_l_m = [int(x) for x in input().split(' ')]
		self.bad_numbers = [int(x) for x in input().split(' ')]

	def process_task(self):
		term = self.b_q_l_m[0]
		q = self.b_q_l_m[1]
		terms_count = 0
		if q == 1 and term not in self.bad_numbers:
			if abs(term) <= self.b_q_l_m[2]:
				self.result = 'inf'
			else:
				self.result = '0'
		elif q == 1:
			self.result = '0'
		elif q == 0:
			if abs(term) <= self.b_q_l_m[2]:
				if term not in self.bad_numbers:
					terms_count += 1
				if 0 not in self.bad_numbers:
					self.result = 'inf'
				else:
					self.result = str(terms_count)
			else:
				self.result = '0'
		elif q == -1:
			if term not in self.bad_numbers:
				if abs(term) <= self.b_q_l_m[2]:
					self.result = 'inf'
				else:
					self.result = '0'
			elif -term not in self.bad_numbers:
				if abs(-term) <= self.b_q_l_m[2]:
					self.result = 'inf'
				else:
					self.result = '0'
			else:
				self.result = '0'
		elif term == 0:
			if term not in self.bad_numbers:
				self.result = 'inf'
			else:
				self.result = '0'
		else:
			while abs(term) <= self.b_q_l_m[2]:
				if term not in self.bad_numbers:
					terms_count += 1
				term *= q
			self.result = str(terms_count)

	def get_result(self):
		return self.result
Solution = CodeforcesTask789BSolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


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')
elif init_term == 0:
	if init_term in bad_list:
		print('0')
	else:
		print('inf')
elif 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)


(b1, q, l, m) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
if abs(b1) > l:
	print(0)
elif b1 == 0:
	if 0 in a:
		print(0)
	else:
		print('inf')
elif q == 0:
	if not 0 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 not b1 in a or not -b1 in a:
		print('inf')
	else:
		print(0)
else:
	cnt = 0
	b = b1
	while abs(b) <= l:
		if not b in a:
			cnt += 1
		b *= q
	print(cnt)


inf = 'inf'
eps = 10 ** (-6)
import math
(start, q, lim, _) = (int(x) for x in input().split())
excs = {int(x) for x in input().split()}

def sign(x):
	return 1 if x > 0 else -1

def solve(start, q, lim, excs):
	if abs(start) > lim:
		return 0
	if start == 0:
		if 0 in excs:
			return 0
		return inf
	if q == 0:
		if 0 not in excs:
			return inf
		if start in excs:
			return 0
		return 1
	if q == 1:
		return 0 if start in excs else inf
	if q == -1:
		if start in excs and -start in excs:
			return 0
		return inf
	(iters, current) = (0, start)
	while abs(current) <= lim:
		if current not in excs:
			iters += 1
		current *= q
	return iters
print(str(solve(start, q, lim, excs)))


from sys import stdin
(B1, Q, L, M) = 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:
	if Q == 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:
		if B1 in bad:
			print(0)
		else:
			print('inf')
	elif B1 in bad and -B1 in bad:
		print(0)
	else:
		print('inf')
else:
	count = 0
	b = B1
	while abs(b) <= L:
		if b not in bad:
			count += 1
		b *= Q
	print(count)


(b, q, l, m) = map(int, input().split())
a = set(map(int, input().split()))
if abs(b) > l:
	print(0)
elif b == 0 or q == 0:
	print('inf' if 0 not in a else int(b not in a))
elif q == 1:
	print('inf' if b not in a else 0)
elif q == -1:
	print('inf' if b not in a or -b not in a else 0)
else:
	(c, v) = (b, set())
	while abs(c) <= l:
		v.add(c)
		c *= q
	print(len(v - a))


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


(b1, q, l, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
if abs(b1) > l:
	print(0)
elif b1 == 0:
	if b1 in a:
		print(0)
	else:
		print('inf')
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')
elif q == 0:
	if 0 not in a:
		print('inf')
	elif b1 in a:
		print(0)
	else:
		print(1)
else:
	ans = 0
	while abs(b1) <= l:
		if b1 not in a:
			ans = ans + 1
		b1 = b1 * q
	print(ans)


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')


(b, q, l, m) = (int(v) for v in input().split())
(a, ok, N) = ([int(v) for v in input().split()], [], 64)
while abs(b) <= l and N:
	N -= 1
	if b not in a:
		ok.append(b)
	b = b * q
print(len(ok) if len(ok) < 31 else 'inf')


from math import *

def ri():
	return map(int, input().split())
(b, q, l, m) = ri()
a = list(ri())
ans = 0
if abs(b) <= l:
	if not b in a:
		ans += 1
else:
	print(0)
	exit()
i = 0
while True:
	i += 1
	b = b * q
	if b in a:
		pass
	elif abs(b) <= l:
		ans += 1
	else:
		print(ans)
		break
	if i > 10:
		if b == b * q * q or b == b * q:
			if b in a and b * q in a:
				print(ans)
				exit()
			else:
				print('inf')
				exit()


import sys
(b, q, l, m) = map(int, input().split())
seq = set(map(int, input().split()))
x = 0
for i in range(100):
	if abs(b) > l:
		break
	if b not in seq:
		x += 1
	b *= q
	if x > 35:
		print('inf')
		sys.exit()
print(x)


(B, Q, L, M) = 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, n) = map(int, input().split())
a = list(map(int, input().split()))
s = set(a)
if abs(b) > l:
	print('0')
elif b == 0:
	if b in s:
		print('0')
	else:
		print('inf')
elif q == 0:
	res = None
	if 0 not in s:
		res = 'inf'
	elif b in s:
		res = 0
	else:
		res = 1
	print(res)
elif q == 1:
	if b not in s:
		print('inf')
	else:
		print(0)
elif q == -1:
	if b not in s or -b not in s:
		print('inf')
	else:
		print(0)
else:
	res = 0
	while abs(b) <= l:
		if b not in s and abs(b) <= l:
			res += 1
		b = b * q
	print(res)


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


(b, q, l, m) = list(map(int, input().split()))
st = set(map(int, input().split()))
mx = 1000
ans = 0
for i in range(0, 100000):
	if abs(b) > l:
		break
	if b not in st:
		ans = ans + 1
	b *= q
	if ans == mx:
		break
if ans == mx:
	print('inf')
else:
	print(ans)


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


(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)


(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)


def mp():
	return map(int, input().split())

def lt():
	return list(map(int, input().split()))

def pt(x):
	print(x)

def ip():
	return input()

def it():
	return int(input())

def sl(x):
	return [t for t in x]

def spl(x):
	return x.split()

def aj(liste, item):
	liste.append(item)

def bin(x):
	return '{0:b}'.format(x)

def listring(l):
	return ' '.join([str(x) for x in l])

def ptlist(l):
	print(' '.join([str(x) for x in l]))
(b1, q, l, m) = mp()
a = lt()
if q == 1:
	if b1 in a or abs(b1) > l:
		pt(0)
	else:
		pt('inf')
elif q == 0:
	if abs(b1) > l:
		pt(0)
	elif b1 == 0:
		if not 0 in a:
			pt('inf')
		else:
			pt(0)
	elif not 0 in a:
		pt('inf')
	else:
		pt(int(not b1 in a))
elif q == -1:
	if abs(b1) > l:
		pt(0)
	elif b1 in a and -b1 in a:
		pt(0)
	else:
		pt('inf')
else:
	t = b1
	c = 0
	if b1 == 0:
		if not 0 in a:
			pt('inf')
		else:
			pt(0)
	else:
		while abs(t) <= l:
			if not t in a:
				c += 1
			t *= q
		pt(c)


(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
	print(count)
else:
	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')
			elif a1 == 0:
				print('1')
			else:
				print('inf')
		else:
			print('inf')
	else:
		print('0')


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)


(b, q, L, m) = map(int, input().split())
p = list(map(int, input().split()))

def solve(b, q, L, m, p):
	if q == 1:
		if b in p:
			return 0
		elif abs(b) <= L:
			return 'inf'
		else:
			return 0
	if q == -1:
		if (b not in p or -b not in p) and abs(b) <= L:
			return 'inf'
		else:
			return 0
	if q == 0:
		if 0 not in p and abs(b) <= L:
			return 'inf'
		elif b in p or not abs(b) <= L:
			return 0
		else:
			return 1
	if b == 0:
		if 0 not in p:
			return 'inf'
		else:
			return 0
	s = 0
	while abs(b) <= L:
		if b not in p:
			s += 1
		b = b * q
	return s
print(solve(b, q, L, m, p))


(b, q, l, m) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
if abs(b) > l:
	print(0)
	exit()
if b == 0:
	if 0 in a:
		print(0)
	else:
		print('inf')
	exit()
if q == 0:
	if 0 in a:
		if b == 0 or b in a:
			print(0)
		else:
			print(1)
	else:
		print('inf')
	exit()
if q == 1:
	if b in a or abs(b) > l:
		print(0)
	else:
		print('inf')
	exit()
if q == -1:
	if b in a and -b in a:
		print(0)
	else:
		print('inf')
	exit()
cnt = 0
for i in range(100):
	if abs(b) > l:
		break
	if b not in a:
		cnt += 1
	b *= q
print(cnt)


def main():
	(a, r, l, n) = map(int, input().split())
	temp = list(map(int, input().split()))
	x = {}
	for bad in temp:
		x[bad] = True
	if abs(a) > l:
		print(0)
		return
	if a == 0:
		ans = 'inf'
		if x.get(0):
			ans = 0
		print(ans)
		return
	if r == 0:
		ans = 'inf'
		if x.get(a) and x.get(0):
			ans = 0
		elif x.get(0):
			ans = 1
		print(ans)
		return
	if r == 1:
		ans = 'inf'
		if x.get(a):
			ans = 0
		print(ans)
		return
	if r == -1:
		ans = 'inf'
		if x.get(a) and x.get(-a):
			ans = 0
		print(ans)
		return
	cur = a
	ans = 0
	while abs(cur) <= l:
		if not x.get(cur):
			ans += 1
		cur *= r
	print(ans)
main()


(B1, Q, L, M) = 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))


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)
solve()


(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)


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


def solve():
	if b == 0:
		if b not in a:
			return 'inf'
		return 0
	if q == 0:
		if 0 not in a and abs(b) <= l:
			return 'inf'
		return int(b not in a and abs(b) <= l)
	if q == 1:
		if b in a or abs(b) > l:
			return 0
		return 'inf'
	if q == -1:
		if b in a and -b in a:
			return 0
		if abs(b) > l:
			return 0
		return 'inf'
	cnt = 0
	c = b
	while abs(c) <= l:
		if c not in a:
			cnt += 1
		c *= q
	return cnt
read = lambda : map(int, input().split())
(b, q, l, m) = read()
a = set(read())
print(solve())


(s, r, m, n) = 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)


def main():
	(b1, q, l, m) = map(int, input().split())
	a = set(map(int, input().split()))
	if b1 == 0:
		if 0 in a:
			return 0
		else:
			return 'inf'
	if q == 0:
		if abs(b1) > l:
			return 0
		if b1 in a:
			if 0 in a:
				return 0
			else:
				return 'inf'
		elif 0 in a:
			return 1
		else:
			return 'inf'
	if q == 1:
		if abs(b1) > l or b1 in a:
			return 0
		else:
			return 'inf'
	if q == -1:
		if abs(b1) > l or (b1 in a and -b1 in a):
			return 0
		else:
			return 'inf'
	result = 0
	b = b1
	while True:
		if abs(b) > l:
			break
		if b not in a:
			result += 1
		b *= q
	return result
print(main())


def main():
	read = lambda : tuple(map(int, input().split()))
	(b, q, l, m) = read()
	ns = {}
	for n in read():
		ns[n] = True
	k = 0
	if b == 0:
		return 'inf' if not b in ns else 0
	if q == 1:
		return 'inf' if not b in ns and abs(b) <= l else 0
	if q == -1:
		return 'inf' if (not b in ns or not -b in ns) and abs(b) <= l else 0
	if q == 0:
		if abs(b) > l:
			return 0
		else:
			return 'inf' if not 0 in ns else 1 if not b in ns else 0
	while abs(b) <= l:
		if not b in ns:
			k += 1
		b *= q
	return k
print(main())


(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)


(b1, q, l, m) = map(int, input().split())
bads = [int(i) for i in input().split()]
if b1 == 0 or q in [0, 1, -1]:
	if b1 == 0:
		if 0 in bads:
			print(0)
		else:
			print('inf')
	elif q == 0:
		if 0 in bads or abs(b1) > l:
			if b1 in bads or abs(b1) > l:
				print(0)
			else:
				print(1)
		else:
			print('inf')
	elif q == 1:
		if b1 in bads or abs(b1) > l:
			print(0)
		else:
			print('inf')
	elif q == -1:
		if b1 in bads and -b1 in bads or abs(b1) > l:
			print(0)
		else:
			print('inf')
else:
	num = 0
	while abs(b1) <= l:
		if b1 not in bads:
			num += 1
		b1 *= q
	print(num)


(b1, q, l, m) = 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)


(b, q, l, m) = map(int, input().split())
bad = set((int(x) for x in input().split()))
c = 0
n = b
done = False
for i in range(50):
	if abs(n) > l:
		done = True
		break
	if n not in bad:
		c += 1
	n = n * q
c1 = 0
n = b
for i in range(70):
	if abs(n) > l:
		break
	if n not in bad:
		c1 += 1
	n = n * q
if done or c == c1:
	print(c)
else:
	print('inf')


from sys import exit
(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)
		exit()
	if q == 1:
		if b in seq:
			print(0)
		else:
			print('inf')
		exit()
	if q == -1:
		if b in seq and b * -1 in seq:
			print(0)
		else:
			print('inf')
		exit()
	if b not in seq:
		wyn += 1
	b *= q
print(wyn)


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)
		elif 0 not in bads:
			print('inf')
		elif 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()


import math, sys, bisect, heapq
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda : map(int, input().split())
alele = lambda : list(map(int, input().split()))

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])
(b, q, l, m) = ilele()
A = alele()
C = Counter(A)
Ans = [b]
if abs(b) > l:
	print(0)
	exit(0)
for i in range(100000):
	b *= q
	if abs(b) > l:
		break
	Ans.append(b)
count = 0
G = set()
for i in Ans:
	if C.get(i, -1) == -1 and abs(i) <= l:
		count += 1
		G.add(i)
if count >= 10000 or (count > 1000 and len(G) <= 3):
	print('inf')
else:
	print(count)


def main():
	(b1, q, l, m) = map(int, input().split())
	a = set(map(int, input().split()))
	if abs(b1) > l:
		print(0)
	elif 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)
main()


(b1, q, l, m) = list(map(int, input().strip().split()))
excl = list(map(int, input().strip().split()))
if abs(b1) > l or (q == 1 and b1 in excl):
	print(0)
elif q in (1, -1) and (b1 not in excl or -b1 not in excl):
	print('inf')
elif q in (1, -1) and (b1 in excl and -b1 in excl):
	print(0)
elif b1 == 0 or q == 0:
	if 0 in excl:
		if b1 != 0 and b1 not in excl:
			print(1)
		else:
			print(0)
	else:
		print('inf')
else:
	writes = 0
	b = b1
	while abs(b) <= l:
		writes += int(b not in excl)
		b *= q
	print(writes)


from bisect import bisect_left

def bins(holes, x, bot, top=None):
	top = top if top is not None else len(holes)
	pos = bisect_left(holes, x, bot, top)
	return pos != top and holes[pos] == x
(b, q, l, m) = list(map(int, input().split(' ')))
s = list(map(int, input().split(' ')))
s = sorted(s)
counter = 0
if abs(b) > l:
	print(0)
elif q == 0 or q == -1 or q == 1:
	if q == 1:
		if bins(s, b, 0):
			print('0')
		else:
			print('inf')
	elif q == 0:
		res = 0
		if not bins(s, b, 0):
			res = 1
		if bins(s, 0, 0):
			print(res)
		else:
			print('inf')
	elif q == -1:
		if bins(s, b, 0) and bins(s, -b, 0):
			print('0')
		else:
			print('inf')
elif b == 0:
	if bins(s, b, 0):
		print('0')
	else:
		print('inf')
else:
	while abs(b) <= l:
		if not bins(s, b, 0):
			counter += 1
		b *= q
	print(counter)


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')


(b1, q, l, m) = map(int, input().split())
a = set(map(int, input().split()))
if q == 0:
	if 0 in a:
		if b1 in a:
			print(0)
		elif abs(b1) <= l:
			print(1)
		else:
			print(0)
	elif abs(b1) <= l:
		print('inf')
	else:
		print(0)
elif q == 1:
	if abs(b1) <= l and b1 not in a:
		print('inf')
	else:
		print(0)
elif q == -1:
	if abs(b1) <= l and (b1 not in a or -b1 not in a):
		print('inf')
	else:
		print(0)
elif b1 == 0:
	if 0 in a:
		print(0)
	else:
		print('inf')
else:
	cnt = 0
	p = b1
	while abs(p) <= l:
		if p not in a:
			cnt += 1
		p *= q
	print(cnt)


(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)


spam = input()
spam = spam.split(' ')
b = int(spam[0])
q = int(spam[1])
l = int(spam[2])
m = int(spam[3])
spam = input()
spam = spam.split(' ')
write = []
inf = False
for i in range(len(spam)):
	spam[i] = int(spam[i])
count = 0
c2 = 0
while b <= l and -1 * b <= l:
	if b not in spam:
		count = count + 1
	if c2 > 100:
		break
	b = b * q
	c2 = c2 + 1
if count > 50:
	print('inf')
else:
	print(count)


(b, q, l, m) = map(int, input().split())
s = set(map(int, input().split()))
if abs(b) > l:
	print(0)
	exit()
if q == 1:
	if b not in s:
		print('inf')
		exit()
	else:
		print(0)
		exit()
if q == -1:
	if b not in s or b * -1 not in s:
		print('inf')
		exit()
	else:
		print(0)
		exit()
if q == 0:
	if 0 not in s:
		print('inf')
		exit()
	else:
		print(1 * (b not in s))
		exit()
if b == 0:
	if 0 not in s:
		print('inf')
		exit()
	else:
		print(0)
		exit()
res = 0
while abs(b) <= l:
	if b not in s:
		res += 1
	b = b * q
print(res)


(b, q, l, m) = map(int, input().split())
a = [int(x) for x in input().split()]
a.sort()
cnt = 0
if (b > l or b < -l) or (b == 0 and 0 in a) or (q == -1 and b in a and (-b in a)) or (q == 0 and 0 in a and (b in a)) or (q == 1 and b in a):
	print(0)
	quit()
if b == 0 or q == 1 or (q == 0 and 0 not in a) or (q == -1):
	print('inf')
	quit()
if q == 0 and 0 in a:
	print(1)
	quit()
for i in a:
	if i <= l and i >= -l and (i % b == 0):
		t = i // b
		while q != 0 and t != 0 and (t % q == 0):
			t //= q
		if t == 1:
			cnt -= 1
	tenp = i
while b != 0 and b <= l and (b >= -l):
	b *= q
	cnt += 1
print(cnt)


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


(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)


from collections import defaultdict
(b, q, l, m) = map(int, input().split())
arr = [int(x) for x in input().split()]
d = defaultdict(bool)
for i in arr:
	d[i] = True
if b == 0:
	if d[b]:
		print(0)
	else:
		print('inf')
elif q == 0:
	if abs(b) > l:
		print(0)
	else:
		ans = 0
		if not d[b]:
			ans += 1
		if d[0]:
			print(ans)
		else:
			print('inf')
elif q == 1:
	if abs(b) > l:
		print(0)
	elif d[b]:
		print(0)
	else:
		print('inf')
elif q == -1:
	if abs(b) > l:
		print(0)
	elif d[b] and d[-b]:
		print(0)
	else:
		print('inf')
else:
	possible = []
	curr = b
	while abs(curr) <= l:
		if not d[curr]:
			possible.append(curr)
		curr *= q
	print(len(possible))


(b, q, l, m) = list(map(int, input().split()))
a = set(map(int, input().split()))
if abs(b) > l:
	print(0)
	exit()
if q == 1:
	if b in a:
		print(0)
	else:
		print('inf')
	exit()
elif q == -1:
	if b in a:
		if -b not in a:
			print('inf')
		else:
			print(0)
	else:
		print('inf')
	exit()
cnt = 0
processed = set()
st = None
while abs(b) <= l:
	if b not in a:
		if b in processed:
			st = 'inf'
			break
		cnt += 1
		processed.add(b)
		b *= q
	else:
		if b in processed:
			st = cnt
			break
		processed.add(b)
		b *= q
		continue
if st is not None:
	print(st)
else:
	print(cnt)