玛莎真的很喜欢代数。最后一课,严厉的老师德瓦斯坦给了她新的练习。
给定由两个整数 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。