Problem: integers_as_service (2019 round3)

Looking for a new direction for his company, Carlos wants to break into the
most exciting tech field: digital rights management (DRM). In the world of
DRM, mega-corporations wage perpetual war against a vast sea of e-pirates,
modern-day Robin Hoods of ambiguous moral character.

One of the biggest players in this struggle is Sony, the well-known
copyrighter of numbers. Considering the speed with which Sony puts out new
products, it's no wonder they're having trouble coming up with enough secret
encryption keys to protect all of their intellectual property. Enter Carlos.

_ "Gone are the days of paying over-priced number theory PhDs to craft primes
by hand. I can make you a system that will generate all the numbers you need,
to your exact specifications." _

Sony wants to see a demonstration of Carlos's system before forking over
millions of dollars in consultancy fees. They have some new products in
development, each of which requires a secret key, **X**. For each key, Sony
has a list of **N** requirements. The _i_th requirement has an operator
character **Oi**, an integer value **Vi**, and an integer result **Ri**.

When **Oi** is 'G', the _i_th requirement states that the greatest common
divisor of **X** and **Vi** must be **Ri**. That is, `GCD(X, Vi) = Ri`.

When **Oi** is 'L', the _i_th requirement states that the least common
multiple of **X** and **Vi** must be **Ri**. That is, `LCM(X, Vi) = Ri`.

There is also a global requirement that all of Sony's secret keys must be
positive integers no larger than 1,000,000,000. Help Carlos build any positive
integer **X** consistent with all of these requirements, or determine that no
such integer exists.

### Input

Input begins with an integer **T**, the number of secret keys that Sony wants
Carlos to generate. For each number, there is first a line containing the
integer **N**. Then, **N** lines follow, the _i_th of which contains the
character **Oi**, and the integers **Vi** and **Ri**, all separated by spaces.

### Output

For the _i_th secret key, print a line containing "Case #_i_: " followed by a
single integer: your chosen value of **X**, or -1 if no valid integer **X**
exists.

### Constraints

1 ≤ **T** ≤ 250  
1 ≤ **N** ≤ 2,000  
**Oi** ∈ {'G', 'L'}   
1 ≤ **Vi**, **Ri** ≤ 1,000,000,000  

### Explanation of Sample

In the first case, `GCD(6, 4) = 2`, meaning that **X** = 6 satisfies the one
and only requirement. Note that, for this case and potentially other cases
below, **various other outputs will also be accepted**.

In the second case, there exists no valid integer **X** such that 1 ≤ **X** ≤
1,000,000,000 and `LCM(X, 4) = 2`.

In the third case, `GCD(24, 18) = 6`, `LCM(24, 40) = 120`, and `GCD(24, 20) =
4`, meaning that **X** = 24 is a valid choice.



Sample input:
12
1
G 4 2
1
L 4 2
3
G 18 6
L 40 120
G 20 4
3
G 36 9
L 10 90
G 24 6
4
G 259904673 63
L 42155313 885261573
G 778065480 60597
L 20448 963734688
3
G 3204696 72834
G 1795435 4919
G 3528270 3582
2
L 1000000000 1000000000
G 1000000000 1000000000
5
L 589 334552
G 3692 4
L 955 542440
L 82 23288
L 574 163016
15
L 16640 881920
G 676 4
L 105470 6750080
G 812 4
L 666 11295360
G 460 20
L 8777 297715840
G 293 1
L 83 2815360
G 2544 848
L 427 14483840
G 115 5
L 588 4986240
G 18 2
L 607 20589440
5
G 50179535 1267
L 24036257 697051453
G 493636927 63133
L 4334407 377093409
G 747704303 5249
24
L 159 51198
L 620 99820
L 434 9982
G 408 2
L 791 36386
L 820 132020
G 425845 161
G 88088 14
L 524 84364
L 396 63756
G 1426 46
L 258 41538
L 839 270158
L 432 69552
L 706 113666
L 544 87584
L 933 300426
L 753 242466
L 237 76314
L 190 30590
G 159 1
L 889 40894
G 2401 7
L 486 78246
10
L 719 612588
G 126 6
L 642 91164
L 377 321204
G 4828 142
L 957 271788
G 781 71
L 869 740388
L 897 254748
L 6660 472860


Sample output:
Case #1: 6
Case #2: -1
Case #3: 24
Case #4: -1
Case #5: 424179
Case #6: -1
Case #7: 1000000000
Case #8: -1
Case #9: 33920
Case #10: -1
Case #11: 322
Case #12: -1



Code: // Integers as a Service
// Solution by Jacob Plachta

#define DEBUG 0

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }
string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#if DEBUG
#define GETCHAR getchar
#else
#define GETCHAR getchar_unlocked
#endif

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=GETCHAR();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

#define LIM 2000

int N;
char O[LIM];
int V[LIM],R[LIM];
map<int,int> minE,maxE,Fv,Fr;
map<int,int>::iterator I;

map<int,int> Fact(int v)
{
	map<int,int> F;
	int p,e;
		for (p=2; p*p<=v; p++)
		{
			e=0;
				while (v%p==0)
					v/=p,e++;
				if (e)
					F[p]=e;
		}
		if (v>1)
			F[v]=1;
	return(F);
}

void SetMin(int p,int e)
{
	Max(minE[p],e);
}

void SetMax(int p,int e)
{
	if (maxE.count(p))
		Min(maxE[p],e);
	else
		maxE[p]=e;
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int i,p,e,ev,er;
	LL ans;
	bool hasAP;
	set<int> AP;
	set<int>::iterator J,K;
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// init
			printf("Case #%d: ",t);
			minE.clear(),maxE.clear();
			hasAP=0;
			// input
			Read(N);
				Fox(i,N)
					scanf("%c%d%d\n",&O[i],&V[i],&R[i]);
			// assemble prime exponent requirements based on original requirements
				Fox(i,N)
				{
					Fv=Fact(V[i]),Fr=Fact(R[i]);
						if (O[i]=='G')
						{
							if (V[i]%R[i])
								goto Imp;
							Foxen(I,Fv)
							{
								p=I->x,ev=I->y;
								er=Fr[p];
								SetMin(p,er);
									if (ev>er)
										SetMax(p,er);
							}
						}
						else
						{
							if (R[i]%V[i])
								goto Imp;
							Foxen(I,Fr)
							{
								p=I->x,er=I->y;
								ev=Fv[p];
								SetMax(p,er);
									if (ev<er)
										SetMin(p,er);
							}
							if (!hasAP)
							{
								hasAP=1,AP.clear();
									Foxen(I,Fr)
										AP.insert(I->x);
							}
							else
							for (J=AP.begin(); J!=AP.end();)
							{
								K=J,J++;
									if (!Fr.count(*K))
										AP.erase(K);
							}
						}
				}
			// construct min. valid value of X
			ans=1;
				Foxen(I,minE)
				{
					p=I->x,e=I->y;
						if ((e) && (hasAP) && (!AP.count(p)))
							goto Imp;
						if ((maxE.count(p)) && (maxE[p]<e))
							goto Imp;
						while (e--)
						{
							ans*=p;
								if (ans>INF)
									goto Imp;
						}
				}
			// output
			printf("%lld\n",ans);
			continue;
Imp:;
			printf("-1\n");
		}
	return(0);
}