Codeforces Round #407 (Div. 2) 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 b defined by two integers b₁ and q. Remind that a geometric progression is a sequence of integers b₁, b₂, b₃, ..., 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₁ and q can equal 0. Also, Dvastan gave Masha m "bad" integers a₁, a₂, ..., 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₁, q, l, m (-10⁹ ≤ b₁, q ≤ 10⁹, 1 ≤ l ≤ 10⁹, 1 ≤ m ≤ 10⁵) — 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₁, a₂, ..., a_m (-10⁹ ≤ a_i ≤ 10⁹) — 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

Input

123 1 2143435 4
123 11 -5453 141245

Output

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.

分析：分类讨论的问题，要注意的是在b1小于l的情况下直接结束，因为题目中并没有说这样也可以跳过输出下一个数。

只有当限制l内的数，在数组中出现的时候才跳过输出下一个数。

查找该数是否在数组中出现时可以用二分法

该题需要讨论 b=0,q=0,q=1,q=-1 这四种情况。关于自己的二分写法需要注意

当数组里面的数都大于key的时候

l始终为-1

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
typedef long long ll;
 ll a[100050];
int binary(ll *a,int len,int key)
{
    int l=-1;
    int r=len;
    int m=(l+r)/2;
    while(l+1<r)
    {
        m=(l+r)/2;
           if(a[m]<=key)
            l=m;
            else
            r=m;
    }
    if(l<0)
    l=0;
    return l;
}
int main()
{
    ll b,q,l,m,h,num,x;
    while(cin>>b>>q>>l>>m)
    {
        num=0;
      for(int i=0;i<m;i++)
      cin>>a[i];
      sort(a,a+m);
      
       if(b==0)
      {
      h=binary(a,m,b);
      if(a[h]!=b)
      cout<<"inf"<<endl;
      else
      cout<<"0"<<endl;
      continue;
      }
       if(abs(b)>l)
        {
            cout<<"0"<<endl;
            continue;
        }
      if(q==0)
      {
           h=binary(a,m,0);
           if(a[h]!=0)
           {
             cout<<"inf"<<endl;
             continue;
         }
          if(abs(b)>l)
        {
            cout<<"0"<<endl;
            continue;
        }
           h=binary(a,m,b);
           if(a[h]!=b)
           num++;
           cout<<num<<endl;
           continue;
      }
         if(abs(b)>l)
        {
            cout<<"0"<<endl;
            continue;
        }
      if(q==1)
      {
          h=binary(a,m,b);
          if(a[h]!=b)
          {  
          cout<<"inf"<<endl;
          continue;
        }
        else
        cout<<"0"<<endl;
        continue;
      }
      if(q==-1)
      {
          h=binary(a,m,b);
          if(a[h]!=b)
          {
              cout<<"inf"<<endl;
              continue;
          }
          h=binary(a,m,-b);
          if(a[h]!=-b)
          {
              cout<<"inf"<<endl;
              continue;
        }
          cout<<"0"<<endl;
          continue;
      }
      num=0;
      h=binary(a,m,b);
      if(a[h]!=b)
      num++;
      x=b;
    //  cout<<num<<endl;
      for(int i=1;;i++)
      {
           x=x*q;
           if(abs(x)>l)
           break;
           h=binary(a,m,x);
           if(a[h]!=x)
           num++; 
      }
      cout<<num<<endl;
    }
    return 0;
}