272cda822f 2017-08-19        kinaba: #include <iostream>
272cda822f 2017-08-19        kinaba: #include <sstream>
272cda822f 2017-08-19        kinaba: #include <iomanip>
272cda822f 2017-08-19        kinaba: #include <vector>
272cda822f 2017-08-19        kinaba: #include <string>
272cda822f 2017-08-19        kinaba: #include <map>
272cda822f 2017-08-19        kinaba: #include <set>
272cda822f 2017-08-19        kinaba: #include <algorithm>
272cda822f 2017-08-19        kinaba: #include <numeric>
272cda822f 2017-08-19        kinaba: #include <iterator>
272cda822f 2017-08-19        kinaba: #include <functional>
272cda822f 2017-08-19        kinaba: #include <complex>
272cda822f 2017-08-19        kinaba: #include <queue>
272cda822f 2017-08-19        kinaba: #include <stack>
272cda822f 2017-08-19        kinaba: #include <cmath>
272cda822f 2017-08-19        kinaba: #include <cassert>
272cda822f 2017-08-19        kinaba: #include <tuple>
272cda822f 2017-08-19        kinaba: using namespace std;
272cda822f 2017-08-19        kinaba: typedef long long LL;
272cda822f 2017-08-19        kinaba: typedef complex<double> CMP;
272cda822f 2017-08-19        kinaba: 
272cda822f 2017-08-19        kinaba: int gcd(int a, int b)
272cda822f 2017-08-19        kinaba: {
272cda822f 2017-08-19        kinaba: 	while (a)
272cda822f 2017-08-19        kinaba: 		swap(a, b %= a);
272cda822f 2017-08-19        kinaba: 	return b;
272cda822f 2017-08-19        kinaba: }
272cda822f 2017-08-19        kinaba: 
272cda822f 2017-08-19        kinaba: bool is_coprime(int a, int b)
272cda822f 2017-08-19        kinaba: {
272cda822f 2017-08-19        kinaba: 	return gcd(a, b) == 1;
272cda822f 2017-08-19        kinaba: }
272cda822f 2017-08-19        kinaba: 
272cda822f 2017-08-19        kinaba: class CoprimeMatrix { public:
272cda822f 2017-08-19        kinaba: 	vector<bool> is_p;
272cda822f 2017-08-19        kinaba: 	vector<int> primes;
272cda822f 2017-08-19        kinaba: 
272cda822f 2017-08-19        kinaba: 	string isPossible(vector <string> coprime)
272cda822f 2017-08-19        kinaba: 	{
272cda822f 2017-08-19        kinaba: 		// eratos
272cda822f 2017-08-19        kinaba: 		if (is_p.empty()) {
272cda822f 2017-08-19        kinaba: 			is_p.assign(60, true);
272cda822f 2017-08-19        kinaba: 			is_p[0] = is_p[1] = false;
272cda822f 2017-08-19        kinaba: 			for (int p = 2; p < is_p.size(); ++p) if (is_p[p]) {
272cda822f 2017-08-19        kinaba: 				primes.push_back(p);
272cda822f 2017-08-19        kinaba: 				for (int q = p + p; q < is_p.size(); q += p)
272cda822f 2017-08-19        kinaba: 					is_p[q] = false;
272cda822f 2017-08-19        kinaba: 			}
272cda822f 2017-08-19        kinaba: 		}
272cda822f 2017-08-19        kinaba: 
272cda822f 2017-08-19        kinaba: 		return solve(coprime) ? "Possible" : "Impossible";
272cda822f 2017-08-19        kinaba: 	}
272cda822f 2017-08-19        kinaba: 
272cda822f 2017-08-19        kinaba: 	bool solve(const vector<string>& coprime)
272cda822f 2017-08-19        kinaba: 	{
272cda822f 2017-08-19        kinaba: 		const int N = coprime.size();
272cda822f 2017-08-19        kinaba: 
272cda822f 2017-08-19        kinaba: 		// sanity
272cda822f 2017-08-19        kinaba: 		for (int i = 0; i < N; ++i)
272cda822f 2017-08-19        kinaba: 		for (int k = 0; k < N; ++k)
272cda822f 2017-08-19        kinaba: 			if (coprime[i][k] != coprime[k][i])
272cda822f 2017-08-19        kinaba: 				return false;
272cda822f 2017-08-19        kinaba: 
272cda822f 2017-08-19        kinaba: 		// trivial case
272cda822f 2017-08-19        kinaba: 		for (int i = 0; i < N; ++i)
272cda822f 2017-08-19        kinaba: 		for (int k = 0; k < N; ++k)
272cda822f 2017-08-19        kinaba: 			if (is_coprime(1 + i, 1 + k) != (coprime[i][k] == 'Y'))
272cda822f 2017-08-19        kinaba: 				goto nontrivial;
272cda822f 2017-08-19        kinaba: 		return true;
272cda822f 2017-08-19        kinaba: 
272cda822f 2017-08-19        kinaba: 	nontrivial:
272cda822f 2017-08-19        kinaba: 		for (int i = 0; i < N; ++i)
272cda822f 2017-08-19        kinaba: 			if(coprime[i][i]=='Y')
272cda822f 2017-08-19        kinaba: 				return false;
272cda822f 2017-08-19        kinaba: 
272cda822f 2017-08-19        kinaba: 		vector<vector<bool>> cos;
272cda822f 2017-08-19        kinaba: 		for (int off = 0; off < N; ++off) {
272cda822f 2017-08-19        kinaba: 			vector<bool> co;
272cda822f 2017-08-19        kinaba: 			for (int t = 0; t + off < N; ++t)
272cda822f 2017-08-19        kinaba: 				co.push_back(coprime[off][off + t] == 'Y');
272cda822f 2017-08-19        kinaba: 
272cda822f 2017-08-19        kinaba: 			// x+off coprime with k in 0,1,2,,,,co.size()-1 iff co[k]
272cda822f 2017-08-19        kinaba: 
272cda822f 2017-08-19        kinaba: 			if (!can(co))
272cda822f 2017-08-19        kinaba: 				return false;
272cda822f 2017-08-19        kinaba: 			cos.push_back(co);
272cda822f 2017-08-19        kinaba: 		}
272cda822f 2017-08-19        kinaba: 
272cda822f 2017-08-19        kinaba: 		for (int p = 2; p < N; ++p) if (is_p[p]) {
272cda822f 2017-08-19        kinaba: 			int last = -1;
272cda822f 2017-08-19        kinaba: 			for(int o=0; o<cos.size() && cos[o].size()>p; ++o)
272cda822f 2017-08-19        kinaba: 				if (cos[o][p] == false) {
272cda822f 2017-08-19        kinaba: 					if (last!=-1 && (o-last)!=p)
272cda822f 2017-08-19        kinaba: 						return false;
272cda822f 2017-08-19        kinaba: 					last = o;
272cda822f 2017-08-19        kinaba: 				}
272cda822f 2017-08-19        kinaba: 				else {
272cda822f 2017-08-19        kinaba: 					if (o - last >= p)
272cda822f 2017-08-19        kinaba: 						return false;
272cda822f 2017-08-19        kinaba: 				}
272cda822f 2017-08-19        kinaba: 		}
272cda822f 2017-08-19        kinaba: 
272cda822f 2017-08-19        kinaba: 		return true;
272cda822f 2017-08-19        kinaba: 	}
272cda822f 2017-08-19        kinaba: 
272cda822f 2017-08-19        kinaba: 	bool can(const vector<bool>& co)
272cda822f 2017-08-19        kinaba: 	{
272cda822f 2017-08-19        kinaba: 		// Can there be a positive n such that coprime(n,i) == co[i] ?
272cda822f 2017-08-19        kinaba: 		vector<int> prime_factors;
272cda822f 2017-08-19        kinaba: 		for (int p = 2; p < co.size(); ++p)
272cda822f 2017-08-19        kinaba: 			if (is_p[p] && !co[p])
272cda822f 2017-08-19        kinaba: 				prime_factors.push_back(p);
272cda822f 2017-08-19        kinaba: 
272cda822f 2017-08-19        kinaba: 		for (int k = 0; k < co.size(); ++k)
272cda822f 2017-08-19        kinaba: 			if (is_coprimev(k, prime_factors) != co[k]) {
272cda822f 2017-08-19        kinaba: 				prime_factors.push_back(primes.back());
272cda822f 2017-08-19        kinaba: 				for (int k = 0; k < co.size(); ++k)
272cda822f 2017-08-19        kinaba: 					if (is_coprimev(k, prime_factors) != co[k])
272cda822f 2017-08-19        kinaba: 						return false;
272cda822f 2017-08-19        kinaba: 				return true;
272cda822f 2017-08-19        kinaba: 			}
272cda822f 2017-08-19        kinaba: 		return true;
272cda822f 2017-08-19        kinaba: 	}
272cda822f 2017-08-19        kinaba: 
272cda822f 2017-08-19        kinaba: 	bool is_coprimev(int k, const vector<int>& pfs)
272cda822f 2017-08-19        kinaba: 	{
272cda822f 2017-08-19        kinaba: 		for (int p : pfs)
272cda822f 2017-08-19        kinaba: 			if (k%p == 0)
272cda822f 2017-08-19        kinaba: 				return false;
272cda822f 2017-08-19        kinaba: 		return true;
272cda822f 2017-08-19        kinaba: 	}
272cda822f 2017-08-19        kinaba: };
272cda822f 2017-08-19        kinaba: 
272cda822f 2017-08-19        kinaba: // BEGIN CUT HERE
272cda822f 2017-08-19        kinaba: #include <ctime>
272cda822f 2017-08-19        kinaba: double start_time; string timer()
272cda822f 2017-08-19        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
272cda822f 2017-08-19        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
272cda822f 2017-08-19        kinaba:  { os << "{ ";
272cda822f 2017-08-19        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
272cda822f 2017-08-19        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
272cda822f 2017-08-19        kinaba: void verify_case(const string& Expected, const string& Received) {
272cda822f 2017-08-19        kinaba:  bool ok = (Expected == Received);
272cda822f 2017-08-19        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
272cda822f 2017-08-19        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
272cda822f 2017-08-19        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
272cda822f 2017-08-19        kinaba: #define END	 verify_case(_, CoprimeMatrix().isPossible(coprime));}
272cda822f 2017-08-19        kinaba: int main(){
272cda822f 2017-08-19        kinaba: 
272cda822f 2017-08-19        kinaba: CASE(0)
272cda822f 2017-08-19        kinaba: 	string coprime_[] = {"NYNYN",
272cda822f 2017-08-19        kinaba:  "YNYYN",
272cda822f 2017-08-19        kinaba:  "NYNYN",
272cda822f 2017-08-19        kinaba:  "YYYNY",
272cda822f 2017-08-19        kinaba:  "NNNYN"};
272cda822f 2017-08-19        kinaba: 	  vector <string> coprime(coprime_, coprime_+sizeof(coprime_)/sizeof(*coprime_));
272cda822f 2017-08-19        kinaba: 	string _ = "Possible";
272cda822f 2017-08-19        kinaba: END
272cda822f 2017-08-19        kinaba: CASE(1)
272cda822f 2017-08-19        kinaba: 	string coprime_[] = {"NY",
272cda822f 2017-08-19        kinaba:  "NN"};
272cda822f 2017-08-19        kinaba: 	  vector <string> coprime(coprime_, coprime_+sizeof(coprime_)/sizeof(*coprime_));
272cda822f 2017-08-19        kinaba: 	string _ = "Impossible";
272cda822f 2017-08-19        kinaba: END
272cda822f 2017-08-19        kinaba: CASE(2)
272cda822f 2017-08-19        kinaba: 	string coprime_[] = {"NYYYYN",
272cda822f 2017-08-19        kinaba:  "YNYNNN",
272cda822f 2017-08-19        kinaba:  "YYNYYY",
272cda822f 2017-08-19        kinaba:  "YNYNYN",
272cda822f 2017-08-19        kinaba:  "YNYYNY",
272cda822f 2017-08-19        kinaba:  "NNYNYN"};
272cda822f 2017-08-19        kinaba: 	  vector <string> coprime(coprime_, coprime_+sizeof(coprime_)/sizeof(*coprime_));
272cda822f 2017-08-19        kinaba: 	string _ = "Possible";
272cda822f 2017-08-19        kinaba: END
272cda822f 2017-08-19        kinaba: CASE(3)
272cda822f 2017-08-19        kinaba: 	string coprime_[] = {"NN",
272cda822f 2017-08-19        kinaba:  "NN"};
272cda822f 2017-08-19        kinaba: 	  vector <string> coprime(coprime_, coprime_+sizeof(coprime_)/sizeof(*coprime_));
272cda822f 2017-08-19        kinaba: 	string _ = "Impossible";
272cda822f 2017-08-19        kinaba: END
272cda822f 2017-08-19        kinaba: CASE(4)
272cda822f 2017-08-19        kinaba: // both x and x+1 and x+2 are coprime with 2
272cda822f 2017-08-19        kinaba: 	string coprime_[] =
272cda822f 2017-08-19        kinaba: {
272cda822f 2017-08-19        kinaba: 	"NYYY",
272cda822f 2017-08-19        kinaba: 	"YNYY",
272cda822f 2017-08-19        kinaba: 	"YYNY",
272cda822f 2017-08-19        kinaba: 	"YYYN",
272cda822f 2017-08-19        kinaba: };
272cda822f 2017-08-19        kinaba: 	  vector <string> coprime(coprime_, coprime_+sizeof(coprime_)/sizeof(*coprime_));
272cda822f 2017-08-19        kinaba: 	string _ = "Impossible";
272cda822f 2017-08-19        kinaba: END
272cda822f 2017-08-19        kinaba: CASE(5)
272cda822f 2017-08-19        kinaba: // x+1 == 1
272cda822f 2017-08-19        kinaba: string coprime_[] = { "NY", "YY" };
272cda822f 2017-08-19        kinaba: 	  vector <string> coprime(coprime_, coprime_+sizeof(coprime_)/sizeof(*coprime_));
272cda822f 2017-08-19        kinaba: 	string _ = "Impossible";
272cda822f 2017-08-19        kinaba: END
272cda822f 2017-08-19        kinaba: CASE(6)
272cda822f 2017-08-19        kinaba: string coprime_[] = { "Y" };
272cda822f 2017-08-19        kinaba: vector <string> coprime(coprime_, coprime_ + sizeof(coprime_) / sizeof(*coprime_));
272cda822f 2017-08-19        kinaba: string _ = "Possible";
272cda822f 2017-08-19        kinaba: END
272cda822f 2017-08-19        kinaba: }
272cda822f 2017-08-19        kinaba: // END CUT HERE