import os
import random
import sys

MAX_DIM = 10**6

CASE = 1
DEST = os.path.join(os.getcwd(), '../data/secret')

def next_file(short_desc=None, long_desc=None):
    global CASE
    basename = os.path.join(DEST, '%02d' % CASE)
    CASE += 1
    if short_desc is not None:
        basename += '-' + short_desc
    if long_desc is not None:
        with open(basename+'.desc', 'w') as desc_out:
            desc_out.write(long_desc)
    return open(basename+'.in', 'w')

def save_case(n, m, a, short_desc=None, long_desc=None, shuffle_adj_list=True):
    sys.stderr.write('save case %d %d %d\n' % (n, m, a))
    f = next_file(short_desc, long_desc)
    f.write('%d %d %d\n' % (n, m, a))
    f.close()

def solve(n, m, a):
    def subsquare(n, m, a):
        return any(a % x == 0 and a / x <= max(n, m) for x in range(1, min(n,m)))

    if a % n == 0 or a % m == 0:
        return 1
    elif subsquare(n, m, a) or subsquare(n, m, n*m-a):
        return 2
    else:
        return 3

    
def random_case(target_answer=None):
    if target_answer is None:
        desc = 'random'
    elif target_answer == 1:
        desc = 'random_1cut'
    else:
        desc = 'random_%dcuts' % target_answer

    while True:
        n = m = 1
        while n == 1 and m == 1:
            n = random.randint(1, MAX_DIM)
            m = random.randint(1, MAX_DIM)
            if target_answer == 1:
                if random.randint(0, 1):
                    a = n*random.randint(1, m-1)
                else:
                    a = m*random.randint(1, n-1)
            else:
                a = random.randint(1, n*m-1)
        if target_answer is None or target_answer == solve(n, m, a):
            save_case(n, m, a, short_desc=desc)
            return


def is_prime(n):
    if n <= 2: return n == 2
    if n % 2 == 0: return False
    r = 3
    while r*r <= n:
        if n % r == 0: return False
        r += 2
    return r

def random_prime(lo, hi):
    n = 1
    while not is_prime(n):
        n = random.randint(lo, hi)
    return n
        

def main():
    random.seed(13)

    save_case(1, 2, 1, short_desc='minimal')
    save_case(2, 1, 1, short_desc='minimal')
    save_case(MAX_DIM, MAX_DIM, MAX_DIM*MAX_DIM-1, short_desc='maximal')
    save_case(MAX_DIM, MAX_DIM, MAX_DIM*MAX_DIM/2, short_desc='maximal')
    save_case(2, 2, 1, short_desc='small')
    save_case(2, 2, 2, short_desc='small')

    n = random_prime(MAX_DIM-100, MAX_DIM)
    m = random_prime(MAX_DIM-100, MAX_DIM)
    save_case(n, m, n, short_desc='oneslice')
    save_case(m, n, n, short_desc='oneslice')

    save_case(MAX_DIM, 1, random.randint(1, MAX_DIM-1), short_desc='narrow')
    save_case(1, MAX_DIM, random.randint(1, MAX_DIM-1), short_desc='narrow')
    save_case(MAX_DIM, 2, random.randint(1, 2*MAX_DIM-1), short_desc='narrow')
    save_case(2, MAX_DIM, random.randint(1, 2*MAX_DIM-1), short_desc='narrow')
    
    save_case(1<<15, 1<<15, 1<<25, short_desc='twopow')
    
    n = random.randint(MAX_DIM-10, MAX_DIM)
    m = random.randint(MAX_DIM-10, MAX_DIM)
    a = max(n, m) + 1
    while not is_prime(a): a += 1
    save_case(n, m, a, short_desc='prime_a')
    
    n = random.randint(MAX_DIM-10, MAX_DIM)
    m = random.randint(MAX_DIM-10, MAX_DIM)
    a = random_prime(n-100, n-1) * random_prime(m-100, m-1)
    save_case(n, m, a, short_desc='rsa_a')

    n = random.randint(MAX_DIM-10, MAX_DIM)
    m = random.randint(MAX_DIM-10, MAX_DIM)
    a = random_prime(n/2-10, n/2+10) * random_prime(m/2-10, m/2+10)
    save_case(n, m, a, short_desc='rsa_a')

    n = random.randint(MAX_DIM-10, MAX_DIM)
    m = random.randint(MAX_DIM-10, MAX_DIM)
    a = random_prime(1, n-1) * random_prime(1, m-1)
    save_case(n, m, a, short_desc='rsa_a')

    n = random.randint(1, MAX_DIM/4)
    m = random.randint(3*MAX_DIM/4, MAX_DIM)
    a = random_prime(n/2-20, n/2+20) * random_prime(m/2-20, m/2+20)
    save_case(n, m, a, short_desc='lopsided_rsa_a')

    n = random.randint(3*MAX_DIM/4, MAX_DIM)
    m = random.randint(1, MAX_DIM/4)
    a = random_prime(n/2-20, n/2+20) * random_prime(m/2-20, m/2+20)
    save_case(n, m, a, short_desc='lopsided_rsa_a')


    for _ in range(10):
        random_case()
    for ans in [1,2,3]:
        for _ in range(10):
            random_case(target_answer=ans)
            
    
if __name__=='__main__':
    main()