Brasil National Programming Challenge

Beautiful Badges.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

struct MaximumFlow {
	typedef int Index;
	typedef int Flow;
	static const Flow InfCapacity = INF;
	struct Edge {
		Index to;
		Flow capacity;
		Index rev;
	};
	vector<vector<Edge> > g;
	void init(Index n) { g.assign(n, vector<Edge>()); }
	void add(Index i, Index j, Flow capacity) {
		Edge e, f; e.to = j, f.to = i; e.capacity = capacity, f.capacity = 0;
		g[i].push_back(e); g[j].push_back(f);
		g[i].back().rev = (Index)g[j].size() - 1; g[j].back().rev = (Index)g[i].size() - 1;
	}
	void addB(Index i, Index j, Flow capacity) {
		Edge e, f; e.to = j, f.to = i; e.capacity = capacity, f.capacity = capacity;
		g[i].push_back(e); g[j].push_back(f);
		g[i].back().rev = (Index)g[j].size() - 1; g[j].back().rev = (Index)g[i].size() - 1;
	}
	//g?????
	Flow maximumFlow(int s, int t) {
		int n = g.size();
		vector<Index> level(n);
		Flow total = 0; bool update;
		do {
			update = false;
			fill(level.begin(), level.end(), -1); level[s] = 0;
			queue<Index> q; q.push(s);
			for(Index d = n; !q.empty() && level[q.front()] < d; ) {
				int u = q.front(); q.pop();
				if(u == t) d = level[u];
				each(e, g[u]) if(e->capacity > 0 && level[e->to] == -1)
					q.push(e->to), level[e->to] = level[u] + 1;
			}
			vector<Index> iter(n);
			for(Index i = 0; i < n; i ++) iter[i] = (int)g[i].size() - 1;
			while(1) {
				Flow f = augment(level, iter, s, t, InfCapacity);
				if(f == 0) break;
				total += f; update = true;
			}
		}while(update);
		return total;
	}
	Flow augment(vector<Index> &level, vector<Index> &iter, Index u, Index t, Flow f) {
		if(u == t || f == 0) return f;
		Index lv = level[u];
		if(lv == -1) return 0;
		level[u] = -1;
		for(; iter[u] >= 0; -- iter[u]) {
			Edge &e = g[u][iter[u]];
			if(level[e.to] <= lv) continue;
			Flow l = augment(level, iter, e.to, t, min(f, e.capacity));
			if(l == 0) continue;
			e.capacity -= l; g[e.to][e.rev].capacity += l;
			level[u] = lv;
			return l;
		}
		return 0;
	}
};


int main() {
	int n;
	scanf("%d", &n);
	const int D = 1000;
	vector<int> blue(D, 0), yellow(D, 0);
	rep(i, n) {
		int c, d;
		scanf("%d%d", &c, &d), -- c, -- d;
		if(c == 0) {
			++ blue[d];
		}else {
			++ yellow[d];
		}
	}
	int s = D * 2, t = s + 1;
	MaximumFlow mf;
	mf.init(t + 1);
	rep(d, D)
		mf.add(s, d, blue[d]);
	rer(x, 1, D) rer(y, 1, D) {
		int xx = x * x, yy = y * y;
		if(xx < 2 * yy && yy < 2 * xx)
			mf.add(x - 1, D + (y - 1), INF);
	}
	rep(d, D)
		mf.add(D + d, t, yellow[d]);
	int ans = mf.maximumFlow(s, t);
	printf("%d\n", ans);
	return 0;
}

Oliver and the battle.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

