B. Masha and geometric depression

Masha really loves algebra. On the last lesson, her strict teacher Dvastan gave she new exercise. You are given geometric progression #cf_span[b] defined by two integers #cf_span[b1] and #cf_span[q]. Remind that a geometric progression is a sequence of integers #cf_span[b1, b2, b3, ...], where for each #cf_span[i > 1] the respective term satisfies the condition #cf_span[bi = bi - 1·q], where #cf_span[q] is called the common ratio of the progression. Progressions in Uzhlyandia are unusual: both #cf_span[b1] and #cf_span[q] *can equal #cf_span[0]*. Also, Dvastan gave Masha #cf_span[m] "bad" integers #cf_span[a1, a2, ..., am], and an integer #cf_span[l]. Masha writes all progression terms one by one onto the board (including repetitive) while condition #cf_span[|bi| ≤ l] is satisfied (#cf_span[|x|] means absolute value of #cf_span[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. The first line of input contains four integers #cf_span[b1], #cf_span[q], #cf_span[l], #cf_span[m] (-#cf_span[109 ≤ b1, q ≤ 109], #cf_span[1 ≤ l ≤ 109], #cf_span[1 ≤ m ≤ 105]) — 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 #cf_span[m] distinct integers #cf_span[a1, a2, ..., am] (-#cf_span[109 ≤ ai ≤ 109)] — numbers that will never be written on the board. 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. In the first sample case, Masha will write integers #cf_span[3, 12, 24]. Progression term #cf_span[6] will be skipped because it is a "bad" integer. Terms bigger than #cf_span[24] won't be written because they exceed #cf_span[l] by absolute value. In the second case, Masha won't write any number because all terms are equal #cf_span[123] and this is a "bad" integer. In the third case, Masha will write infinitely integers #cf_span[123]. ## Input The first line of input contains four integers #cf_span[b1], #cf_span[q], #cf_span[l], #cf_span[m] (-#cf_span[109 ≤ b1, q ≤ 109], #cf_span[1 ≤ l ≤ 109], #cf_span[1 ≤ m ≤ 105]) — 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 #cf_span[m] distinct integers #cf_span[a1, a2, ..., am] (-#cf_span[109 ≤ ai ≤ 109)] — 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. [samples] ## Note 在第一个样例中，Masha 将写下整数 #cf_span[3, 12, 24]。等比数列项 #cf_span[6] 将被跳过，因为它是一个 "坏" 整数。大于 #cf_span[24] 的项不会被写下，因为它们的绝对值超过了 #cf_span[l]。 在第二个样例中，Masha 不会写下任何数字，因为所有项都等于 #cf_span[123]，而这是一个 "坏" 整数。 在第三个样例中，Masha 将写下无穷多个 #cf_span[123]。

**Definitions** Let $ b_1, q \in \mathbb{Z} $ be the initial term and common ratio of a geometric progression. Let $ l \in \mathbb{Z}^+ $ be the upper bound on absolute value of terms to be written. Let $ A = \{a_1, a_2, \dots, a_m\} \subset \mathbb{Z} $ be the set of "bad" integers, with $ m \geq 1 $. Define the progression $ b_i = b_1 \cdot q^{i-1} $ for $ i \geq 1 $. **Constraints** 1. $ -10^9 \leq b_1, q \leq 10^9 $ 2. $ 1 \leq l \leq 10^9 $ 3. $ 1 \leq m \leq 10^5 $ 4. $ -10^9 \leq a_j \leq 10^9 $ for all $ j \in \{1, \dots, m\} $ **Objective** Count the number of terms $ b_i $ such that: - $ |b_i| \leq l $, and - $ b_i \notin A $. If the number of such terms is infinite, output `"inf"`.