結果
| 問題 | No.2806 Cornflake Man |
| ユーザー |
 nouka28
|
| 提出日時 | 2024-07-12 21:59:48 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 1,913 ms / 2,000 ms |
| コード長 | 21,458 bytes |
| コンパイル時間 | 7,025 ms |
| コンパイル使用メモリ | 337,036 KB |
| 実行使用メモリ | 23,040 KB |
| 最終ジャッジ日時 | 2024-08-06 20:26:16 |
| 合計ジャッジ時間 | 16,081 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 35 ms
8,960 KB |
| testcase_01 | AC | 599 ms
11,648 KB |
| testcase_02 | AC | 11 ms
5,376 KB |
| testcase_03 | AC | 629 ms
11,904 KB |
| testcase_04 | AC | 9 ms
5,376 KB |
| testcase_05 | AC | 116 ms
5,748 KB |
| testcase_06 | AC | 22 ms
6,940 KB |
| testcase_07 | AC | 751 ms
13,184 KB |
| testcase_08 | AC | 20 ms
6,652 KB |
| testcase_09 | AC | 365 ms
8,576 KB |
| testcase_10 | AC | 411 ms
7,936 KB |
| testcase_11 | AC | 52 ms
5,376 KB |
| testcase_12 | AC | 522 ms
8,684 KB |
| testcase_13 | AC | 1,054 ms
13,696 KB |
| testcase_14 | AC | 195 ms
6,016 KB |
| testcase_15 | AC | 1,913 ms
23,040 KB |
| testcase_16 | AC | 2 ms
5,376 KB |
| testcase_17 | AC | 2 ms
5,376 KB |
| testcase_18 | AC | 2 ms
5,376 KB |
| testcase_19 | AC | 2 ms
5,376 KB |
ソースコード
#pragma region template
/*
template made by nouka28
last update 2024.7.7
*/
//include
#include<bits/stdc++.h>
using namespace std;
//atcoder
#include<atcoder/all>
using namespace atcoder;
using mint=atcoder::modint998244353;
// using mint=atcoder::modint1000000007;
// using mint=atcoder::modint;
istream& operator>>(istream&is,mint &x){long long x_;is>>x_;x=x_;return is;}
ostream& operator<<(ostream&os,mint &x){os<<x.val();return os;}
//pragma
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
//define
// #define int long long
#define pb push_back
#define eb emplace_back
#define ep emplace
#define fi first
#define se second
#define ALL(x) begin(x),end(x)
#define LEN(x) (signed int)(x.size())
#define BIT(x,i) ((x)>>(i)&1)
//using
using u32=unsigned int;
using u64=unsigned long long;
using ull=unsigned long long;
using i32=signed int;
using i64=signed long long;
using ll=signed long long;
using f64=double;
using f80=long double;
using pi=pair<i32,i32>;
using pl=pair<i64,i64>;
using pd=pair<f80,f80>;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T>using VVV=V<V<V<T>>>;
template<class T>using VVVV=V<V<V<V<T>>>>;
template<class T>using VVVVV=V<V<V<V<V<T>>>>>;
template<class T>using pqmax=priority_queue<T>;
template<class T>using pqmin=priority_queue<T,vector<T>,greater<T>>;
using u128=__uint128_t;
using i128=__int128_t;
//io INT128
i128 i128_parse(string &s){i128 ret=0;for(i32 i=0;i<(i32)s.length();i++)if('0'<=s[i]&&s[i]<='9')ret=10*ret+s[i]-'0';return ret;}
u128 u128_parse(string &s){u128 ret=0;for(i32 i=0;i<(i32)s.length();i++)if('0'<=s[i]&&s[i]<='9')ret=10*ret+s[i]-'0';return ret;}
istream &operator>>(istream &is,i128 &x){string s;is>>s;x=i128_parse(s);return is;}
istream &operator>>(istream &is,u128 &x){string s;is>>s;x=u128_parse(s);return is;}
ostream &operator<<(ostream &os,i128 x){
ostream::sentry s(os);
if(s){u128 tmp=x<0?-x:x;char buffer[128];char *d=end(buffer);
do{--d;*d="0123456789"[tmp%10];tmp/=10;}while(tmp!=0);
if(x<0){--d;*d='-';}
int len=end(buffer)-d;
if (os.rdbuf()->sputn(d,len)!=len){os.setstate(ios_base::badbit);}
}
return os;
}
//const
const i64 LINF=0x1fffffffffffffff;
const i32 INF=0x3fffffff;
const i64 MOD=998244353;
const i64 MOD2=1000000007;
const f80 PI=3.1415926535897932384626433832795028841971;
const f80 DINF=numeric_limits<f80>::infinity();
const f80 EPS=1e-9;
const i64 di[]={0,1,0,-1,1,-1,1,-1};
const i64 dj[]={1,0,-1,0,1,1,-1,-1};
//function
#define overload4(_1,_2,_3,_4,name,...) name
#define overload3(_1,_2,_3,name,...) name
#define rep1(n) for(i64 i=0;i<n;i++)
#define rep2(i,n) for(i64 i=0;i<n;i++)
#define rep3(i,a,b) for(i64 i=a;i<b;i++)
#define rep4(i,a,b,c) for(i64 i=a;i<b;i+=c)
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(n) for(i64 i=n;i--;)
#define rrep2(i,n) for(i64 i=n;i--;)
#define rrep3(i,a,b) for(i64 i=b;i-->(a);)
#define rrep4(i,a,b,c) for(i64 i=(a)+((b)-(a)-1)/(c)*(c)i>=a;i-=c)
#define rrep(...) overload4(__VA_ARGS__,rrep4,rrep3,rrep2,rrep1)(__VA_ARGS__)
#define SUM(...) accumulate(ALL(__VA_ARGS__),i64(0))
#define DSUM(...) accumulate(ALL(__VA_ARGS__),f80(0))
template<class T>bool chmin(T &x,const T&y){if(x>y){x=y;return true;}return false;}
template<class T>bool chmax(T &x,const T&y){if(x<y){x=y;return true;}return false;}
template<class T>i32 lob(const V<T>&arr,const T&v){return (i32)(lower_bound(ALL(arr),v)-arr.begin());}
template<class T>i32 upb(const V<T>&arr,const T&v){return (i32)(upper_bound(ALL(arr),v)-arr.begin());}
template<class T>constexpr auto min(T a,T b,T c){return min(a,min(b,c));}
template<class... T>constexpr auto min(T... a){return min(initializer_list<common_type_t<T...>>{a...});}
template<class T>constexpr auto max(T a,T b,T c){return max(a,max(b,c));}
template<class... T>constexpr auto max(T... a){return max(initializer_list<common_type_t<T...>>{a...});}
//io
struct SetUpIO{
SetUpIO(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout<<fixed<<setprecision(15);
}
}set_up_io;
//in
void scan(char &x){cin>>x;}
void scan(u32&x){cin>>x;}
void scan(u64 &x){cin>>x;}
void scan(i32 &x){cin>>x;}
void scan(i64 &x){cin>>x;}
void scan(string &x){cin>>x;}
void scan(mint &x){cin>>x;}
template<class T1,class T2>void scan(pair<T1,T2> &x){scan(x.first);scan(x.second);}
template<class T>void scan(V<T> &x){for(T &ele:x){scan(ele);}}
template<class T>void scan(deque<T> &x){for(T &ele:x){scan(ele);}}
template<class T,i32 size>void scan(array<T,size> &x){for(T &ele:x){scan(ele);}}
template<class T,i32 size>void scan(T (&x)[size]){for(T &ele:x){scan(ele);}}
void rd(){}
template<class Head,class... Tail>void rd(Head &head,Tail &...tail){scan(head);rd(tail...);}
#define CHR(...) char __VA_ARGS__;rd(__VA_ARGS__)
#define U32(...) u32 __VA_ARGS__;rd(__VA_ARGS__)
#define U64(...) u64 __VA_ARGS__;rd(__VA_ARGS__)
#define I32(...) i32 __VA_ARGS__;rd(__VA_ARGS__)
#define I64(...) i64 __VA_ARGS__;rd(__VA_ARGS__)
#define UINT(...) u32 __VA_ARGS__;rd(__VA_ARGS__)
#define ULL(...) u64 __VA_ARGS__;rd(__VA_ARGS__)
#define INT(...) i32 __VA_ARGS__;rd(__VA_ARGS__)
#define LL(...) i64 __VA_ARGS__;rd(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;rd(__VA_ARGS__)
#define VEC(type,name,size) V<type> name(size);rd(name);
#define VVEC(type,name,size1,size2) VV<type> name(size1,V<type>(size2));rd(name)
//out
void print(){putchar(' ');}
void print(bool x){printf("%d",x);}
void print(u32 x){printf("%u",x);}
void print(u64 x){printf("%llu",x);}
void print(i32 x){printf("%d",x);}
void print(i64 x){printf("%lld",x);}
void print(char x){printf("%c",x);}
void print(f64 x){printf("%.15f",x);}
void print(f80 x){printf("%.15Lf",x);}
void print(const string &x){for(auto&&i:x)print(i);}
void print(mint x){printf("%d",x.val());}
template<class T>void print(const V<T>&);
template<class T1,class T2>void print(const pair<T1,T2>&x){print(x.first);putchar(' ');print(x.second);}
template<class T>void print(complex<T>&x){if(x.real()>=0)print('+');print(x.real());if(x.imag()>=0)print('+');print(x.imag());print('i');}
template<class T>void print(const V<T>&x){if(x.empty())return;print(x[0]);for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}
template<class T>void print(const deque<T>&x){if(x.empty())return;print(x[0]);for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}
template<class T>void print(const set<T>&x){if(x.empty())return;print(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}
template<class T>void print(const unordered_set<T>&x){if(x.empty())return;print(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}
template<class T>void print(const multiset<T>&x){if(x.empty())return;print(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}
template<class T>void print(const unordered_multiset<T>&x){if(x.empty())return;print(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}
template<class T1,class T2>void print(map<T1,T2>&x){if(x.empty())return;print(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}
template<class T1,class T2>void print(unordered_map<T1,T2>&x){if(x.empty())return;print(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}
template<class T, size_t size> void print(const array<T, size>& x){ print(x[0]); for(auto i = x.begin(); ++i != x.end(); ){ putchar(' '); print(*i); } }
template<class T,i32 size>void print(const T(&x)[size]){print(x[0]);for(auto i=x;++i!=end(x);){/*putchar(' ');*/print(*i);}}
template<class T>void print(const T&a){cout<<a;}
int out(){putchar('\n');return 0;}
template<class T>int out(const T&t){print(t);putchar('\n');return 0;}
template<class Head,class... Tail>int out(const Head&head,const Tail&...tail){print(head);putchar(' ');out(tail...);return 0;}
#ifdef LOCAL
void dbg(){putchar(' ');}
void dbg(bool x){printf("%d",x);}
void dbg(u32 x){printf("%u",x);}
void dbg(u64 x){printf("%llu",x);}
void dbg(i32 x){printf("%d",x);}
void dbg(i64 x){printf("%lld",x);}
void dbg(char x){printf("%c",x);}
void dbg(f64 x){printf("%.15f",x);}
void dbg(f80 x){printf("%.15Lf",x);}
void dbg(const string &x){for(auto&&i:x)dbg(i);}
void dbg(mint x){printf("%d",x.val());}
template<class T>void dbg(const V<T>&);
template<class T1,class T2>void dbg(const pair<T1,T2>&x){putchar('(');dbg(x.first);putchar(',');dbg(x.second);putchar(')');}
template<class T>void dbg(complex<T>&x){if(x.real()>=0)dbg('+');dbg(x.real());if(x.imag()>=0)dbg('+');dbg(x.imag());dbg('i');}
template<class T>void dbg(const V<T>&x){putchar('[');if(!x.empty()){dbg(x[0]);for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i);}}putchar(']');}
template<class T>void dbg(const deque<T>&x){putchar('[');if(!x.empty()){dbg(x[0]);for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i);}}putchar(']');}
template<class T>void dbg(const set<T>&x){putchar('{');if(!x.empty()){dbg(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i);}}putchar('}');}
template<class T>void dbg(const unordered_set<T>&x){putchar('{');if(!x.empty()){dbg(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i);}}putchar('}');}
template<class T>void dbg(const multiset<T>&x){putchar('{');if(!x.empty()){dbg(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i);}}putchar('}');}
template<class T>void dbg(const unordered_multiset<T>&x){putchar('{');if(!x.empty()){dbg(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i);}}putchar('}');}
template<class T1,class T2>void dbg(map<T1,T2>&x){putchar('{');if(!x.empty()){dbg(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i);}}putchar('}');}
template<class T1,class T2>void dbg(unordered_map<T1,T2>&x){putchar('{');if(!x.empty()){dbg(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i);}}putchar('}');}
template<class T, size_t size> void dbg(const array<T, size>& x){ putchar('[');dbg(x[0]); for(auto i = x.begin(); ++i != x.end(); ){ putchar(','); dbg(*i); } putchar(']');}
template<class T,i32 size>void dbg(const T(&x)[size]){/*putchar('[');*/dbg(x[0]);for(auto i=x;++i!=end(x);){/*putchar(' ')*/;dbg(*i);}/*putchar(']');*/}
template<class T>void dbg(const T&a){cout<<a;}
int dbg2(){putchar('\n');return 0;}
template<class T>int dbg2(const T&t){dbg(t);putchar('\n');return 0;}
template<class Head,class... Tail>int dbg2(const Head&head,const Tail&...tail){dbg(head);putchar(' ');dbg2(tail...);return 0;}
#define debug(...) {dbg((string)(#__VA_ARGS__));dbg(":");dbg2(__VA_ARGS__);}
#else
#define debug(...) void(0)
#endif
//random
random_device rnd;mt19937 mt(rnd());const i64 MT_MAX=LINF;
uniform_int_distribution<i64> RAND(0,MT_MAX);
f64 randd(){return 1.0*RAND(mt)/MT_MAX;}
//random value [a,b]
i64 randint(i64 a,i64 b){return a+RAND(mt)%(b-a+1);}
//funtion2
#define extrep(v,...) for(auto v:__MAKE_MAT__({__VA_ARGS__}))
vector<vector<i64>> __MAKE_MAT__(vector<i64> v){
if(v.empty())return vector<vector<i64>>(1,vector<i64>());
i64 n=v.back();v.pop_back();vector<vector<i64>> ret,tmp=__MAKE_MAT__(v);
for(auto e:tmp)for(i64 i=0;i<n;++i){ret.push_back(e);ret.back().push_back(i);}
return ret;
}
//V',Pを返す。PはVを昇順に並べた時のidx
template<class T>
pair<vector<T>,vector<i32>> sortperm(vector<T> v){
vector<pair<T,int>> sv;
for(i32 i=0;i<(i32)v.size();i++){sv.push_back({v[i],i});}
sort(sv.begin(),sv.end());vector<T> rv;vector<i32> p;
for(auto[x,idx]:sv){rv.push_back(x);p.push_back(idx);}
return {rv,p};
}
i64 pow(i64 a,i64 b){i64 x=1;while(b){if(b&1){x*=a;}a=a*a;b>>=1;}return x;}
bool isupper(char x){return('A'<=x&&x<='Z');}
bool islower(char x){return('a'<=x&&x<='z');}
char upper(char &x){if(isupper(x)){return x;}return x-'a'+'A';}
char lower(char &x){if(islower(x)){return x;}return x-'A'+'a';}
string upper(string s){for(auto&e:s)e=upper(e);return s;}
string lower(string s){for(auto&e:s)e=lower(e);return s;}
bool isdigit(char x){return('0'<=x&&x<='9');}
bool ingrid(int x,int y,int h,int w){return 0<=x&&x<h&&0<=y&&y<w;}
#pragma endregion
//math
namespace nouka28{
random_device rnd;
mt19937 mt(rnd());
const long long MT_MAX=(1LL<<62)-1;
uniform_int_distribution<long long> rd(0,MT_MAX);
double randd(){
return 1.0*rd(mt)/MT_MAX;
}
long long randint(long long a,long long b){
// [a,b]の乱数を生成
return a+rd(mt)%(b-a+1);
}
template<class T=long long>
vector<T> Quotients(T n){
vector<T> retl,retr;
for(int i=1;i*i<=n;i++){
retl.push_back(i);
if(i<n/i)retr.push_back(n/i);
}
reverse(retr.begin(),retr.end());
retl.insert(retl.end(),retr.begin(),retr.end());
return retl;
}
template<class T=long long>T ceil_sqrt(T n){
T l=-1,r=n;
while(r-l>1){
T m=(l+r)>>1;
if(m*m>=n)r=m;
else l=m;
}
return r;
}
//ceil(a/b)
template<class T=long long>T ceil(T a,T b){
if(a>=0){
return (a+b-1)/b;
}else{
return (a)/b;
}
};
//floor(a/b)
template<class T=long long>T floor(T a,T b){
if(a>=0){
return a/b;
}else{
return -(-a+b-1)/b;
}
};
//x^y mod m
template<class T=long long>T modpow(T x,T y,T m){
T res=1%m;x%=m;
while(y){
if(y%2)res=(res*x)%m;
x=(x*x)%m;
y>>=1;
}
return res;
}
//a^0+a^1+..+a^(n-1) (mod m)
template<class T>
T geometric_progression(T a,T n,T m){
if(n==0)return 0;
if(n%2==1){
return (geometric_progression(a,n-1,m)*a+1)%m;
}else{
return (geometric_progression(a*a%m,n/2,m)*(1+a))%m;
}
};
//素数判定(高速)
bool is_prime(long long n){
if(n<=1)return 0;
if(n==2)return 1;
if(n%2==0)return 0;
long long s=0,d=n-1;
while(d%2==0)d/=2,s++;
if(n<4759123141LL){
for(long long e:{2,7,61}){
if(n<=e)break;
long long t,x=modpow<__int128_t>(e,d,n);
if(x!=1){
for(t=0;t<s;t++){
if(x==n-1)break;
x=__int128_t(x)*x%n;
}
if(t==s)return 0;
}
}
return 1;
}else{
for(long long e:{2,325,9375,28178,450775,9780504,1795265022}){
if(n<=e)break;
long long t,x=modpow<__int128_t>(e,d,n);
if(x!=1){
for(t=0;t<s;t++){
if(x==n-1)break;
x=__int128_t(x)*x%n;
}
if(t==s)return 0;
}
}
return 1;
}
}
//Xor Shift
unsigned xor_shift_rng(){
static unsigned tx=123456789,ty=362436069,tz=521288629,tw=88675123;
unsigned tt=(tx^(tx<<11));
tx=ty,ty=tz,tz=tw;
return (tw=(tw^(tw>>19))^(tt^(tt>>8)));
}
//ロー法 Nを割り切る素数を見つける
long long pollard(long long n){
if(n%2==0)return 2;
if(is_prime(n))return n;
long long step=0;
while(true){
long long r=(long long)xor_shift_rng();
auto f=[&](long long x)->long long {return ((__int128_t(x)*x)%n+r)%n;};
long long x=++step,y=f(x);
while(true){
long long p=gcd(abs(y-x),n);
if(p==0||p==n)break;
if(p!=1)return p;
x=f(x);
y=f(f(y));
}
}
}
//internal fast factrize vector
void _internal_factrize_vector(long long n,vector<long long>&v){
if(n==1)return;
long long p=pollard(n);
if(p==n){v.push_back(p);return;}
_internal_factrize_vector(p,v);
_internal_factrize_vector(n/p,v);
}
//fast factrize vector
vector<long long> factrize_vector(long long n){
vector<long long> res;
_internal_factrize_vector(n,res);
sort(res.begin(),res.end());
return res;
}
//internal fast factrize map
void _internal_factrize_map(long long n,map<long long,long long>&v){
if(n==1)return;
long long p=pollard(n);
if(p==n){v[p]++;return;}
_internal_factrize_map(p,v);
_internal_factrize_map(n/p,v);
}
//fast factrize map
map<long long,long long> factrize_map(long long n){
map<long long,long long> res;
_internal_factrize_map(n,res);
return res;
}
//fast factor
vector<long long> factor(long long n){
map<long long,long long> fm;_internal_factrize_map(n,fm);
vector<long long> res={1};
for(auto[i,j]:fm){
vector<long long> tmp;
int p=1;
for(long long k=0;k<=j;k++){
for(auto e:res){
tmp.push_back(e*p);
}
p*=i;
}
swap(res,tmp);
}
return res;
}
//euler phi function
long long euler_phi(long long n){
vector<long long> ps=factrize_vector(n);
ps.erase(unique(ps.begin(),ps.end()),ps.end());
for(long long p:ps){
n/=p;n*=(p-1);
}
return n;
}
//ax+by=gcd(a,b)
template<class T=long long>
tuple<T,T,T> extgcd(T a,T b){
T x1=1,y1=0,d1=a,x2=0,y2=1,d2=b;
while(d2!=0){
T q=d1/d2,u=d1-d2*q,v=x1-x2*q,w=y1-y2*q;
d1=d2;d2=u;x1=x2;x2=v;y1=y2;y2=w;
}
if(d1<0){
d1=-d1;x1=-x1;y1=-y1;
}
return {d1,x1,y1};
}
//x inverse (mod m)
long long modinv(long long a,long long m){
long long b=m,u=1,v=0;
while(b){
long long t=a/b;
a-=t*b;swap(a,b);
u-=t*v;swap(u,v);
}
u%=m;
if(u<0)u+=m;
return u;
}
//find primitive root
long long primitive_root(long long p){
vector<long long> f=factrize_vector(p-1);
f.erase(unique(f.begin(),f.end()),f.end());
while(1){
long long x=randint(1,p-1);
bool flg=1;
for(auto e:f)if(modpow<__int128_t>(x,(p-1)/e,p)==1){flg=0;break;}
if(flg)return x;
}
}
//x^k=y (mod m) gcd(x,m)=1 k>=0
long long discrete_logarithm_coprime_mod(long long x,long long y,long long m){
x%=m;y%=m;
if(y==1||m==1){
return 0;
}
if(x==0){
if(y==0)return 1;
else return -1;
}
long long M=ceil_sqrt(m),a=modpow(modinv(x,m),M,m);
unordered_map<long long,long long> mp;
long long pow_x=1;
for(long long i=0;i<M;i++){
if(!mp.count(pow_x))mp[pow_x]=i;
pow_x=pow_x*x%m;
}
long long ya=y;
for(long long i=0;i<M;i++){
if(mp.count(ya))return M*i+mp[ya];
ya=ya*a%m;
}
return -1;
}
//x^k=y (mod m) gcd(x,m)=1 k>=1
long long discrete_Nlogarithm_coprime_mod(long long x,long long y,long long m){
if(m==1){
if(x==1)return 1;
else return -1;
}
if(x==0){
if(y==0)return 1;
else return -1;
}
long long M=ceil_sqrt(m),a=modpow(modinv(x,m),M,m);
unordered_map<long long,long long> mp;
long long pow_x=1;
for(long long i=0;i<=M;i++){
if(!mp.count(pow_x))mp[pow_x]=i;
pow_x=pow_x*x%m;
}
long long ya=y;
for(long long i=0;i<M;i++){
if(ya==1&&i>0)return i*M;
else if(mp.count(ya))return M*i+mp[ya];
ya=ya*a%m;
}
return -1;
}
//x^k=y (mod m) k>=0
long long discrete_logarithm_arbitrary_mod(long long x,long long y,long long m){
if(m==1){
return 0;
}
x%=m;y%=m;
long long d,pow_x=1;
for(d=0;;d++){
if(!(m>>d))break;
if(pow_x==y){
return d;
}
pow_x=pow_x*x%m;
}
long long g=gcd(pow_x,m);
if(y%g!=0){
return -1;
}
m/=g;
long long z=y*modinv(pow_x,m),t=discrete_logarithm_coprime_mod(x,z,m);
if(t==-1)return -1;
else return d+t;
}
//x^k=y (mod m) k>=1
long long discrete_Nlogarithm_arbitrary_mod(long long x,long long y,long long m){
if(m==1){
if(x==1)return 1;
else return -1;
}
x%=m;y%=m;
long long d,pow_x=1;
for(d=0;;d++){
if(!(m>>d))break;
if(pow_x==y&&d){
return d;
}
pow_x=pow_x*x%m;
}
long long g=gcd(pow_x,m);
if(y%g!=0){
return -1;
}
m/=g;
long long z=y*modinv(pow_x,m),t;
if(d)t=discrete_logarithm_coprime_mod(x,z,m);
else t=discrete_Nlogarithm_coprime_mod(x,y,m);
if(t==-1)return -1;
else return d+t;
}
}
int main(){
INT(n,m);
VEC(int,a,n);
sort(ALL(a));
set<int> st;
set<int> ast(ALL(a));
rep(i,1,n){
auto ds=nouka28::factor(a[i]);
debug(ds);
bool f=0;
for(auto&&e:ds){
if(st.count(e)){
f=1;
}
}
if(f)continue;
for(int j=a[i];j<=m;j+=a[i]){
if(!ast.count(j)){
out(-1);
return 0;
}
}
st.insert(a[i]);
}
out(LEN(st));
out(st);
}