struct UnionFind {
	vector<int> data;
	void init(int n) { data.assign(n, -1); }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if(x != y) {
			if(data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) { return root(x) == root(y); }
	int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
	int size(int x) { return -data[root(x)]; }
};

int main() {
	int T;
	scanf("%d", &T);
	rep(ii, T) {
		int H, W;
		scanf("%d%d", &H, &W);
		vector<vector<bool> > ground(H, vector<bool>(W));
		rep(i, H) rep(j, W) {
			int g;
			scanf("%d", &g);
			ground[i][j] = g != 0;
		}
		UnionFind uf; uf.init(H * W);
		rep(i, H) rep(j, W) if(ground[i][j]) {
			rer(dy, -1, 1) rer(dx, -1, 1) if(dy || dx) {
				int yy = i + dy, xx = j + dx;
				if(!(0 <= yy && yy < H && 0 <= xx && xx < W)) continue;
				if(ground[yy][xx])
					uf.unionSet(i * W + j, yy * W + xx);
			}
		}
		int ans1 = 0, ans2 = 0;
		rep(i, H) rep(j, W) if(ground[i][j]) {
			ans1 += uf.root(i * W + j) == i * W + j;
			amax(ans2, uf.size(i * W + j));
		}
		printf("%d %d\n", ans1, ans2);
	}
	return 0;
}

Parade.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

template<int MOD>
struct ModInt {
	static const int Mod = MOD;
	unsigned x;
	ModInt(): x(0) { }
	ModInt(signed sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
	ModInt(signed long long sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
	int get() const { return (int)x; }
	
	ModInt &operator+=(ModInt that) { if((x += that.x) >= MOD) x -= MOD; return *this; }
	ModInt &operator-=(ModInt that) { if((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
	ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
	
	ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
	ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
	ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
};
typedef ModInt<1000000007> mint;

int main() {
	int T;
	scanf("%d", &T);
	rep(ii, T) {
		int N, M;
		scanf("%d%d", &N, &M);
		vector<int> L(N), C(N);
		rep(i, N)
			scanf("%d%d", &L[i], &C[i]), -- L[i], -- C[i];
		vector<vi> g(N);
		rep(i, N) if(L[i] != -1)
			g[L[i]].push_back(i);
		vi A;
		rep(i, N) if(L[i] == -1) {
			if(!A.empty()) return 1;
			int j = i;
			while(1) {
				A.push_back(C[j]);
				if(g[j].empty()) break;
				if(g[j].size() != 1) return 1;
				j = g[j][0];
			}
		}
		if(A.size() != N) return 1;
		const int X = 1000;
		mint ans = 0;
		vector<vector<mint> > dp(X, vector<mint>(M+1, 0));
		vector<mint> sums(M+1, 0);
		sums[0] = 1;
		rep(i, N) {
			int a = A[i];
			for(int j = M; j >= 1; -- j) {
				mint t = sums[j-1];
				t -= dp[a][j];
				dp[a][j] += t;
				sums[j] += t;
				ans += t;
			}
		}
		printf("%d\n", ans.get());
	}
	return 0;
}

Sherif and The BOMBS.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

int sq(int x) { return x*x; }
int main() {
	const int W = 1000;
	vector<vi> cnt(W+1, vector<int>(W+1, 0));
	int N;
	scanf("%d", &N);
	rep(ii, N) {
		int X, Y, R;
		scanf("%d%d%d", &X, &Y, &R);
		int rr = R * R;
		rer(y, 1, W) rer(x, 1, W) {
			int d = sq(x-X) + sq(y-Y);
			if(d <= rr)
				++ cnt[y][x];
		}
	}
	int ans = 0;
	rer(y, 1, W) rer(x, 1, W)
		ans += cnt[y][x] >= 2;
	printf("%d\n", ans);
	return 0;
}

The Power of Factorization.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <unordered_map>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

template<typename T>T gcd(T x, T y){if(y==0)return x;else return gcd(y,x%y);}



vector<bool> isprime;
vector<int> primes;
void sieve(int n){
	if((int)isprime.size() >= n+1) return;
	isprime.assign(n+1, true);
	isprime[0] = isprime[1] = false;
	int sqrtn = (int)(sqrt(n * 1.) + .5);
	for(int i = 2; i <= sqrtn; i ++) if(isprime[i]) {
		for(int j = i * i; j <= n; j += i)
			isprime[j] = false;
	}
	primes.clear();
	for(int i = 2; i <= n; i ++) if(isprime[i])
		primes.push_back(i);
}

inline long long mulmodll(long long a, long long b, long long m) {
	long long quot, res;
	const unsigned HALF_OF_ONE = 0x3f000000;
#ifdef __GNUC__
//80bit???????????????
//#pragma STDC FENV_ACCESS on
//	unsigned short fcw;
//	asm ("fnstcw %0;" : "=m" (fcw));
//	unsigned short fcw_s = fcw;
//	fcw |= 3<<8;
//	asm ("fldcw %0;" : : "m" (fcw));
	asm (
		"fildq %1;\n\t"
		"fildq %2;\n\t"
		"fmulp;\n\t"
		"fildq %3;\n\t"
		"fdivrp;\n\t"
		"fadd %4;\n\t"
		"fisttpq %0;"
		: "=m" (quot)
		: "m" (a), "m" (b), "m" (m), "m"(HALF_OF_ONE)
		: "st(2)"
		);
//	asm ("fldcw %0;" : : "m" (fcw_s));
//#pragma STDC FENV_ACCESS off
#else
#pragma STDC FENV_ACCESS on
	unsigned short fcw;
	//??80bit????????
	__asm {
		fnstcw word ptr [fcw];
		mov ax, [fcw];
		or word ptr [fcw], 3<<8;
		fldcw word ptr [fcw];

		fild qword ptr [a];
		fild qword ptr [b];
		fmulp st(1), st(0);
		fild qword ptr [m];
		fdivp st(1), st(0);
		fadd dword ptr [HALF_OF_ONE];
		fisttp qword ptr [quot];

		mov [fcw], ax;
		fldcw word ptr [fcw];
	};
#pragma STDC FENV_ACCESS off
#endif
	res = a * b - m * quot;
	if(res < 0) res += m;
	return res;
}

long long powmodll(long long a, long long k, long long MOD) {
	unsigned long long r = MOD == 1 ? 0 : 1;
	while(k) {
		if(k & 1)
			r = mulmodll(r, a, MOD);
		a = mulmodll(a, a, MOD);
		k >>= 1;
	}
	return r;
}

#ifdef WIN32
extern "C" int __stdcall QueryPerformanceFrequency(long long*);
extern "C" int __stdcall QueryPerformanceCounter(long long*);
double getTime() {
	long long c, freq;
	QueryPerformanceCounter(&c);
	QueryPerformanceFrequency(&freq);
	return c * 1. / freq;
}
#else
#include <sys/time.h>
double getTime() {
	struct timeval tv;
	gettimeofday(&tv, NULL);
	return tv.tv_sec + tv.tv_usec / 1e6;
}
#endif

typedef long long FactorsInt;
typedef vector<pair<FactorsInt,int> > Factors;

template<typename Op> inline Factors combineFactors(Op op, int id, const Factors &a, const Factors &b) {
	Factors c;
	int an = a.size(), bn = b.size();
	int ai = 0, bi = 0;
	while(ai < an || bi < bn) {
		typename Factors::value_type::first_type p; int q;
		if(ai < an && (bi >= bn || a[ai].first < b[bi].first)) {
			p = a[ai].first, q = op(a[ai].second, id);
			ai ++;
		}else if(bi < bn && (ai >= an || a[ai].first > b[bi].first)) {
			p = b[bi].first, q = op(id, b[bi].second);
			bi ++;
		}else {
			p = a[ai].first, q = op(a[ai].second, b[bi].second);
			ai ++, bi ++;
		}
		if(q != 0) c.push_back(mp(p, q));
	}
	return c;
}

Factors productFactors(const Factors &a, const Factors &b) {
	return combineFactors(std::plus<int>(), 0, a, b);
}

long long pollardRho(long long n, int seed) {
	if(n <= 1) return -1;
	if(n > 2 && n % 2 == 0) return 2;
	seed %= n;
	long long x = 2;
	for(long long j = 1; ; j <<= 1) {
		long long y = x;
		for(int i = 0; i < j; ++ i) {
			if((x = (mulmodll(x, x, n) + seed) >= n)) x -= n;
			long long d = gcd(abs(x - y), n);
			if(d != 1) return d < n ? d : -1;
		}
	}
}

bool millarRabin(long long n) {
	if (n <= 1 || (n > 2 && n % 2 == 0)) return false;
	int test[] = {2,3,5,7,11,13,17,19,23,-1};
	long long d = n - 1; int s = 0;
	while (d % 2 == 0) ++ s, d /= 2;
	for(int i = 0; ; ++i) {
		long long a = test[i];
		if(a == -1 || a >= n) break;
		long long x = powmodll(a, d, n);
		if(x == 1) continue;
		int r;
		for(r = 0; r < s; ++r) {
			if(x == n - 1) break;
			x = mulmodll(x, x, n);
		}
		if(r == s) return false;
	}
	return true;
}

void factor(long long X, Factors &factors) {
	factors.clear();
	if(millarRabin(X)) {
		factors.push_back(mp(X, 1));
		return;
	}
	each(pt, primes) {
		int p = *pt;
		if((long long)p * p > X) break;
		if(X % p != 0) continue;
		X /= p;
		int k = 1;
		while(X % p == 0) {
			++ k;
			X /= p;
		}
		factors.push_back(mp(p, k));
	}
	if(X == 1) return;
	if(millarRabin(X)) {
		factors.push_back(mp(X, 1));
		return;
	}
	rep(iter, 1000) {
		long long d = pollardRho(X, iter);
		if(d != -1) {
			Factors a;
			factor(d, a);
			factors = productFactors(factors, a);
			X /= d;
			if(millarRabin(X)) {
				factors.push_back(mp(X, 1));
				return;
			}
		}
	}
//	cerr << "failed to factor: " << X << endl;
	factors.push_back(mp(X, 1));
}


long long powk(long long x, int k) {
	long long r = x;
	rep(i, k-1)
		r *= x;
	return r;
}

int rooti(long long x, int k) {
	if(k <= 1) return -1;
	int r;
	if(k == 2) r = (int)sqrt(x * 1.L);
	else if(k == 3) r = (int)cbrt(x * 1.L);
	else r = (int)pow(x * 1.L, 1.L / k);
	long long p = powk(r, k);
	if(p > x) {
		do -- r; while(powk(r, k) > x);
	}else {
		while(powk(r+1, k) <= x) ++ r;
	}
	return r;
}

bool perfectPower(long long x, int &y, int &k) {
	rer(i, 2, 10) {
		int r = rooti(x, i);
		if(powk(r, i) == x) {
			y = r, k = i;
			return true;
		}
	}
	y = k = -1;
	return false;
}

const int MaxK = 60;
char gcdTable[MaxK+1][MaxK+1];
vi powerChains[MaxK+1];

void powerChain(int x, vector<int> &v) {
	if(x == 1) return;
	int y, k;
	if(!perfectPower(x, y, k)) {
		v.push_back(x);
	}else {
		powerChain(y, v);
		v.push_back(k);
	}
}


struct Xor128 {
	unsigned x, y, z, w;
	Xor128(): x(123456789), y(362436069), z(521288629), w(88675123) { }
	unsigned next() {
		unsigned t = x ^ (x << 11);
		x = y; y = z; z = w;
		return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
	}
	unsigned long long nextll() {
		unsigned long long x = (unsigned long long)next() << 32;
		return x | next();
	}
} xor128;

vector<vector<long long> > bestsubarrays;
int bestN; int bestM;
Factors factors;
double timeLimit;

vector<vector<char> > representparts;
vector<char> curparts;
vector<vector<char> > partssets;
vector<char> exponentdivisors;
unordered_map<unsigned,int> memo[61];
unsigned cnthashseed[61];
unsigned cnthash;
int curN = 0;

void findPartitions2rec(vector<char> &counts);

void findPartitions2rec2(int i, int g, vector<char> &counts) {
	if(i < g) {
		if(curparts.empty())
			return;
		partssets.push_back(curparts);
		curparts.clear();
		findPartitions2rec(counts);
		curparts = partssets.back();
		partssets.pop_back();
		return;
	}
	if((int)counts.size() > i && counts[i] > 0) {
		char pt = representparts[i].back();
		-- counts[i], representparts[i].pop_back(), cnthash -= cnthashseed[i];
		++ counts[i-g], representparts[i-g].push_back(pt), cnthash += cnthashseed[i-g];
		curparts.push_back(pt);
		int poppedback = 0;
		while(counts.size() > 1 && counts.back() == 0)
			counts.pop_back(), ++ poppedback;

		findPartitions2rec2(i, g, counts);

		rep(k, poppedback)
			counts.push_back(0);
		curparts.pop_back();
		-- counts[i-g], representparts[i-g].pop_back(), cnthash -= cnthashseed[i-g];
		++ counts[i], representparts[i].push_back(pt), cnthash += cnthashseed[i];
	}
	findPartitions2rec2(i-1, g, counts);
}

void findPartitions2rec(vector<char> &counts) {
	int &memoized = memo[partssets.size()][cnthash];
	if(memoized >= curN) return;
	memoized = curN;
	if(counts.size() == 1) {
		int N = curN, M = partssets.size();
		if(bestN * M < N * bestM) {
			bestsubarrays.clear();
			rep(i, partssets.size()) {
				const vector<char> &s = partssets[i];
				int g = exponentdivisors[i];

				long long prod = 1;
				each(j, s) prod *= factors[*j].first;

				vector<long long> v;
				v.push_back(prod);
				v.insert(v.end(), all(powerChains[g]));
				bestsubarrays.push_back(v);
			}
			bestN = N, bestM = M;
/*
			cerr << "[";
			each(i, bestsubarrays) {
				if(i != bestsubarrays.begin()) cerr << "], [";
				each(j, *i) {
					if(j != i->begin()) cerr << ", ";
					cerr << *j;
				}
			}
			cerr << "]: " << N << " / " << M << " (" << N * 1. / M << ")" << endl;
//			*/
		}
		return;
	}
	for(int g = counts.size()-1; g >= 1; -- g) {
		exponentdivisors.push_back(g);
		curN += 1 + powerChains[g].size();
		findPartitions2rec2(counts.size()-1, g, counts);
		curN -= 1 + powerChains[g].size();
		exponentdivisors.pop_back();
	}
}

void findPartitions2() {
	int K = 0;
	each(i, factors) amax(K, i->second);
	representparts.assign(K+1, vector<char>());
	vector<char> counts(K+1, 0);
	cnthash = 0;
	each(i, factors) {
		++ counts[i->second];
		representparts[i->second].push_back(i - factors.begin());
	}
	rep(k, 61) memo[k].clear();
	rer(i, 0, K)
		cnthash += cnthashseed[i] * counts[i];
	memo[0][cnthash] = -1;
	findPartitions2rec(counts);
}


int main() {
	cnthashseed[0] = 1;
	rer(i, 1, 60)
		cnthashseed[i] = i * 1000000007;
	double absoluteLimit = getTime() + 2.;
	sieve(100000);
	rer(x, 0, MaxK) rer(y, 0, MaxK)
		gcdTable[x][y] = (char)gcd(x, y);
	rer(k, 1, MaxK)
		powerChain(k, powerChains[k]);
	int T;
	scanf("%d", &T);
	rep(ii, T) {
		long long X;
		scanf("%lld", &X);
		timeLimit = getTime() + (absoluteLimit - getTime()) / (T - ii) * 0.99;
//		X = xor128.nextll() % ((ll)1e18-1) + 2;
		if(X <= 1 || X > (ll)1e18) {
			cerr << "error X = " << X << endl;
			continue;
		}
		factor(X, factors);
//		cerr << "factor: "; each(i, factors) cerr << (i==factors.begin()?"":" * ") << i->first << "^" << i->second; cerr << endl;
		bestN = -1, bestM = 1;
		findPartitions2();
		{	vector<long long> A;
			vector<int> L, R;
			int offset = 0;
			each(i, bestsubarrays) {
				each(j, *i)
					A.push_back(*j);
				L.push_back(offset);
				offset += i->size();
				R.push_back(offset);
			}
			int N = A.size(), M = L.size();
			printf("%d %d\n", N, M);
			rep(i, N) {
				if(i != 0) putchar(' ');
				printf("%lld", A[i]);
			}
			puts("");
			rep(i, M)
				printf("%d %d\n", L[i] + 1, R[i]);
		}
	}
	return 0;
}