Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Masha and geometric depression

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputMasha 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.

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/26/2019 16:32:12 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|