#!/usr/bin/env python

from collections import Counter

def decompose_sum(s):
    return [(a,s-a) for a in range(1,int(s/2+1))]

def isprime(n):
    '''check if integer n is a prime'''

    # make sure n is a positive integer
    n = abs(int(n))

    # 0 and 1 are not primes
    if n < 2:
        return False

    # 2 is the only even prime number
    if n == 2:
        return True

    # all other even numbers are not primes
    if not n & 1:
        return False

    # range starts with 3 and only needs to go up
    # the square root of n for all odd numbers
    for x in range(3, int(n**0.5) + 1, 2):
        if n % x == 0:
            return False

    return True

################################################################################
################################################################################
## Template file for problem 1. You have to fill in the function findNumbers  ##
## defined below. The function takes in an input number and return the list   ##
## of numbers that satisfy the problem statement. Please ensure you return a  ##
## list as the submission will be auto evaluated. We have provided a little   ##
## helper to ensure that the return value is correct.                         ##
##                                                                            ##
## You can run this template file to see the output of your function.         ##
## First replace the TEST_NUMBER with correct number.                         ##
## Then simply run: `python problem1_template.py`                             ##
## You should see the output printed once your program runs.                  ##
##                                                                            ##
## DO NOT CHANGE THE NAME OF THE FUNCTION BELOW. ONLY FILL IN THE LOGIC.      ##
## DONT FORGET TO RETURN THE VALUES AS A LIST                                 ##
## IF YOU MAKE ANY IMPORTS PUT THEM IN THE BODY OF THE FUNCTION               ##
##                                                                            ##
## You are free to write additional helper functions but ensure they are all  ##
## in this file else your submission wont work.                               ##
##                                                                            ##
## Good Luck!                                                                 ##
################################################################################
################################################################################

TEST_NUMBER = 100

def findNumbers(inputNumber):
    ##################################
    ##          FILL ME IN          ##
    ##################################
        # Generate all possible pairs
    all_pairs = set((a,b) for a in range(1,inputNumber+1) for b in range(a,inputNumber+1) if a+b <= 2*inputNumber)
    # Fact 1 --> Select pairs for which all sum decompositions have non-unique product
    product_counts = Counter(c*d for c,d in all_pairs)
    unique_products = set((a,b) for a,b in all_pairs if product_counts[a*b]==1)
    s_pairs = [(a,b) for a,b in all_pairs if
        all((x,y) not in unique_products for (x,y) in decompose_sum(a+b)) ]

    # Fact 2 --> Select pairs for which the product is unique
    product_counts = Counter(c*d for c,d in s_pairs)
    p_pairs = [(a,b) for a,b in s_pairs if product_counts[a*b]==1]

    # Fact 3 --> Select pairs for which the sum is unique
    sum_counts = Counter(c+d for c,d in p_pairs)
    final_pairs = [(a,b) for a,b in p_pairs if sum_counts[a+b]==1 ]

    if len(final_pairs) == 1:
        a,b = final_pairs[0]
        return [a,b]
    if(len(final_pairs)==0):
        return []

    # for pair in final_pairs:
    #     print(pair)

    dict_map = {}
    for pair in final_pairs:
        a,b=pair
        if b-a in dict_map:
            dict_map[b-a].append([a,b])
        else:
            dict_map[b-a] = [[a,b]]


    dup_list = []

    for key in dict_map:
        if len(dict_map[key]) > 1:
            dup_list.append(dict_map[key])

    for item in dup_list:
        print(item,end='\n')

    pos = -1
    ele = 0
    flag = False
    for i,lists in enumerate(dup_list):
        dicter = {}

        for j,item in enumerate(lists):
            a,b = item
            if (a in dicter and dicter[a] == 1) or (b in dicter and dicter[b] == 1):
                pos = i
                if a in dicter:
                    ele = a
                else:
                    ele = b
                flag = True
                break
            dicter[a]=dicter.get(a,0)+1
            dicter[b]=dicter.get(b,0)+1

    ans = []

    print(ele)

    print(pos)
    if pos==-1:
        return []
    elif pos !=-1 :
        for i,item in enumerate(dup_list[pos]):
            a,b = item
            if a is ele or b is ele:
                continue
            else:
                ans = [a,b]


    for item in dup_list:
        print(item)

    return ans

def ensureNumbers(returnList):
    for num in returnList:
        if type(num) is int:
            continue
        else:
            print(num, ' is not an integer.')
            raise TypeError('The return value is not a list of integers')
    return returnList


def ensureListOfNumbers(returnList):
    if type(returnList) is list:
        return ensureNumbers(returnList)
    else:
        print('Return value is not a list. Please ensure you return a list.')
        raise TypeError('The return value is not a list')



if __name__ == "__main__":
    print(ensureListOfNumbers(findNumbers(TEST_NUMBER)))