← 返回题目列表

Codeforces · 789/B

B. 玛莎和几何凹陷

中文机器翻译题面 查看原题

玛莎真的很喜欢代数。最后一课,严厉的老师德瓦斯坦给了她新的练习。

给定由两个整数 b1 和 q 定义的几何级数 b。请记住,几何级数是整数 b1、b2、b3、... 的序列,其中对于每个 i > 1,相应项满足条件 bi = bi - 1·q,其中 q 称为级数的公比。 Uzhlyandia 中的级数很不寻常:b1 和 q 都可以等于 0。此外,Dvastan 给了 Masha m 个“坏”整数 a1、a2、...、am 和一个整数 l。

Masha 将所有级数项一一写在黑板上(包括重复项),同时条件 |bi|满足≤l(|x|表示x的绝对值)。有一个例外:如果一项等于“坏”整数之一,玛莎会跳过它(不会写到黑板上)并前进到下一项。

但是课程很快就要结束了,所以玛莎必须计算黑板上会写多少个整数。为了不陷入抑郁,玛莎向你寻求帮助:帮助她计算她要写多少个数字,或者打印“inf”以防她需要写无限多个整数。

输入

输入的第一行包含四个整数 b1, q, l, m (-109 ≤ b1, q ≤ 109, 1 ≤ l ≤ 109, 1 ≤ m ≤ 105)——分别是初始项和级数的公比、可以写在黑板上的最大数字的绝对值和“坏”整数的数量。

第二行包含 m 个不同的整数 a1, a2, ..., am (-109 ≤ ai ≤ 109) - 永远不会写在黑板上的数字。

输出

打印唯一的整数,表示如果是有限的,则将写在板上的级数项的数量,否则打印“inf”(不带引号)。

示例

输入 #1

3 2 30 4
6 14 25 48

输出 #1

3

输入 #2

123 1 2143435 4
123 11 -5453 141245

输出 #2

0

输入 #3

123 1 2143435 4
54343 -13 6 124

输出 #3

inf

注意

在第一个示例中,Masha 将写入整数 3、12、24。将跳过级数项 6,因为它是一个“坏”整数。大于 24 的项不会被写入,因为它们的绝对值超过 l。

在第二种情况下,Masha 不会写任何数字,因为所有项都等于 123,这是一个“坏”整数。

在第三种情况下,Masha 将写入无限整数 123。