#ifndef ONLINE_JUDGE #define _GLIBCXX_DEBUG #endif #include using namespace std; #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define bit(n,k) (((ll)n>>(ll)k)&1) /*nのk bit目*/ #define pb push_back #define pf push_front #define FI first #define SE second #define eb emplace_back #define endl '\n' #define SZ(x) ((ll)(x).size()) #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define PI 3.14159265359 const double eps = 1e-12; const long long INF= 1e+18+1; typedef long long ll; typedef vector vl; typedef vector >vvl; typedef vector > >vvvl; typedef vector > > >vvvvl; typedef vector > > > >vvvvvl; typedef pair P; typedef tuple T; typedef struct Point_Coordinates { ll x, y; } point; template using minpq=priority_queue,greater>; const ll MOD=1000000007LL; //ll MOD=1000000007LL; // const ll MOD=998244353LL; //const ll MOD=1777777777LL; //const ll MAX_V=114514LL; //const ll MAX = 500010LL; const ll mod=MOD; string abc="abcdefghijklmnopqrstuvwxyz"; string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ"; vl dx={0,0,1,-1,1,1,-1,-1}; vl dy={1,-1,0,0,-1,1,-1,1}; templatebool chmax(T &a,const T &b){if(abool chmin(T &a,const T &b){if(b ostream &operator<<(ostream &os,const vector&v){ for(int i=0;i<(int)v.size();i++) os< istream &operator>>(istream &is,vector&v){ for(T &x:v)is>>x; return is; } // 2^127 = 170141183460469231731687303715884105728 ~ 10^38 using int128=__int128; ostream &operator<<(ostream &os,const __int128 n){ if(n==0){ os<<0; return os; } __int128 num=n; bool neg=false; if(num<0)neg=true,num=-num; string res=""; while(num>0){ res.push_back('0'+num%10); num/=10; } if(neg) res.push_back('-'); reverse(begin(res),end(res)); os<>(istream &is,__int128 &n){ string s; is>>s; int idx=0; bool neg=false; if(s[0]=='-')neg=true,idx++; n=0; for(;idx<(int)s.size();idx++){ n=10*n+s[idx]-'0'; } if(neg) n=-n; return is; } __int128 abs128(__int128 x){ return x<0?-x:x; } __int128 gcd128(__int128 a,__int128 b){ if(a==0) return b; if(b==0) return a; return b>0?gcd128(b,a%b):a; } namespace fastprime{ int128 pow_mod(int128 a,int128 n,int128 m){ int128 ret=1; while(n){ if(n&1)ret=ret*a%m; a=a*a%m; n>>=1; } return ret; } bool miller_rabin(int128 n){ if(n<=1) return false; if(n==2) return true; if(n%2==0) return false; int128 d=n-1,s=0; while(!(d&1))d>>=1,s++;// n-1=2^s*d for(int128 a:{2,3,5,7,11,13,17,19,23,29,31,37}){ if(n<=a) break; int128 y=pow_mod(a,d,n);// y=a^d (mod n) int128 t; for(t=d;t pollard_rho(int128 n){ if(n==1) return {}; int128 x=pollard_rho_single(n); if(x==n) return {x}; vector l=pollard_rho(x); vector r=pollard_rho(n/x); l.insert(l.end(),r.begin(),r.end()); return l; } } #define ll int128 #define int int128 signed main(){ ll n,m,p; cin>>n>>m>>p; vector a(n); rep(i,n)cin>>a[i]; //a[i]=p^k*qのときコストk+1回で×qできる //1<=k<=log(max{A})なのでk<=[9*log(2,10)]=29より //コストは1~30 //全てのqが1のとき例外として"-1" vector

vec(n); bool one=true; rep(i,n){ ll cnt=0; ll now=a[i]; while(now%p==0)now/=p,cnt++; vec[i]={cnt+1,now}; if(now!=1)one=false; // cout< dp(t,-1); dp[0]=1; for(int i=1;i=vec[j].first)chmax(dp[i],dp[i-vec[j].first]*vec[j].second); } // cout<m){ cout<