// gcds.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <algorithm>
#include <assert.h>
using namespace std;
#define ASSERT(x) assert(x)
int primes[]={5,7,11,13,19,23,29,31,37,41,43};
int cand[9];
int buf[4][4];
long long minr=-1;
long long mx, my;
long long gcd(long long x, long long y)
{
    if(y==0)return x;
    do{
        long long r=x%y;
        x=y;y=r;
    }while(y!=0);
    return x;
}

long long extGCD(long long a, long long b, long long & ar, long long & br)
{
        long long x = 0, y = 1;
    long long old_a=a,old_b=b;
        ar = 1, br = 0;
        unsigned long long t, q;
        while (b != 0)
        {
                t = b; q = a / b; b = a % b; a = t;
                t = x; x = ar - q * x; ar = t;
                t = y; y = br - q * y; br = t;
        }
    if(ar<0)ar+=old_b;
    if(br<0)br+=old_a;
        return (a);
}
long long lcm(long long x, long long y)
{
    return x/gcd(x,y)*y;
}

long long chinese(long long c[4])
{
    long long s,t;
    long long d1=extGCD(c[0],c[1],s,t);
    ASSERT(d1==1);
    if(s!=0)s=c[1]-s;
    long long m1=c[0]*c[1];
    long long r1=c[0]*s;
    d1=extGCD(c[2],c[3],s,t);
    ASSERT(d1==1);
    long long a,b;
    a=((c[3]-3)*s)%c[3]; 
    b=((c[2]-2)*t)%c[2];
    long long m2=c[2]*c[3];
    long long r2=(a*c[2]+b*c[3])%m2;
    d1=extGCD(m1,m2,s,t);
    ASSERT((r2-r1)%d1==0);
    b=(r1*t)%m1;
    a=(r2*s)%m2;
    long long d2=gcd(d1,r1);
    m1/=d1;
    m2/=d2;
    d1/=d2;
    r1%=m1;r2%=m2;
    d1=extGCD(m1,m2,s,t);
    ASSERT(d1==1);
    a=(r1*t)%m1;
    b=(r2*s)%m2;
    long long r3=(a*m2+b*m1)%(m1*m2);
    return lcm(r3,d2);
}

void test_buf()
{
    long long c[4];
    int i;
    for(i=0;i<4;i++){
        long long l1=lcm(buf[i][0],buf[i][1]);
        long long l2=lcm(buf[i][2],buf[i][3]);
        c[i]=lcm(l1,l2);
    }
    long long x=chinese(c);
    for(i=0;i<4;i++){
        long long l1=lcm(buf[0][i],buf[1][i]);
        long long l2=lcm(buf[2][i],buf[3][i]);
        c[i]=lcm(l1,l2);
    }
    long long y=chinese(c);
    if(minr<0||minr>x+y){
        minr=x+y;
        mx=x;
        my=y;
        printf("Found x=%lld,y=%lld\n",mx,my);
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    int i,j,k,t;
    for(i=0;i<11;i++)for(j=i+1;j<11;j++){
        for(k=0,t=0;k<11;k++){
            if(k!=i&&k!=j){
                cand[t++]=primes[k];
            }
        }
        do{
            buf[0][0]=6;buf[0][1]=cand[0];buf[0][2]=2;buf[0][3]=3;
            buf[1][0]=cand[1];buf[1][1]=cand[2];buf[1][2]=cand[3];buf[1][3]=cand[4];
            buf[2][0]=2;buf[2][1]=cand[5];buf[2][2]=2;buf[2][3]=cand[6];
            buf[3][0]=3;buf[3][1]=cand[7];buf[3][2]=cand[8];buf[3][3]=3;
            test_buf();
            buf[0][0]=3;buf[0][1]=2;buf[0][2]=cand[0];buf[0][3]=6;
            buf[1][0]=cand[1];buf[1][1]=cand[2];buf[1][2]=cand[3];buf[1][3]=cand[4];
            buf[2][0]=cand[5];buf[2][1]=2;buf[2][2]=cand[6];buf[2][3]=2;
            buf[3][0]=3;buf[3][1]=cand[7];buf[3][2]=cand[8];buf[3][3]=3;
            test_buf();
            buf[0][0]=3;buf[0][1]=cand[0];buf[0][2]=cand[1];buf[0][3]=3;
            buf[1][0]=cand[2];buf[1][1]=2;buf[1][2]=cand[3];buf[1][3]=2;
            buf[2][0]=cand[4];buf[2][1]=cand[5];buf[2][2]=cand[6];buf[2][3]=cand[7];
            buf[3][0]=3;buf[3][1]=2;buf[3][2]=cand[8];buf[3][3]=6;
            test_buf();
            buf[0][0]=3;buf[0][1]=cand[0];buf[0][2]=cand[1];buf[0][3]=3;
            buf[1][0]=2;buf[1][1]=cand[2];buf[1][2]=2;buf[1][3]=cand[3];
            buf[2][0]=cand[5];buf[2][1]=cand[4];buf[2][2]=cand[6];buf[2][3]=cand[7];
            buf[3][0]=6;buf[3][1]=cand[8];buf[3][2]=2;buf[3][3]=3;
            test_buf();
        }while(next_permutation(cand,cand+9));
    }
        return 0;
}