from itertools import combinations
import time
import threading
from collections import defaultdict
import math
from multiprocessing import Pool
 
# 配置参数（优化阈值）
TARGET = 21940 # 目标值
BASE_VALUES = [36.5, 41.5, 59, 68.5, 74, 91.5]  # 基础系数列表
FLUCTUATION = 1.0  # 系数波动范围
MAX_SOLUTIONS = 3  # 每个组合的最大解数量
SOLVER_TIMEOUT = 180  # 求解超时时间(秒)
THREE_VAR_THRESHOLD = 259000  # 使用三个变量的阈值
PRODUCT_RANGE_THRESHOLD = 129000  # 乘积范围限制阈值
HIGH_TARGET_THRESHOLD = 259000  # 更高目标值阈值
SHOW_PROGRESS = True  # 是否显示进度
MAX_SOLUTIONS_PER_COMB = 100  # 每个组合的最大解数量，用于提前终止
USE_MULTIPROCESSING = True  # 是否使用多进程加速
 
def is_valid_product(p):
    """确保单个乘积不超过129000"""
    return p <= 129000  # 严格限制所有乘积不超过129000
 
def find_single_variable_solutions(values):
    """查找单个数的解（a*x = TARGET）"""
    solutions = []
    for a in values:
        quotient = TARGET / a
        if quotient != int(quotient):
            continue
        x = int(quotient)
        if 1 <= x <= 10000 and is_valid_product(a * x):
            solutions.append((a, x))
            if len(solutions) >= MAX_SOLUTIONS:
                break
    return solutions
 
