/***********Template Starts Here***********/ //#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define pb push_back #define nl puts ("") #define sp printf ( " " ) #define phl printf ( "hello\n" ) #define ff first #define ss second #define POPCOUNT __builtin_popcountll #define RIGHTMOST __builtin_ctzll #define LEFTMOST(x) (63-__builtin_clzll((x))) #define MP make_pair #define CLR(x,y) memset(x,y,sizeof(x)) #define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end()) #define MIN(a,b) ((a)<(b)?(a):(b)) #define MAX(a,b) ((a)>(b)?(a):(b)) #define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1) #define SQ(x) ((x)*(x)) #define ABS(x) ((x)<0?-(x):(x)) #define FABS(x) ((x)+eps<0?-(x):(x)) #define ALL(x) (x).begin(),(x).end() #define LCM(x,y) (((x)/gcd((x),(y)))*(y)) #define SZ(x) ((vlong)(x).size()) #define NORM(x) if(x>=mod)x-=mod; #define MOD(x,y) (((x)*(y))%mod) #define ODD(x) (((x)&1)==0?(0):(1)) using namespace std; typedef long long vlong; typedef unsigned long long uvlong; typedef pair < vlong, vlong > pll; typedef vector vll; typedef vector vl; const vlong inf = 2147383647; const double pi = 2 * acos ( 0.0 ); const double eps = 1e-9; struct debugger{ template debugger& operator , (const T& v){ cerr<>= 1; } return res; } inline vlong bigmod ( vlong a, vlong p, vlong m ) { vlong res = 1 % m, x = a % m; while ( p ) { if ( p & 1 ) res = ( res * x ) % m; x = ( x * x ) % m; p >>= 1; } return res; } /***********Extended****************/ #define sc(x) scanf("%d",&x) #define scl(x) scanf("%lld",&x) #define scc(x,y) scanf("%d %d",&x,&y) #define sccl(x,y) scanf("%lld %lld",&x,&y) #define sccc(x,y,z) scanf("%d %d %d",&x,&y,&z) #define scccl(x,y,z) scanf("%lld %lld %lld",&x,&y,&z) #define prc(c) printf("Case %d: ",c) #define prn(c) printf("Case %d:\n",c) #define pr(c) printf("%d\n",c) #define prl(c) printf("%lld\n",c) #define FORL(x,y,z) for(int x = y ; x=z; x--) #define lli long long int //int dx[] = {-1,1,0,0}; //int dy[] = {0,0,-1,1}; /***********Template Ends Here***********/ /* int flag[50005]; int prime[50005]; int ind = 0; void sieve(){ flag[0] = 1; flag[1] = 1; for(int i=4;i<=50000;i+=2) flag[i]++; prime[0] = 2; ind = 1; for(int i=3;i<=50000;i+=2){ if(!flag[i]){ prime[ind] = i; ind++; for(int j=i+i;j<=50000;j+=i) flag[j]++; } } // cout<>n){ if(n==1) cout<<-1<