def find_two_variable_solutions(values):
    """优化的双变量求解算法，确保每个乘积不超过129000"""
    solutions = defaultdict(list)
    for i, a in enumerate(values):
        for b in values[i:]:
            seen_xy = set()
            # 调整x的最大值，确保a*x不超过129000
            max_x = min(math.floor((TARGET - b) / a), math.floor(129000 / a))
            min_x = max(1, math.ceil((TARGET - b * 10000) / a))
 
            if max_x < min_x:
                continue
 
            x_count = max_x - min_x + 1
            x_step = max(1, x_count // 1000)
 
            for x in range(min_x, max_x + 1, x_step):
                ax = a * x
                if ax > 129000:  # 额外检查确保不超过129000
                    continue
 
                remainder = TARGET - ax
 
                if remainder < b:
                    break
 
                if remainder > b * 10000:
                    continue
 
                if remainder % b == 0:
                    y = remainder // b
                    by = b * y
                    if 1 <= y <= 10000 and by <= 129000:  # 确保b*y也不超过129000
                        xy_pair = (x, y) if a <= b else (y, x)
                        if xy_pair not in seen_xy:
                            seen_xy.add(xy_pair)
                            solutions[(a, b)].append((a, x, b, y))
                            if len(solutions[(a, b)]) >= MAX_SOLUTIONS_PER_COMB:
                                break
    return solutions
 
def process_three_var_combination(args):
    """处理三变量组合的辅助函数，用于并行计算"""
    a, b, c, value_ranges, target = args
    solutions = []
    seen_xyz = set()
 
    min_x, max_x = value_ranges[a]
    x_count = max_x - min_x + 1
    x_step = max(1, x_count // 1000)
 
    for x in range(min_x, max_x + 1, x_step):
        ax = a * x
        if not is_valid_product(ax):
            continue
 
        remainder1 = target - ax
        if remainder1 < 0:
            break
 
        max_y = math.floor((remainder1 - c) / b)
        min_y = max(1, math.ceil((remainder1 - c * 10000) / b))
 
        if max_y < min_y:
            continue
 
        y_count = max_y - min_y + 1
        y_step = max(1, y_count // 100)
 
        for y in range(min_y, max_y + 1, y_step):
            by = b * y
            if not is_valid_product(by):
                continue
 
            remainder2 = remainder1 - by
            if remainder2 < 0:
                break
 
            if remainder2 > c * 10000:
                continue
 
            if remainder2 % c == 0:
                z = remainder2 // c
                if 1 <= z <= 10000 and is_valid_product(c * z):
                    xyz_tuple = tuple(sorted([x, y, z]))
                    if xyz_tuple not in seen_xyz:
                        seen_xyz.add(xyz_tuple)
                        solutions.append((a, x, b, y, c, z))
                        if len(solutions) >= MAX_SOLUTIONS_PER_COMB:
                            return solutions
 
    return solutions
 
def find_three_variable_solutions(values):
    """优化的三变量求解算法，确保每个乘积不超过129000"""
    solutions = defaultdict(list)
    sorted_values = sorted(values)
 
    # 预计算每个系数的有效范围，确保每个乘积不超过129000
    value_ranges = {}
    for a in sorted_values:
        min_x = max(1, math.ceil(1 / a))  # 最小为1
        max_x = min(10000, math.floor(129000 / a))  # 确保a*x <= 129000
        value_ranges[a] = (min_x, max_x)
 
    combinations_list = []
    for i, a in enumerate(sorted_values):
        for j in range(i + 1, len(sorted_values)):
            b = sorted_values[j]
            for k in range(j + 1, len(sorted_values)):
                c = sorted_values[k]
                combinations_list.append((a, b, c, value_ranges, TARGET))
 
    if USE_MULTIPROCESSING:
        with Pool() as pool:
            results = pool.map(process_three_var_combination, combinations_list)
 
        for i, (a, b, c, _, _) in enumerate(combinations_list):
            if results[i]:
                solutions[(a, b, c)] = results[i]
    else:
        total_combinations = len(combinations_list)
        for i, (a, b, c, _, _) in enumerate(combinations_list):
            res = process_three_var_combination((a, b, c, value_ranges, TARGET))
            if res:
                solutions[(a, b, c)] = res
 
            if SHOW_PROGRESS and i % 10 == 0:
                print(f"\r三变量组合进度: {i}/{total_combinations} 组", end='')
 
    if SHOW_PROGRESS and not USE_MULTIPROCESSING:
        print(f"\r三变量组合进度: {total_combinations}/{total_combinations} 组 - 完成")
 
    return solutions
 
def find_balanced_solutions(solutions, var_count, num=2):
    """从所有解中筛选出最平衡的解"""
    if var_count == 1 or not solutions:
        return solutions
 
    balanced = []
    for sol in solutions:
        vars = sol[1::2]  # 获取解中的变量值
        diff = max(vars) - min(vars)  # 计算变量之间的最大差值
        balanced.append((diff, sol))
 
    # 按差值排序，返回差值最小的解
    return [s for _, s in sorted(balanced, key=lambda x: x[0])[:num]]
 
def find_original_solutions(solutions, balanced_solutions, num=3):
    """从剩余解中获取原始顺序的解"""
    if not solutions:
        return []
 
    remaining = [s for s in solutions if s not in balanced_solutions]
    return remaining[:num]
 
def display_solutions(solutions_dict, var_count):
    """优化的解显示函数"""
    if not solutions_dict:
        return
 
    print(f"\n找到 {len(solutions_dict)} 组{var_count}变量解：")
 
    for i, (coeffs, pair_solutions) in enumerate(sorted(solutions_dict.items()), 1):
        balanced = find_balanced_solutions(pair_solutions, var_count)
        original = find_original_solutions(pair_solutions, balanced)
        all_display = balanced + original
 
        if var_count == 1:
            a = coeffs
            print(f"\n{i}. 组合: a={a} ({len(pair_solutions)} 个有效解)")
        elif var_count == 2:
            a, b = coeffs
            print(f"\n{i}. 组合: a={a}, b={b} ({len(pair_solutions)} 个有效解)")
        else:
            a, b, c = coeffs
            print(f"\n{i}. 组合: a={a}, b={b}, c={c} ({len(pair_solutions)} 个有效解)")
 
        for j, sol in enumerate(all_display, 1):
            tag = "[平衡解]" if j <= len(balanced) else "[原始解]"
 
            if var_count == 1:
                a, x = sol
                print(f"  {j}. x={x}, a*x={a*x:.1f}, 总和={a*x:.1f} {tag}")
            elif var_count == 2:
                a, x, b, y = sol
                print(f"  {j}. x={x}, y={y}, a*x={a*x:.1f}, b*y={b*y:.1f}, 总和={a*x + b*y:.1f} {tag}")
            else:
                a, x, b, y, c, z = sol
                print(f"  {j}. x={x}, y={y}, z={z}, "
                      f"a*x={a*x:.1f}, b*y={b*y:.1f}, c*z={c*z:.1f}, "
                      f"总和={a*x + b*y + c*z:.1f} {tag}")
 
def run_with_timeout(func, args=(), kwargs=None, timeout=SOLVER_TIMEOUT):
    """运行函数并设置超时限制"""
    if kwargs is None:
        kwargs = {}
 
    result = []
    error = []
 
    def wrapper():
        try:
            result.append(func(*args, **kwargs))
        except Exception as e:
            error.append(e)
 
    thread = threading.Thread(target=wrapper)
    thread.daemon = True
    thread.start()
    thread.join(timeout)
 
    if thread.is_alive():
        print(f"警告: {func.__name__} 超时（{timeout}秒），跳过此方法")
        return None
 
    if error:
        raise error[0]
 
    return result[0]
 
def main():
    print(f"目标值: {TARGET}")
 
    # 生成波动后的系数
    FLUCTUATED_VALUES = [round(v - FLUCTUATION, 1) for v in BASE_VALUES]
 
    # 尝试基础系数
    print(f"\n==== 尝试基础系数 ====")
 
    # 目标值255966 > 259000不成立，会按顺序尝试单、双、三变量解
    base_solutions = {
        'single': run_with_timeout(find_single_variable_solutions, args=(BASE_VALUES,)),
        'two': run_with_timeout(find_two_variable_solutions, args=(BASE_VALUES,)),
        'three': []
    }
 
    has_solution = False
 
    # 显示单变量解
    if base_solutions['single']:
        has_solution = True
        display_solutions({a: [sol] for a, sol in zip(BASE_VALUES, base_solutions['single']) if sol}, 1)
 
    # 显示双变量解
    if base_solutions['two'] and len(base_solutions['two']) > 0:
        has_solution = True
        display_solutions(base_solutions['two'], 2)
 
    # 单变量和双变量都无解时，尝试三变量解
    if not has_solution:
        print(f"\n==== 单变量和双变量无解，尝试三变量解 ====")
        base_solutions['three'] = run_with_timeout(find_three_variable_solutions, args=(BASE_VALUES,))
 
        if base_solutions['three'] and len(base_solutions['three']) > 0:
            has_solution = True
            display_solutions(base_solutions['three'], 3)
 
    if has_solution:
        print(f"\n使用基础系数列表，共找到有效解")
        return
 
    # 如果基础系数没有找到解，尝试波动系数
    print(f"\n==== 尝试波动系数 ====")
 
    fluctuated_solutions = {
        'single': run_with_timeout(find_single_variable_solutions, args=(FLUCTUATED_VALUES,)),
        'two': run_with_timeout(find_two_variable_solutions, args=(FLUCTUATED_VALUES,)),
        'three': []
    }
 
    has_solution = False
 
    # 显示单变量解
    if fluctuated_solutions['single']:
        has_solution = True
        display_solutions({a: [sol] for a, sol in zip(FLUCTUATED_VALUES, fluctuated_solutions['single']) if sol}, 1)
 
    # 显示双变量解
    if fluctuated_solutions['two'] and len(fluctuated_solutions['two']) > 0:
        has_solution = True
        display_solutions(fluctuated_solutions['two'], 2)
 
    # 单变量和双变量都无解时，尝试三变量解
    if not has_solution:
        print(f"\n==== 单变量和双变量无解，尝试三变量解 ====")
        fluctuated_solutions['three'] = run_with_timeout(find_three_variable_solutions, args=(FLUCTUATED_VALUES,))
 
        if fluctuated_solutions['three'] and len(fluctuated_solutions['three']) > 0:
            has_solution = True
            display_solutions(fluctuated_solutions['three'], 3)
 
    if has_solution:
        print(f"\n使用波动系数列表，共找到有效解")
        return
 
    # 如果所有系数集都没有找到解
    print("\n没有找到符合条件的解，即使使用波动后的系数列表。")
 
if __name__ == "__main__":
    start_time = time.time()
    main()
    print(f"\n总耗时: {time.time() - start_time:.2f}秒")    

ZnJvbSBpdGVydG9vbHMgaW1wb3J0IGNvbWJpbmF0aW9ucwppbXBvcnQgdGltZQppbXBvcnQgdGhyZWFkaW5nCmZyb20gY29sbGVjdGlvbnMgaW1wb3J0IGRlZmF1bHRkaWN0CmltcG9ydCBtYXRoCmZyb20gbXVsdGlwcm9jZXNzaW5nIGltcG9ydCBQb29sCgojIOmFjee9ruWPguaVsO+8iOS8mOWMlumYiOWAvO+8iQpUQVJHRVQgPSAyMTk0MCAjIOebruagh+WAvApCQVNFX1ZBTFVFUyA9IFszNi41LCA0MS41LCA1OSwgNjguNSwgNzQsIDkxLjVdICAjIOWfuuehgOezu+aVsOWIl+ihqApGTFVDVFVBVElPTiA9IDEuMCAgIyDns7vmlbDms6LliqjojIPlm7QKTUFYX1NPTFVUSU9OUyA9IDMgICMg5q+P5Liq57uE5ZCI55qE5pyA5aSn6Kej5pWw6YePClNPTFZFUl9USU1FT1VUID0gMTgwICAjIOaxguino+i2heaXtuaXtumXtCjnp5IpClRIUkVFX1ZBUl9USFJFU0hPTEQgPSAyNTkwMDAgICMg5L2/55So5LiJ5Liq5Y+Y6YeP55qE6ZiI5YC8ClBST0RVQ1RfUkFOR0VfVEhSRVNIT0xEID0gMTI5MDAwICAjIOS5mOenr+iMg+WbtOmZkOWItumYiOWAvApISUdIX1RBUkdFVF9USFJFU0hPTEQgPSAyNTkwMDAgICMg5pu06auY55uu5qCH5YC86ZiI5YC8ClNIT1dfUFJPR1JFU1MgPSBUcnVlICAjIOaYr+WQpuaYvuekuui/m+W6pgpNQVhfU09MVVRJT05TX1BFUl9DT01CID0gMTAwICAjIOavj+S4que7hOWQiOeahOacgOWkp+ino+aVsOmHj++8jOeUqOS6juaPkOWJjee7iOatogpVU0VfTVVMVElQUk9DRVNTSU5HID0gVHJ1ZSAgIyDmmK/lkKbkvb/nlKjlpJrov5vnqIvliqDpgJ8KCmRlZiBpc192YWxpZF9wcm9kdWN0KHApOgogICAgIiIi56Gu5L+d5Y2V5Liq5LmY56ev5LiN6LaF6L+HMTI5MDAwIiIiCiAgICByZXR1cm4gcCA8PSAxMjkwMDAgICMg5Lil5qC86ZmQ5Yi25omA5pyJ5LmY56ev5LiN6LaF6L+HMTI5MDAwCgpkZWYgZmluZF9zaW5nbGVfdmFyaWFibGVfc29sdXRpb25zKHZhbHVlcyk6CiAgICAiIiLmn6Xmib7ljZXkuKrmlbDnmoTop6PvvIhhKnggPSBUQVJHRVTvvIkiIiIKICAgIHNvbHV0aW9ucyA9IFtdCiAgICBmb3IgYSBpbiB2YWx1ZXM6CiAgICAgICAgcXVvdGllbnQgPSBUQVJHRVQgLyBhCiAgICAgICAgaWYgcXVvdGllbnQgIT0gaW50KHF1b3RpZW50KToKICAgICAgICAgICAgY29udGludWUKICAgICAgICB4ID0gaW50KHF1b3RpZW50KQogICAgICAgIGlmIDEgPD0geCA8PSAxMDAwMCBhbmQgaXNfdmFsaWRfcHJvZHVjdChhICogeCk6CiAgICAgICAgICAgIHNvbHV0aW9ucy5hcHBlbmQoKGEsIHgpKQogICAgICAgICAgICBpZiBsZW4oc29sdXRpb25zKSA+PSBNQVhfU09MVVRJT05TOgogICAgICAgICAgICAgICAgYnJlYWsKICAgIHJldHVybiBzb2x1dGlvbnMKCmRlZiBmaW5kX3R3b192YXJpYWJsZV9zb2x1dGlvbnModmFsdWVzKToKICAgICIiIuS8mOWMlueahOWPjOWPmOmHj+axguino+eul+azle+8jOehruS/neavj+S4quS5mOenr+S4jei2hei/hzEyOTAwMCIiIgogICAgc29sdXRpb25zID0gZGVmYXVsdGRpY3QobGlzdCkKICAgIGZvciBpLCBhIGluIGVudW1lcmF0ZSh2YWx1ZXMpOgogICAgICAgIGZvciBiIGluIHZhbHVlc1tpOl06CiAgICAgICAgICAgIHNlZW5feHkgPSBzZXQoKQogICAgICAgICAgICAjIOiwg+aVtHjnmoTmnIDlpKflgLzvvIznoa7kv51hKnjkuI3otoXov4cxMjkwMDAKICAgICAgICAgICAgbWF4X3ggPSBtaW4obWF0aC5mbG9vcigoVEFSR0VUIC0gYikgLyBhKSwgbWF0aC5mbG9vcigxMjkwMDAgLyBhKSkKICAgICAgICAgICAgbWluX3ggPSBtYXgoMSwgbWF0aC5jZWlsKChUQVJHRVQgLSBiICogMTAwMDApIC8gYSkpCiAgICAgICAgICAgIAogICAgICAgICAgICBpZiBtYXhfeCA8IG1pbl94OgogICAgICAgICAgICAgICAgY29udGludWUKICAgICAgICAgICAgICAgIAogICAgICAgICAgICB4X2NvdW50ID0gbWF4X3ggLSBtaW5feCArIDEKICAgICAgICAgICAgeF9zdGVwID0gbWF4KDEsIHhfY291bnQgLy8gMTAwMCkKICAgICAgICAgICAgCiAgICAgICAgICAgIGZvciB4IGluIHJhbmdlKG1pbl94LCBtYXhfeCArIDEsIHhfc3RlcCk6CiAgICAgICAgICAgICAgICBheCA9IGEgKiB4CiAgICAgICAgICAgICAgICBpZiBheCA+IDEyOTAwMDogICMg6aKd5aSW5qOA5p+l56Gu5L+d5LiN6LaF6L+HMTI5MDAwCiAgICAgICAgICAgICAgICAgICAgY29udGludWUKICAgICAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgIHJlbWFpbmRlciA9IFRBUkdFVCAtIGF4CiAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgIGlmIHJlbWFpbmRlciA8IGI6CiAgICAgICAgICAgICAgICAgICAgYnJlYWsKICAgICAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgIGlmIHJlbWFpbmRlciA+IGIgKiAxMDAwMDoKICAgICAgICAgICAgICAgICAgICBjb250aW51ZQogICAgICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgaWYgcmVtYWluZGVyICUgYiA9PSAwOgogICAgICAgICAgICAgICAgICAgIHkgPSByZW1haW5kZXIgLy8gYgogICAgICAgICAgICAgICAgICAgIGJ5ID0gYiAqIHkKICAgICAgICAgICAgICAgICAgICBpZiAxIDw9IHkgPD0gMTAwMDAgYW5kIGJ5IDw9IDEyOTAwMDogICMg56Gu5L+dYip55Lmf5LiN6LaF6L+HMTI5MDAwCiAgICAgICAgICAgICAgICAgICAgICAgIHh5X3BhaXIgPSAoeCwgeSkgaWYgYSA8PSBiIGVsc2UgKHksIHgpCiAgICAgICAgICAgICAgICAgICAgICAgIGlmIHh5X3BhaXIgbm90IGluIHNlZW5feHk6CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBzZWVuX3h5LmFkZCh4eV9wYWlyKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgc29sdXRpb25zWyhhLCBiKV0uYXBwZW5kKChhLCB4LCBiLCB5KSkKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmIGxlbihzb2x1dGlvbnNbKGEsIGIpXSkgPj0gTUFYX1NPTFVUSU9OU19QRVJfQ09NQjoKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBicmVhawogICAgcmV0dXJuIHNvbHV0aW9ucwoKZGVmIHByb2Nlc3NfdGhyZWVfdmFyX2NvbWJpbmF0aW9uKGFyZ3MpOgogICAgIiIi5aSE55CG5LiJ5Y+Y6YeP57uE5ZCI55qE6L6F5Yqp5Ye95pWw77yM55So5LqO5bm26KGM6K6h566XIiIiCiAgICBhLCBiLCBjLCB2YWx1ZV9yYW5nZXMsIHRhcmdldCA9IGFyZ3MKICAgIHNvbHV0aW9ucyA9IFtdCiAgICBzZWVuX3h5eiA9IHNldCgpCiAgICAKICAgIG1pbl94LCBtYXhfeCA9IHZhbHVlX3Jhbmdlc1thXQogICAgeF9jb3VudCA9IG1heF94IC0gbWluX3ggKyAxCiAgICB4X3N0ZXAgPSBtYXgoMSwgeF9jb3VudCAvLyAxMDAwKQogICAgCiAgICBmb3IgeCBpbiByYW5nZShtaW5feCwgbWF4X3ggKyAxLCB4X3N0ZXApOgogICAgICAgIGF4ID0gYSAqIHgKICAgICAgICBpZiBub3QgaXNfdmFsaWRfcHJvZHVjdChheCk6CiAgICAgICAgICAgIGNvbnRpbnVlCiAgICAgICAgICAgIAogICAgICAgIHJlbWFpbmRlcjEgPSB0YXJnZXQgLSBheAogICAgICAgIGlmIHJlbWFpbmRlcjEgPCAwOgogICAgICAgICAgICBicmVhawogICAgICAgICAgICAKICAgICAgICBtYXhfeSA9IG1hdGguZmxvb3IoKHJlbWFpbmRlcjEgLSBjKSAvIGIpCiAgICAgICAgbWluX3kgPSBtYXgoMSwgbWF0aC5jZWlsKChyZW1haW5kZXIxIC0gYyAqIDEwMDAwKSAvIGIpKQogICAgICAgIAogICAgICAgIGlmIG1heF95IDwgbWluX3k6CiAgICAgICAgICAgIGNvbnRpbnVlCiAgICAgICAgICAgIAogICAgICAgIHlfY291bnQgPSBtYXhfeSAtIG1pbl95ICsgMQogICAgICAgIHlfc3RlcCA9IG1heCgxLCB5X2NvdW50IC8vIDEwMCkKICAgICAgICAKICAgICAgICBmb3IgeSBpbiByYW5nZShtaW5feSwgbWF4X3kgKyAxLCB5X3N0ZXApOgogICAgICAgICAgICBieSA9IGIgKiB5CiAgICAgICAgICAgIGlmIG5vdCBpc192YWxpZF9wcm9kdWN0KGJ5KToKICAgICAgICAgICAgICAgIGNvbnRpbnVlCiAgICAgICAgICAgICAgICAKICAgICAgICAgICAgcmVtYWluZGVyMiA9IHJlbWFpbmRlcjEgLSBieQogICAgICAgICAgICBpZiByZW1haW5kZXIyIDwgMDoKICAgICAgICAgICAgICAgIGJyZWFrCiAgICAgICAgICAgICAgICAKICAgICAgICAgICAgaWYgcmVtYWluZGVyMiA+IGMgKiAxMDAwMDoKICAgICAgICAgICAgICAgIGNvbnRpbnVlCiAgICAgICAgICAgICAgICAKICAgICAgICAgICAgaWYgcmVtYWluZGVyMiAlIGMgPT0gMDoKICAgICAgICAgICAgICAgIHogPSByZW1haW5kZXIyIC8vIGMKICAgICAgICAgICAgICAgIGlmIDEgPD0geiA8PSAxMDAwMCBhbmQgaXNfdmFsaWRfcHJvZHVjdChjICogeik6CiAgICAgICAgICAgICAgICAgICAgeHl6X3R1cGxlID0gdHVwbGUoc29ydGVkKFt4LCB5LCB6XSkpCiAgICAgICAgICAgICAgICAgICAgaWYgeHl6X3R1cGxlIG5vdCBpbiBzZWVuX3h5ejoKICAgICAgICAgICAgICAgICAgICAgICAgc2Vlbl94eXouYWRkKHh5el90dXBsZSkKICAgICAgICAgICAgICAgICAgICAgICAgc29sdXRpb25zLmFwcGVuZCgoYSwgeCwgYiwgeSwgYywgeikpCiAgICAgICAgICAgICAgICAgICAgICAgIGlmIGxlbihzb2x1dGlvbnMpID49IE1BWF9TT0xVVElPTlNfUEVSX0NPTUI6CiAgICAgICAgICAgICAgICAgICAgICAgICAgICByZXR1cm4gc29sdXRpb25zCiAgICAKICAgIHJldHVybiBzb2x1dGlvbnMKCmRlZiBmaW5kX3RocmVlX3ZhcmlhYmxlX3NvbHV0aW9ucyh2YWx1ZXMpOgogICAgIiIi5LyY5YyW55qE5LiJ5Y+Y6YeP5rGC6Kej566X5rOV77yM56Gu5L+d5q+P5Liq5LmY56ev5LiN6LaF6L+HMTI5MDAwIiIiCiAgICBzb2x1dGlvbnMgPSBkZWZhdWx0ZGljdChsaXN0KQogICAgc29ydGVkX3ZhbHVlcyA9IHNvcnRlZCh2YWx1ZXMpCiAgICAKICAgICMg6aKE6K6h566X5q+P5Liq57O75pWw55qE5pyJ5pWI6IyD5Zu077yM56Gu5L+d5q+P5Liq5LmY56ev5LiN6LaF6L+HMTI5MDAwCiAgICB2YWx1ZV9yYW5nZXMgPSB7fQogICAgZm9yIGEgaW4gc29ydGVkX3ZhbHVlczoKICAgICAgICBtaW5feCA9IG1heCgxLCBtYXRoLmNlaWwoMSAvIGEpKSAgIyDmnIDlsI/kuLoxCiAgICAgICAgbWF4X3ggPSBtaW4oMTAwMDAsIG1hdGguZmxvb3IoMTI5MDAwIC8gYSkpICAjIOehruS/nWEqeCA8PSAxMjkwMDAKICAgICAgICB2YWx1ZV9yYW5nZXNbYV0gPSAobWluX3gsIG1heF94KQogICAgCiAgICBjb21iaW5hdGlvbnNfbGlzdCA9IFtdCiAgICBmb3IgaSwgYSBpbiBlbnVtZXJhdGUoc29ydGVkX3ZhbHVlcyk6CiAgICAgICAgZm9yIGogaW4gcmFuZ2UoaSArIDEsIGxlbihzb3J0ZWRfdmFsdWVzKSk6CiAgICAgICAgICAgIGIgPSBzb3J0ZWRfdmFsdWVzW2pdCiAgICAgICAgICAgIGZvciBrIGluIHJhbmdlKGogKyAxLCBsZW4oc29ydGVkX3ZhbHVlcykpOgogICAgICAgICAgICAgICAgYyA9IHNvcnRlZF92YWx1ZXNba10KICAgICAgICAgICAgICAgIGNvbWJpbmF0aW9uc19saXN0LmFwcGVuZCgoYSwgYiwgYywgdmFsdWVfcmFuZ2VzLCBUQVJHRVQpKQogICAgCiAgICBpZiBVU0VfTVVMVElQUk9DRVNTSU5HOgogICAgICAgIHdpdGggUG9vbCgpIGFzIHBvb2w6CiAgICAgICAgICAgIHJlc3VsdHMgPSBwb29sLm1hcChwcm9jZXNzX3RocmVlX3Zhcl9jb21iaW5hdGlvbiwgY29tYmluYXRpb25zX2xpc3QpCiAgICAgICAgCiAgICAgICAgZm9yIGksIChhLCBiLCBjLCBfLCBfKSBpbiBlbnVtZXJhdGUoY29tYmluYXRpb25zX2xpc3QpOgogICAgICAgICAgICBpZiByZXN1bHRzW2ldOgogICAgICAgICAgICAgICAgc29sdXRpb25zWyhhLCBiLCBjKV0gPSByZXN1bHRzW2ldCiAgICBlbHNlOgogICAgICAgIHRvdGFsX2NvbWJpbmF0aW9ucyA9IGxlbihjb21iaW5hdGlvbnNfbGlzdCkKICAgICAgICBmb3IgaSwgKGEsIGIsIGMsIF8sIF8pIGluIGVudW1lcmF0ZShjb21iaW5hdGlvbnNfbGlzdCk6CiAgICAgICAgICAgIHJlcyA9IHByb2Nlc3NfdGhyZWVfdmFyX2NvbWJpbmF0aW9uKChhLCBiLCBjLCB2YWx1ZV9yYW5nZXMsIFRBUkdFVCkpCiAgICAgICAgICAgIGlmIHJlczoKICAgICAgICAgICAgICAgIHNvbHV0aW9uc1soYSwgYiwgYyldID0gcmVzCiAgICAgICAgICAgIAogICAgICAgICAgICBpZiBTSE9XX1BST0dSRVNTIGFuZCBpICUgMTAgPT0gMDoKICAgICAgICAgICAgICAgIHByaW50KGYiXHLkuInlj5jph4/nu4TlkIjov5vluqY6IHtpfS97dG90YWxfY29tYmluYXRpb25zfSDnu4QiLCBlbmQ9JycpCiAgICAKICAgIGlmIFNIT1dfUFJPR1JFU1MgYW5kIG5vdCBVU0VfTVVMVElQUk9DRVNTSU5HOgogICAgICAgIHByaW50KGYiXHLkuInlj5jph4/nu4TlkIjov5vluqY6IHt0b3RhbF9jb21iaW5hdGlvbnN9L3t0b3RhbF9jb21iaW5hdGlvbnN9IOe7hCAtIOWujOaIkCIpCiAgICAKICAgIHJldHVybiBzb2x1dGlvbnMKCmRlZiBmaW5kX2JhbGFuY2VkX3NvbHV0aW9ucyhzb2x1dGlvbnMsIHZhcl9jb3VudCwgbnVtPTIpOgogICAgIiIi5LuO5omA5pyJ6Kej5Lit562b6YCJ5Ye65pyA5bmz6KGh55qE6KejIiIiCiAgICBpZiB2YXJfY291bnQgPT0gMSBvciBub3Qgc29sdXRpb25zOgogICAgICAgIHJldHVybiBzb2x1dGlvbnMKICAgIAogICAgYmFsYW5jZWQgPSBbXQogICAgZm9yIHNvbCBpbiBzb2x1dGlvbnM6CiAgICAgICAgdmFycyA9IHNvbFsxOjoyXSAgIyDojrflj5bop6PkuK3nmoTlj5jph4/lgLwKICAgICAgICBkaWZmID0gbWF4KHZhcnMpIC0gbWluKHZhcnMpICAjIOiuoeeul+WPmOmHj+S5i+mXtOeahOacgOWkp+W3ruWAvAogICAgICAgIGJhbGFuY2VkLmFwcGVuZCgoZGlmZiwgc29sKSkKICAgIAogICAgIyDmjInlt67lgLzmjpLluo/vvIzov5Tlm57lt67lgLzmnIDlsI/nmoTop6MKICAgIHJldHVybiBbcyBmb3IgXywgcyBpbiBzb3J0ZWQoYmFsYW5jZWQsIGtleT1sYW1iZGEgeDogeFswXSlbOm51bV1dCgpkZWYgZmluZF9vcmlnaW5hbF9zb2x1dGlvbnMoc29sdXRpb25zLCBiYWxhbmNlZF9zb2x1dGlvbnMsIG51bT0zKToKICAgICIiIuS7juWJqeS9meino+S4reiOt+WPluWOn+Wni+mhuuW6j+eahOinoyIiIgogICAgaWYgbm90IHNvbHV0aW9uczoKICAgICAgICByZXR1cm4gW10KICAgIAogICAgcmVtYWluaW5nID0gW3MgZm9yIHMgaW4gc29sdXRpb25zIGlmIHMgbm90IGluIGJhbGFuY2VkX3NvbHV0aW9uc10KICAgIHJldHVybiByZW1haW5pbmdbOm51bV0KCmRlZiBkaXNwbGF5X3NvbHV0aW9ucyhzb2x1dGlvbnNfZGljdCwgdmFyX2NvdW50KToKICAgICIiIuS8mOWMlueahOino+aYvuekuuWHveaVsCIiIgogICAgaWYgbm90IHNvbHV0aW9uc19kaWN0OgogICAgICAgIHJldHVybgogICAgCiAgICBwcmludChmIlxu5om+5YiwIHtsZW4oc29sdXRpb25zX2RpY3QpfSDnu4R7dmFyX2NvdW50feWPmOmHj+ino++8miIpCiAgICAKICAgIGZvciBpLCAoY29lZmZzLCBwYWlyX3NvbHV0aW9ucykgaW4gZW51bWVyYXRlKHNvcnRlZChzb2x1dGlvbnNfZGljdC5pdGVtcygpKSwgMSk6CiAgICAgICAgYmFsYW5jZWQgPSBmaW5kX2JhbGFuY2VkX3NvbHV0aW9ucyhwYWlyX3NvbHV0aW9ucywgdmFyX2NvdW50KQogICAgICAgIG9yaWdpbmFsID0gZmluZF9vcmlnaW5hbF9zb2x1dGlvbnMocGFpcl9zb2x1dGlvbnMsIGJhbGFuY2VkKQogICAgICAgIGFsbF9kaXNwbGF5ID0gYmFsYW5jZWQgKyBvcmlnaW5hbAogICAgICAgIAogICAgICAgIGlmIHZhcl9jb3VudCA9PSAxOgogICAgICAgICAgICBhID0gY29lZmZzCiAgICAgICAgICAgIHByaW50KGYiXG57aX0uIOe7hOWQiDogYT17YX0gKHtsZW4ocGFpcl9zb2x1dGlvbnMpfSDkuKrmnInmlYjop6MpIikKICAgICAgICBlbGlmIHZhcl9jb3VudCA9PSAyOgogICAgICAgICAgICBhLCBiID0gY29lZmZzCiAgICAgICAgICAgIHByaW50KGYiXG57aX0uIOe7hOWQiDogYT17YX0sIGI9e2J9ICh7bGVuKHBhaXJfc29sdXRpb25zKX0g5Liq5pyJ5pWI6KejKSIpCiAgICAgICAgZWxzZToKICAgICAgICAgICAgYSwgYiwgYyA9IGNvZWZmcwogICAgICAgICAgICBwcmludChmIlxue2l9LiDnu4TlkIg6IGE9e2F9LCBiPXtifSwgYz17Y30gKHtsZW4ocGFpcl9zb2x1dGlvbnMpfSDkuKrmnInmlYjop6MpIikKICAgICAgICAKICAgICAgICBmb3Igaiwgc29sIGluIGVudW1lcmF0ZShhbGxfZGlzcGxheSwgMSk6CiAgICAgICAgICAgIHRhZyA9ICJb5bmz6KGh6KejXSIgaWYgaiA8PSBsZW4oYmFsYW5jZWQpIGVsc2UgIlvljp/lp4vop6NdIgogICAgICAgICAgICAKICAgICAgICAgICAgaWYgdmFyX2NvdW50ID09IDE6CiAgICAgICAgICAgICAgICBhLCB4ID0gc29sCiAgICAgICAgICAgICAgICBwcmludChmIiAge2p9LiB4PXt4fSwgYSp4PXthKng6LjFmfSwg5oC75ZKMPXthKng6LjFmfSB7dGFnfSIpCiAgICAgICAgICAgIGVsaWYgdmFyX2NvdW50ID09IDI6CiAgICAgICAgICAgICAgICBhLCB4LCBiLCB5ID0gc29sCiAgICAgICAgICAgICAgICBwcmludChmIiAge2p9LiB4PXt4fSwgeT17eX0sIGEqeD17YSp4Oi4xZn0sIGIqeT17Yip5Oi4xZn0sIOaAu+WSjD17YSp4ICsgYip5Oi4xZn0ge3RhZ30iKQogICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgYSwgeCwgYiwgeSwgYywgeiA9IHNvbAogICAgICAgICAgICAgICAgcHJpbnQoZiIgIHtqfS4geD17eH0sIHk9e3l9LCB6PXt6fSwgIgogICAgICAgICAgICAgICAgICAgICAgZiJhKng9e2EqeDouMWZ9LCBiKnk9e2IqeTouMWZ9LCBjKno9e2MqejouMWZ9LCAiCiAgICAgICAgICAgICAgICAgICAgICBmIuaAu+WSjD17YSp4ICsgYip5ICsgYyp6Oi4xZn0ge3RhZ30iKQoKZGVmIHJ1bl93aXRoX3RpbWVvdXQoZnVuYywgYXJncz0oKSwga3dhcmdzPU5vbmUsIHRpbWVvdXQ9U09MVkVSX1RJTUVPVVQpOgogICAgIiIi6L+Q6KGM5Ye95pWw5bm26K6+572u6LaF5pe26ZmQ5Yi2IiIiCiAgICBpZiBrd2FyZ3MgaXMgTm9uZToKICAgICAgICBrd2FyZ3MgPSB7fQogICAgCiAgICByZXN1bHQgPSBbXQogICAgZXJyb3IgPSBbXQogICAgCiAgICBkZWYgd3JhcHBlcigpOgogICAgICAgIHRyeToKICAgICAgICAgICAgcmVzdWx0LmFwcGVuZChmdW5jKCphcmdzLCAqKmt3YXJncykpCiAgICAgICAgZXhjZXB0IEV4Y2VwdGlvbiBhcyBlOgogICAgICAgICAgICBlcnJvci5hcHBlbmQoZSkKICAgIAogICAgdGhyZWFkID0gdGhyZWFkaW5nLlRocmVhZCh0YXJnZXQ9d3JhcHBlcikKICAgIHRocmVhZC5kYWVtb24gPSBUcnVlCiAgICB0aHJlYWQuc3RhcnQoKQogICAgdGhyZWFkLmpvaW4odGltZW91dCkKICAgIAogICAgaWYgdGhyZWFkLmlzX2FsaXZlKCk6CiAgICAgICAgcHJpbnQoZiLorablkYo6IHtmdW5jLl9fbmFtZV9ffSDotoXml7bvvIh7dGltZW91dH3np5LvvInvvIzot7Pov4fmraTmlrnms5UiKQogICAgICAgIHJldHVybiBOb25lCiAgICAKICAgIGlmIGVycm9yOgogICAgICAgIHJhaXNlIGVycm9yWzBdCiAgICAKICAgIHJldHVybiByZXN1bHRbMF0KCmRlZiBtYWluKCk6CiAgICBwcmludChmIuebruagh+WAvDoge1RBUkdFVH0iKQogICAgCiAgICAjIOeUn+aIkOazouWKqOWQjueahOezu+aVsAogICAgRkxVQ1RVQVRFRF9WQUxVRVMgPSBbcm91bmQodiAtIEZMVUNUVUFUSU9OLCAxKSBmb3IgdiBpbiBCQVNFX1ZBTFVFU10KICAgIAogICAgIyDlsJ3or5Xln7rnoYDns7vmlbAKICAgIHByaW50KGYiXG49PT09IOWwneivleWfuuehgOezu+aVsCA9PT09IikKICAgIAogICAgIyDnm67moIflgLwyNTU5NjYgPiAyNTkwMDDkuI3miJDnq4vvvIzkvJrmjInpobrluo/lsJ3or5XljZXjgIHlj4zjgIHkuInlj5jph4/op6MKICAgIGJhc2Vfc29sdXRpb25zID0gewogICAgICAgICdzaW5nbGUnOiBydW5fd2l0aF90aW1lb3V0KGZpbmRfc2luZ2xlX3ZhcmlhYmxlX3NvbHV0aW9ucywgYXJncz0oQkFTRV9WQUxVRVMsKSksCiAgICAgICAgJ3R3byc6IHJ1bl93aXRoX3RpbWVvdXQoZmluZF90d29fdmFyaWFibGVfc29sdXRpb25zLCBhcmdzPShCQVNFX1ZBTFVFUywpKSwKICAgICAgICAndGhyZWUnOiBbXQogICAgfQogICAgCiAgICBoYXNfc29sdXRpb24gPSBGYWxzZQogICAgCiAgICAjIOaYvuekuuWNleWPmOmHj+inowogICAgaWYgYmFzZV9zb2x1dGlvbnNbJ3NpbmdsZSddOgogICAgICAgIGhhc19zb2x1dGlvbiA9IFRydWUKICAgICAgICBkaXNwbGF5X3NvbHV0aW9ucyh7YTogW3NvbF0gZm9yIGEsIHNvbCBpbiB6aXAoQkFTRV9WQUxVRVMsIGJhc2Vfc29sdXRpb25zWydzaW5nbGUnXSkgaWYgc29sfSwgMSkKICAgIAogICAgIyDmmL7npLrlj4zlj5jph4/op6MKICAgIGlmIGJhc2Vfc29sdXRpb25zWyd0d28nXSBhbmQgbGVuKGJhc2Vfc29sdXRpb25zWyd0d28nXSkgPiAwOgogICAgICAgIGhhc19zb2x1dGlvbiA9IFRydWUKICAgICAgICBkaXNwbGF5X3NvbHV0aW9ucyhiYXNlX3NvbHV0aW9uc1sndHdvJ10sIDIpCiAgICAKICAgICMg5Y2V5Y+Y6YeP5ZKM5Y+M5Y+Y6YeP6YO95peg6Kej5pe277yM5bCd6K+V5LiJ5Y+Y6YeP6KejCiAgICBpZiBub3QgaGFzX3NvbHV0aW9uOgogICAgICAgIHByaW50KGYiXG49PT09IOWNleWPmOmHj+WSjOWPjOWPmOmHj+aXoOino++8jOWwneivleS4ieWPmOmHj+inoyA9PT09IikKICAgICAgICBiYXNlX3NvbHV0aW9uc1sndGhyZWUnXSA9IHJ1bl93aXRoX3RpbWVvdXQoZmluZF90aHJlZV92YXJpYWJsZV9zb2x1dGlvbnMsIGFyZ3M9KEJBU0VfVkFMVUVTLCkpCiAgICAgICAgCiAgICAgICAgaWYgYmFzZV9zb2x1dGlvbnNbJ3RocmVlJ10gYW5kIGxlbihiYXNlX3NvbHV0aW9uc1sndGhyZWUnXSkgPiAwOgogICAgICAgICAgICBoYXNfc29sdXRpb24gPSBUcnVlCiAgICAgICAgICAgIGRpc3BsYXlfc29sdXRpb25zKGJhc2Vfc29sdXRpb25zWyd0aHJlZSddLCAzKQogICAgCiAgICBpZiBoYXNfc29sdXRpb246CiAgICAgICAgcHJpbnQoZiJcbuS9v+eUqOWfuuehgOezu+aVsOWIl+ihqO+8jOWFseaJvuWIsOacieaViOinoyIpCiAgICAgICAgcmV0dXJuCiAgICAKICAgICMg5aaC5p6c5Z+656GA57O75pWw5rKh5pyJ5om+5Yiw6Kej77yM5bCd6K+V5rOi5Yqo57O75pWwCiAgICBwcmludChmIlxuPT09PSDlsJ3or5Xms6Lliqjns7vmlbAgPT09PSIpCiAgICAKICAgIGZsdWN0dWF0ZWRfc29sdXRpb25zID0gewogICAgICAgICdzaW5nbGUnOiBydW5fd2l0aF90aW1lb3V0KGZpbmRfc2luZ2xlX3ZhcmlhYmxlX3NvbHV0aW9ucywgYXJncz0oRkxVQ1RVQVRFRF9WQUxVRVMsKSksCiAgICAgICAgJ3R3byc6IHJ1bl93aXRoX3RpbWVvdXQoZmluZF90d29fdmFyaWFibGVfc29sdXRpb25zLCBhcmdzPShGTFVDVFVBVEVEX1ZBTFVFUywpKSwKICAgICAgICAndGhyZWUnOiBbXQogICAgfQogICAgCiAgICBoYXNfc29sdXRpb24gPSBGYWxzZQogICAgCiAgICAjIOaYvuekuuWNleWPmOmHj+inowogICAgaWYgZmx1Y3R1YXRlZF9zb2x1dGlvbnNbJ3NpbmdsZSddOgogICAgICAgIGhhc19zb2x1dGlvbiA9IFRydWUKICAgICAgICBkaXNwbGF5X3NvbHV0aW9ucyh7YTogW3NvbF0gZm9yIGEsIHNvbCBpbiB6aXAoRkxVQ1RVQVRFRF9WQUxVRVMsIGZsdWN0dWF0ZWRfc29sdXRpb25zWydzaW5nbGUnXSkgaWYgc29sfSwgMSkKICAgIAogICAgIyDmmL7npLrlj4zlj5jph4/op6MKICAgIGlmIGZsdWN0dWF0ZWRfc29sdXRpb25zWyd0d28nXSBhbmQgbGVuKGZsdWN0dWF0ZWRfc29sdXRpb25zWyd0d28nXSkgPiAwOgogICAgICAgIGhhc19zb2x1dGlvbiA9IFRydWUKICAgICAgICBkaXNwbGF5X3NvbHV0aW9ucyhmbHVjdHVhdGVkX3NvbHV0aW9uc1sndHdvJ10sIDIpCiAgICAKICAgICMg5Y2V5Y+Y6YeP5ZKM5Y+M5Y+Y6YeP6YO95peg6Kej5pe277yM5bCd6K+V5LiJ5Y+Y6YeP6KejCiAgICBpZiBub3QgaGFzX3NvbHV0aW9uOgogICAgICAgIHByaW50KGYiXG49PT09IOWNleWPmOmHj+WSjOWPjOWPmOmHj+aXoOino++8jOWwneivleS4ieWPmOmHj+inoyA9PT09IikKICAgICAgICBmbHVjdHVhdGVkX3NvbHV0aW9uc1sndGhyZWUnXSA9IHJ1bl93aXRoX3RpbWVvdXQoZmluZF90aHJlZV92YXJpYWJsZV9zb2x1dGlvbnMsIGFyZ3M9KEZMVUNUVUFURURfVkFMVUVTLCkpCiAgICAgICAgCiAgICAgICAgaWYgZmx1Y3R1YXRlZF9zb2x1dGlvbnNbJ3RocmVlJ10gYW5kIGxlbihmbHVjdHVhdGVkX3NvbHV0aW9uc1sndGhyZWUnXSkgPiAwOgogICAgICAgICAgICBoYXNfc29sdXRpb24gPSBUcnVlCiAgICAgICAgICAgIGRpc3BsYXlfc29sdXRpb25zKGZsdWN0dWF0ZWRfc29sdXRpb25zWyd0aHJlZSddLCAzKQogICAgCiAgICBpZiBoYXNfc29sdXRpb246CiAgICAgICAgcHJpbnQoZiJcbuS9v+eUqOazouWKqOezu+aVsOWIl+ihqO+8jOWFseaJvuWIsOacieaViOinoyIpCiAgICAgICAgcmV0dXJuCiAgICAKICAgICMg5aaC5p6c5omA5pyJ57O75pWw6ZuG6YO95rKh5pyJ5om+5Yiw6KejCiAgICBwcmludCgiXG7msqHmnInmib7liLDnrKblkIjmnaHku7bnmoTop6PvvIzljbPkvb/kvb/nlKjms6LliqjlkI7nmoTns7vmlbDliJfooajjgIIiKQoKaWYgX19uYW1lX18gPT0gIl9fbWFpbl9fIjoKICAgIHN0YXJ0X3RpbWUgPSB0aW1lLnRpbWUoKQogICAgbWFpbigpCiAgICBwcmludChmIlxu5oC76ICX5pe2OiB7dGltZS50aW1lKCkgLSBzdGFydF90aW1lOi4yZn3np5IiKSAgICA=