XNUCA2020-RE-repair

阅读量    93929 |

分享到: QQ空间 新浪微博 微信 QQ facebook twitter

 

当初没做出来,官方也没放WP,最近有空整理一下这道题

 

题目分析

首先看一下程序逻辑

程序首先注册了SIGILL的信号处理函数。程序提供了一个qemu_arm,不知道做了什么特殊处理,官方的qemu是无法运行这段程序的,应该就是SIGILL这个地方有差异。

然后经过分析得知建立了一个二叉树头,并且把一个键值对表加入到了这个树里,最后要求输入44字符flag,起始固定为flag{,进入sub_10A54执行程序逻辑,由于需要repair,自然F5是没法儿好好解析了,其实还存在一段正确的输出。

进入逻辑函数,发现充满了PUSH {R0-R5, R7}; UND #1;这样的东西,此时会进入到SIGILL的处理函数中进行跳转,因此本题的意义就是修复这段逻辑。

首先搜索一下这个桩的Hex,发现只有这里有。

随后分析SIGILL处理函数,首先根据信号发生的位置sig_addr减去常量获得偏移,随后以这个为key去树里查找要跳转的位置,如果没有查找到,就去查找另一个表,如果找到了某一项,则根据找到的idx,去两个表里取得一个值,取哪个表取决于R6,这里应该是一个判断的结构

最后一段其实是保证堆栈平衡和手动跳转,F5失败了

因此我们优化一下条件跳转表的结构,重新F5

 

解题思路

写脚本追随跳转还原代码,随后给IDA进行分析,请看注释

from keystone import *
from capstone import *
from enum import Enum

# 原程序提取出来的数据
jump_offsets = [3072, 2050, 4, 3414, 2056, 3756, 10, 2062, 16, 2068, 22, 2074, 28, 2080, 34, 1030, 2086, 40, 3420, 2092,
                3762, 46, 2098, 52, 2104, 58, 2110, 64, 2116, 70, 1036, 2122, 76, 3426, 2128, 3768, 82, 2134, 88, 2140,
                94, 2146, 100, 2152, 106, 3090, 2158, 112, 3432, 2164, 118, 124, 2176, 130, 2182, 136, 2188, 142, 3096,
                2194, 148, 3438, 2200, 154, 2206, 160, 2212, 166, 2218, 172, 2224, 178, 3102, 2230, 184, 3444, 2236,
                190, 2242, 196, 2248, 202, 208, 2260, 214, 1060, 2266, 220, 3450, 2272, 226, 2278, 232, 2284, 238, 2290,
                244, 2296, 250, 1066, 2302, 256, 3456, 2308, 262, 2314, 268, 2320, 274, 2326, 280, 2332, 286, 3120,
                2338, 292, 1414, 2344, 298, 2350, 304, 2356, 310, 2362, 316, 2368, 322, 1078, 2374, 328, 1420, 2380,
                334, 2386, 340, 2392, 346, 2398, 352, 2404, 358, 3132, 2410, 364, 3474, 2416, 370, 2422, 376, 2428, 382,
                2434, 388, 2440, 1090, 2446, 400, 3480, 2452, 406, 2458, 412, 2464, 418, 2470, 424, 2476, 430, 1096,
                2482, 436, 1438, 2488, 442, 2494, 448, 2500, 454, 2506, 460, 2512, 466, 1102, 2518, 472, 1444, 2524,
                478, 2530, 484, 2536, 490, 2542, 496, 2548, 502, 3156, 2554, 508, 3498, 2560, 514, 2566, 520, 2572, 526,
                2578, 532, 2584, 538, 3162, 2590, 544, 1456, 2596, 550, 2602, 556, 2608, 562, 2614, 568, 2620, 574,
                3168, 2626, 580, 1462, 2632, 586, 2638, 592, 2644, 598, 2650, 604, 2656, 610, 1126, 2662, 616, 3516,
                2668, 622, 2674, 628, 2680, 634, 2686, 640, 2692, 646, 3180, 2698, 652, 3522, 2704, 2710, 664, 2716,
                670, 2722, 676, 2728, 796, 682, 2734, 688, 3528, 2740, 694, 2746, 700, 2752, 706, 2758, 712, 2764, 2850,
                718, 3192, 2770, 724, 1486, 2776, 730, 2782, 736, 2788, 742, 2794, 748, 2800, 2856, 754, 3198, 2806,
                760, 1492, 2812, 766, 2818, 772, 2824, 778, 2830, 784, 2862, 790, 3204, 2844, 1498, 802, 808, 814, 820,
                2868, 2874, 1162, 832, 1504, 838, 2892, 850, 856, 826, 862, 3216, 868, 3558, 874, 880, 2934, 2940, 2880,
                2946, 1174, 2952, 3564, 910, 916, 2970, 928, 2886, 934, 1180, 2988, 1522, 2994, 3000, 3006, 3012, 844,
                970, 1186, 976, 1528, 982, 3036, 3042, 3048, 2898, 3054, 3240, 1012, 3582, 1018, 1024, 3078, 3084, 2904,
                1042, 3246, 1048, 3588, 1054, 3108, 3114, 1072, 2910, 3126, 3252, 1084, 3594, 3138, 3144, 3150, 1108,
                2916, 1114, 1210, 1120, 3600, 3174, 1132, 3186, 1144, 2922, 1150, 1216, 1156, 1558, 3210, 1168, 3222,
                3228, 2928, 3234, 1222, 1192, 1198, 1204, 3258, 3264, 886, 3270, 1228, 3276, 1570, 1234, 3288, 1246,
                1252, 892, 1258, 3282, 3312, 1576, 1270, 3324, 3330, 1288, 898, 3342, 1240, 1300, 3630, 3354, 3360,
                3366, 3372, 904, 1330, 3294, 1336, 3636, 3390, 3396, 3402, 1360, 2958, 1366, 3300, 1372, 3642, 1378,
                1384, 1390, 1396, 2964, 1402, 3306, 1408, 3648, 3462, 3468, 1426, 1432, 922, 3486, 1264, 3492, 1606,
                1450, 3504, 3510, 1468, 2976, 1474, 3318, 1480, 3660, 3534, 3540, 3546, 3552, 2982, 1510, 1276, 1516,
                3666, 3570, 3576, 1534, 1540, 940, 1546, 1282, 1552, 3672, 3606, 1564, 3618, 3624, 946, 1582, 3336,
                1588, 1630, 1594, 1600, 3654, 1612, 952, 1618, 1294, 1624, 1636, 3678, 3684, 3690, 1648, 958, 3702,
                3348, 1660, 3714, 1672, 1678, 1684, 964, 3738, 1306, 3744, 3696, 3750, 1708, 1714, 1720, 3018, 1726,
                1312, 1732, 1654, 1738, 1744, 1750, 1756, 3024, 1762, 1318, 1768, 3708, 1774, 1780, 1786, 1792, 3030,
                1798, 1324, 1804, 1666, 1810, 1816, 1822, 1828, 988, 1834, 3378, 1840, 3720, 1846, 1852, 1858, 1864,
                994, 1870, 3384, 1876, 3726, 1882, 1888, 1894, 1900, 1000, 1906, 1912, 3732, 1918, 1924, 1930, 1936,
                1006, 1942, 1948, 1690, 1954, 1960, 1966, 1972, 3060, 1978, 1354, 1984, 1696, 1990, 1996, 2002, 2008,
                3066, 2014, 3408, 2020, 1702, 2026, 2032, 2038, 2044]
jump_targets = [-1380, 1426, 3520, -1062, -1534, -436, 1130, 650, 662, -442, 2636, -520, 3220, -1522, 626, 1646, -562,
                1442, -2172, 1246, -1740, 806, 982, 2492, 620, 1766, -22, 554, -1582, -16, 686, -1276, 1058, -1950, 140,
                -2334, 1130, -1042, 1628, -196, 260, 86, 686, 530, 2468, -1854, -22, 80, -1680, -520, 8, 2312, -2086,
                -58, -1894, 2024, -1378, 2222, -1044, -1390, 1808, -1224, 1342, 2800, 958, 2234, -292, 1250, -412, 2498,
                1384, 890, 608, -1546, 3280, -400, -982, 854, 1144, 1616, 640, 1412, 398, 706, 3292, 2686, -1636, 2540,
                -1800, -202, 2354, 1276, 3424, -796, 14, -1690, 1478, -1876, 458, 374, 1072, 2234, -1068, -520, 1688,
                796, 488, -58, 3208, -1468, 2752, -2014, 1688, -432, -1504, 1250, -904, -1888, 824, -1972, -244, -838,
                3268, 478, 1580, 398, 1106, 2254, -1642, 1418, 2116, -1834, 578, 490, 2354, 520, 3292, -898, 836, 862,
                1604, -960, -688, 2222, 230, -2074, 3226, 224, 3094, 502, 1346, 266, -106, -1414, 2002, -994, -298,
                -2022, -946, 602, -1378, 38, -682, 146, -1198, 950, -1522, 2168, -790, -2236, 2416, 1762, -1042, 2884,
                -838, 2330, -1576, 2174, -322, 1568, -652, -400, 1756, -808, 1202, 428, -1132, 3124, -214, 1496, -700,
                2752, 272, 410, -1858, 1376, -726, -832, 1292, 14, 928, 2638, 230, 974, -2092, -94, -478, 296, -898,
                2446, -936, -1864, 632, 1316, 1196, 2518, -1540, 2878, -2032, 2078, -1600, 1418, 1030, 1556, -1788,
                -964, 68, 572, -568, 1796, -1408, 668, -1540, 1334, -1054, 1508, -1954, 2464, 1876, -2362, 1868, -2358,
                -1132, 14, 158, 2308, -58, 3130, 934, 2950, 856, 1172, 380, -832, 1646, -1818, -196, -694, 2866, -2494,
                2230, 562, -22, 934, 1772, 2036, -808, -16, -2778, -2350, 248, -508, 3052, -1582, 2812, 700, 2158, 232,
                -1008, 1784, -1878, -1504, 74, 1702, -1138, 1118, -1654, 446, -418, 1364, -2446, -664, -1402, -2316,
                1148, -3186, -1228, 1892, -1120, -736, 14, -1852, 2680, -814, 2716, -676, -316, 542, -124, -2652, -960,
                -1342, 968, 1238, 2224, -460, 488, -66, 128, 776, -1180, 2110, 314, 782, 74, 1922, 2188, -2166, 1646,
                -1956, -382, 1496, -1632, 182, -1920, 284, 1100, -1218, -1560, -496, -412, -570, 1814, -948, -310, 38,
                -630, -490, 350, -2850, -2910, 290, 1070, 1286, 1720, 2296, -382, 302, -1470, -2964, -2076, -2682,
                -1224, -2238, -982, -1404, 2242, -496, -2958, -2220, -2520, -544, -2148, -112, -460, 146, -1914, -2982,
                1124, -2514, 566, -840, -940, -1188, -2238, 284, -3012, 1316, 398, 740, -136, 1936, -984, -420, 1502,
                -2304, 164, -192, -1126, 1088, 206, 1462, -1884, 1930, -340, -2658, -324, 506, 1118, -862, 1280, -286,
                -2220, -118, -118, -2046, 194, 440, 2152, 122, -3060, 224, -274, 848, 2422, -2508, -1728, -172, -868,
                -534, -1536, 602, 254, -352, 2050, 1028, -3018, -912, -2244, -2346, -1380, 872, 920, -76, 782, -244,
                -2670, -3030, -1080, 1894, -432, 692, -1980, -1102, -3402, 812, 1984, 182, -154, -654, -688, -3144,
                2014, -2658, -1242, 218, 1936, -1006, 2002, -106, 2014, -2382, 1408, 1858, -942, -3066, -1156, -1212,
                86, -358, 1462, -634, -1248, 188, -1014, -2658, -390, 1498, 2308, -1078, -1200, -1122, -1230, -1426,
                -952, 1796, 1348, 1582, 2206, -1392, -3408, 578, -478, -3360, -76, -1534, -250, -1552, 1034, -1480, 308,
                -418, 1190, 386, 2, 1930, 134, 1978, -106, -1074, -1596, -316, 2668, -2316, -1014, 2008, -2202, -1378,
                44, 38, 380, -2976, 362, -2466, -2400, -2028, 1732, -1378, -556, -46, -1726, 1238, 974, -1378, 818,
                -1726, 1432, -1750, -106, 758, 1798, 1294, -2502, -898, 1046, -1270, -1534, -2622, -1324, -376, -1600,
                1154, -1168, 656, -100, -1036, 2116, 1864, 356, -1000, -1266, 1720, 1546, 140, 428, -826, -322, -1182,
                1570, -226, 1792, -538, -364, -490, -16, 260, 872, -538, 50, 1868, -844, 602, -772, -1054, -484, 8,
                -1360, -1144, -1780, 1240, 116, -1240, 2062, -1498, -16, -1816, 500, 1132, -640, -942, 134, -3228, -964,
                380, 820, 428, -1828, 1252]

cond_offsets = [658, 1342, 1348, 2170, 2838, 394, 1642, 3612, 1138, 2254]
cond_targets = [[-196, -76], [1076, 2302], [2284, 692], [-1348, -580], [-630, -1116], [3016, 2584], [-1600, 1528],
                [-2916, -1368], [-142, 2212], [-1510, 904]]

# 读原始程序
repair = open(r"E:\Ctf\XNUCA2020\repair\repair\repair", 'rb')
repair_bytes = repair.read()
repair.close()

# 寻找桩
stub = bytes([0xbf, 0xb4, 0x01, 0xde])
stub_pos = 0
stubs = [] 
while True:
    stub_pos = repair_bytes.find(stub, stub_pos)
    if stub_pos == -1:
        break
    stubs.append(stub_pos)
    stub_pos += len(stub)

# 把所有桩之间的代码存起来
codes = {0xA64: repair_bytes[0xA64: 0xA66]}
for i in range(len(stubs) - 1):
    code_start = stubs[i] + 4
    code_len = stubs[i + 1] - code_start
    codes[code_start] = repair_bytes[code_start: code_start + code_len] 

# 指令类型
class inst_type(Enum):
    UNK = 0
    INS = 1, # 原指令
    COND = 2, # 条件跳转
    B = 3 # 跳转

# 自定义指令
class instruction(object):
    def __init__(self):
        self.address = None
        self.code = None
        self.type = inst_type.UNK
        self.tag = False

# 在所有指令里寻找某地址
def ins_find(ins, pc):
    for inst in ins:
        if inst.type == inst_type.INS and inst.address == pc:
            return inst
    return None

# 提取程序流
def extract_procedures(pc, ins):
    while True:
        if pc in stubs: 
            # 如果是桩
            sig_addr = pc + 2
            sig_offset = sig_addr - 0xA64
            if sig_offset in jump_offsets:
                # 指向下一步
                pc = jump_targets[jump_offsets.index(sig_offset)] + sig_addr
            elif sig_offset in cond_offsets:
                # 条件跳转
                inst = instruction()
                inst.type = inst_type.COND
                inst.address = []
                ins.append(inst)
                for k in range(2):
                    pc_next = cond_targets[cond_offsets.index(sig_offset)][k] + sig_addr
                    inst.address.append(pc_next)
                    # 递归进行
                    extract_procedures(pc_next, ins)
                break
            else:
                exit(-1)
        elif pc in codes.keys():
            # 不是桩
            sig_code = codes[pc]
            ins_f = ins_find(ins, pc)
            if ins_f is None:
                # 没走过存入列表
                inst = instruction()
                inst.type = inst_type.INS
                inst.address = pc
                inst.code = sig_code
                ins.append(inst)
            else: 
                # 走过的路径直接跳转过去
                inst = instruction()
                inst.type = inst_type.B
                inst.address = pc
                ins.append(inst)
                break
            pc += len(sig_code)
        else:
            # 程序流结束
            inst = instruction()
            inst.type = inst_type.B
            inst.address = pc
            ins.append(inst)
            break

# 汇编中被跳转的地址需要有个Label
def fix_tag(ins):
    for inst in ins:
        if inst.type == inst_type.COND:
            for a in inst.address:
                ins_f = ins_find(ins, a)
                ins_f.tag = True
        elif inst.type == inst_type.B:
            ins_f = ins_find(ins, inst.address)
            if inst.address != 6452:
                ins_f.tag = True


instructions = []
pc_init = 0xA64

extract_procedures(pc_init, instructions) 
fix_tag(instructions)

ks = Ks(KS_ARCH_ARM, KS_MODE_THUMB)
cs = Cs(CS_ARCH_ARM, CS_MODE_THUMB)
asm = ''

# 原函数开始
for i in cs.disasm(repair_bytes[0xA54:0xA66], 0x10A54):
    asm += "\t%s\t%s\r\n" % (i.mnemonic, i.op_str)

# 按提取的指令还原程序流
for p in instructions:
    if p.tag: 
        # 被跳转目标的Label
        asm += "pos_%d:\r\n" % p.address
    if p.type == inst_type.INS:
        # 原代码直接复制
        for i in cs.disasm(p.code, p.address + 0x10000):
            asm += "\t%s\t%s\r\n" % (i.mnemonic, i.op_str)
    elif p.type == inst_type.B:
        # 跳转
        asm += "\tb pos_%d\r\n" % p.address
    elif p.type == inst_type.COND:
        # 条件跳转
        asm += "\tcmp r6, #0\r\n"
        asm += "\tbeq pos_%d\r\n" % p.address[0]
        asm += "\tb pos_%d\r\n" % p.address[1]

# 程序判断输入正确的跳转
asm += "pos_6452:\r\n" 
for i in cs.disasm(repair_bytes[0x1934:0x193C], 0x11934):
    asm += "\t%s\t%s\r\n" % (i.mnemonic, i.op_str)

assembly, _ = ks.asm(asm, 0x10A54) 

# 输出
repair_bytes = list(repair_bytes)
repair_bytes[0xA54: 0xA54 + len(assembly)] = assembly
fp = open(r"E:\Ctf\XNUCA2020\repair\repair\repaired", 'wb')
fp.write(bytes(repair_bytes))
fp.close()

 

还原后分析

还原后代码如下

int __fastcall sub_10A54(unsigned __int8 *a1, unsigned __int8 *a2, int *a3)
{
  int v5; // [sp+14h] [bp+14h]

  v5 = 0;
  do
  {
    while ( 1 )
    {
      while ( 1 )
      {
        while ( 1 )
        {
          while ( 1 )
          {
            while ( 1 )
            {
              while ( 1 )
              {
                while ( 1 )
                {
                  while ( !a2[v5] )
                  {
                    a3[a2[v5 + 1]] = (16975111 * (a2[v5 + 1] + 127)) ^ a1[(16975111 * (a2[v5 + 2] + 127)) ^ a3[a2[v5 + 2]]];
                    v5 += 3;
                  }
                  if ( a2[v5] != 1 )
                    break;
                  a3[a2[v5 + 1]] = (16975111 * (a2[v5 + 1] + 127)) ^ ((a3[a2[v5 + 3]] ^ (16975111 * (a2[v5 + 3] + 127)))
                                                                    + ((16975111 * (a2[v5 + 2] + 127)) ^ a3[a2[v5 + 2]]));
                  v5 += 4;
                }
                if ( a2[v5] != 2 )
                  break;
                a3[a2[v5 + 1]] = (16975111 * (a2[v5 + 1] + 127)) ^ ((a3[a2[v5 + 3]] ^ (16975111 * (a2[v5 + 3] + 127)))
                                                                  - ((16975111 * (a2[v5 + 2] + 127)) ^ a3[a2[v5 + 2]]));
                v5 += 4;
              }
              if ( a2[v5] != 3 )
                break;
              a3[a2[v5 + 1]] = (16975111 * (a2[v5 + 1] + 127)) ^ ((a3[a2[v5 + 3]] ^ (16975111 * (a2[v5 + 3] + 127)))
                                                                * ((16975111 * (a2[v5 + 2] + 127)) ^ a3[a2[v5 + 2]]));
              v5 += 4;
            }
            if ( a2[v5] != 4 )
              break;
            a3[a2[v5 + 1]] = (16975111 * (a2[v5 + 1] + 127)) ^ a3[a2[v5 + 3]] ^ (0x1030507 * (a2[v5 + 3] + 127)) ^ (16975111 * (a2[v5 + 2] + 127)) ^ a3[a2[v5 + 2]];
            v5 += 4;
          }
          if ( a2[v5] != 5 )
            break;
          a3[a2[v5 + 1]] = (16975111 * (a2[v5 + 1] + 127)) ^ (a3[a2[v5 + 3]] ^ (0x1030507 * (a2[v5 + 3] + 127))) & ((0x1030507 * (a2[v5 + 2] + 127)) ^ a3[a2[v5 + 2]]);
          v5 += 4;
        }
        if ( a2[v5] != 6 )
          break;
        a3[a2[v5 + 1]] = (16975111 * (a2[v5 + 1] + 127)) ^ *(_DWORD *)&a2[v5 + 2];
        v5 += 6;
      }
      if ( a2[v5] != 7 )
        break;
      if ( a3[a2[v5 + 1]] != 16975111 * (a2[v5 + 1] + 127) )
        return 0;
      v5 += 2;
    }
  }
  while ( a2[v5] != 8 );
  return 1;
}

分析可知程序这个函数验证了输入的40个字节,每8个字节验证一次一共验证5次

把校验函数代码翻译成python,尝试使用z3一把梭

from z3 import *
from pwn import *

op_code = bytes([6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 1, 0, 6, 0, 52, 63, 93, 10,
                 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 1, 0, 0, 0, 0, 1, 0, 6, 0, 120, 211, 169, 103, 4, 0, 0, 1, 2, 2, 0, 2, 6,
                 0, 2, 0, 0, 0, 0, 1, 0, 6, 0, 175, 47, 169, 91, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 3, 0, 0, 0, 0, 1, 0, 6,
                 0, 115, 150, 38, 72, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 4, 0, 0, 0, 0, 1, 0, 6, 0, 60, 126, 77, 158, 3, 0,
                 0, 1, 1, 2, 0, 2, 6, 0, 5, 0, 0, 0, 0, 1, 0, 6, 0, 217, 228, 101, 79, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 6,
                 0, 0, 0, 0, 1, 0, 6, 0, 28, 84, 26, 230, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 7, 0, 0, 0, 0, 1, 0, 6, 0, 30,
                 3, 80, 143, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 164, 230, 153, 151, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1,
                 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 1, 0, 6, 0, 162, 242, 37, 111, 3, 0, 0, 1, 2, 2, 0,
                 2, 6, 0, 1, 0, 0, 0, 0, 1, 0, 6, 0, 193, 147, 115, 247, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 2, 0, 0, 0, 0, 1,
                 0, 6, 0, 158, 3, 133, 221, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 3, 0, 0, 0, 0, 1, 0, 6, 0, 186, 93, 22, 206,
                 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 4, 0, 0, 0, 0, 1, 0, 6, 0, 236, 160, 62, 184, 3, 0, 0, 1, 1, 2, 0, 2, 6,
                 0, 5, 0, 0, 0, 0, 1, 0, 6, 0, 157, 89, 165, 156, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 6, 0, 0, 0, 0, 1, 0, 6,
                 0, 106, 1, 113, 62, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 7, 0, 0, 0, 0, 1, 0, 6, 0, 204, 213, 233, 48, 4, 0,
                 0, 1, 1, 2, 0, 2, 6, 0, 199, 16, 237, 137, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2,
                 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 1, 0, 6, 0, 108, 21, 168, 205, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 1, 0, 0,
                 0, 0, 1, 0, 6, 0, 195, 253, 89, 23, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 2, 0, 0, 0, 0, 1, 0, 6, 0, 96, 200,
                 5, 224, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 3, 0, 0, 0, 0, 1, 0, 6, 0, 235, 173, 43, 77, 4, 0, 0, 1, 1, 2, 0,
                 2, 6, 0, 4, 0, 0, 0, 0, 1, 0, 6, 0, 106, 38, 37, 140, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 5, 0, 0, 0, 0, 1,
                 0, 6, 0, 114, 47, 190, 246, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 6, 0, 0, 0, 0, 1, 0, 6, 0, 109, 67, 117, 23,
                 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 7, 0, 0, 0, 0, 1, 0, 6, 0, 114, 237, 93, 147, 4, 0, 0, 1, 2, 2, 0, 2, 6,
                 0, 150, 148, 12, 129, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 0,
                 0, 0, 0, 0, 1, 0, 6, 0, 84, 21, 18, 47, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 1, 0, 0, 0, 0, 1, 0, 6, 0, 92,
                 241, 112, 8, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 2, 0, 0, 0, 0, 1, 0, 6, 0, 61, 162, 175, 17, 4, 0, 0, 1, 2,
                 2, 0, 2, 6, 0, 3, 0, 0, 0, 0, 1, 0, 6, 0, 235, 21, 116, 224, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 4, 0, 0, 0,
                 0, 1, 0, 6, 0, 40, 137, 171, 215, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 5, 0, 0, 0, 0, 1, 0, 6, 0, 253, 101,
                 126, 214, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 6, 0, 0, 0, 0, 1, 0, 6, 0, 147, 249, 119, 217, 4, 0, 0, 1, 1,
                 2, 0, 2, 6, 0, 7, 0, 0, 0, 0, 1, 0, 6, 0, 114, 244, 102, 148, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 94, 45, 27,
                 95, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 1, 0,
                 6, 0, 197, 185, 30, 126, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 1, 0, 0, 0, 0, 1, 0, 6, 0, 245, 3, 7, 83, 4, 0,
                 0, 1, 1, 2, 0, 2, 6, 0, 2, 0, 0, 0, 0, 1, 0, 6, 0, 12, 151, 74, 150, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 3,
                 0, 0, 0, 0, 1, 0, 6, 0, 45, 165, 55, 62, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 4, 0, 0, 0, 0, 1, 0, 6, 0, 82,
                 147, 252, 29, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 5, 0, 0, 0, 0, 1, 0, 6, 0, 56, 218, 105, 203, 3, 0, 0, 1,
                 2, 2, 0, 2, 6, 0, 6, 0, 0, 0, 0, 1, 0, 6, 0, 24, 254, 22, 109, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 7, 0, 0,
                 0, 0, 1, 0, 6, 0, 99, 132, 122, 200, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 5, 235, 248, 214, 2, 2, 0, 2, 7, 2,
                 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 1, 0, 6, 0, 177, 133, 148,
                 11, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 1, 0, 0, 0, 0, 1, 0, 6, 0, 50, 155, 219, 31, 3, 0, 0, 1, 1, 2, 0, 2,
                 6, 0, 2, 0, 0, 0, 0, 1, 0, 6, 0, 213, 92, 38, 100, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 3, 0, 0, 0, 0, 1, 0,
                 6, 0, 21, 228, 118, 213, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 4, 0, 0, 0, 0, 1, 0, 6, 0, 68, 98, 2, 155, 3, 0,
                 0, 1, 1, 2, 0, 2, 6, 0, 5, 0, 0, 0, 0, 1, 0, 6, 0, 65, 53, 6, 246, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 6, 0,
                 0, 0, 0, 1, 0, 6, 0, 137, 30, 175, 122, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 7, 0, 0, 0, 0, 1, 0, 6, 0, 248,
                 69, 221, 239, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 94, 144, 41, 46, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1,
                 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 1, 0, 6, 0, 218, 179, 223, 158, 3, 0, 0, 1, 2, 2, 0,
                 2, 6, 0, 1, 0, 0, 0, 0, 1, 0, 6, 0, 73, 221, 235, 17, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 2, 0, 0, 0, 0, 1,
                 0, 6, 0, 152, 252, 156, 165, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 3, 0, 0, 0, 0, 1, 0, 6, 0, 233, 65, 162,
                 111, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 4, 0, 0, 0, 0, 1, 0, 6, 0, 110, 98, 238, 128, 3, 0, 0, 1, 1, 2, 0,
                 2, 6, 0, 5, 0, 0, 0, 0, 1, 0, 6, 0, 110, 76, 179, 152, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 6, 0, 0, 0, 0, 1,
                 0, 6, 0, 46, 11, 9, 51, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 7, 0, 0, 0, 0, 1, 0, 6, 0, 55, 187, 134, 231, 4,
                 0, 0, 1, 2, 2, 0, 2, 6, 0, 26, 54, 157, 215, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6,
                 2, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 1, 0, 6, 0, 125, 86, 156, 178, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 1, 0,
                 0, 0, 0, 1, 0, 6, 0, 178, 234, 228, 201, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 2, 0, 0, 0, 0, 1, 0, 6, 0, 113,
                 219, 161, 87, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 3, 0, 0, 0, 0, 1, 0, 6, 0, 5, 98, 199, 152, 4, 0, 0, 1, 1,
                 2, 0, 2, 6, 0, 4, 0, 0, 0, 0, 1, 0, 6, 0, 76, 98, 97, 3, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 5, 0, 0, 0, 0,
                 1, 0, 6, 0, 110, 227, 108, 230, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 6, 0, 0, 0, 0, 1, 0, 6, 0, 220, 30, 126,
                 99, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 7, 0, 0, 0, 0, 1, 0, 6, 0, 247, 142, 131, 143, 4, 0, 0, 1, 1, 2, 0,
                 2, 6, 0, 10, 65, 126, 146, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6,
                 0, 8, 0, 0, 0, 0, 1, 0, 6, 0, 155, 225, 215, 189, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 9, 0, 0, 0, 0, 1, 0, 6,
                 0, 26, 57, 48, 189, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 10, 0, 0, 0, 0, 1, 0, 6, 0, 164, 199, 132, 34, 3, 0,
                 0, 1, 2, 2, 0, 2, 6, 0, 11, 0, 0, 0, 0, 1, 0, 6, 0, 91, 132, 43, 90, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 12,
                 0, 0, 0, 0, 1, 0, 6, 0, 45, 128, 28, 151, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 13, 0, 0, 0, 0, 1, 0, 6, 0,
                 247, 40, 85, 99, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 14, 0, 0, 0, 0, 1, 0, 6, 0, 47, 244, 99, 0, 4, 0, 0, 1,
                 1, 2, 0, 2, 6, 0, 15, 0, 0, 0, 0, 1, 0, 6, 0, 4, 13, 251, 40, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 142, 177,
                 221, 152, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 8, 0, 0, 0, 0,
                 1, 0, 6, 0, 111, 171, 44, 163, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 9, 0, 0, 0, 0, 1, 0, 6, 0, 247, 142, 217,
                 181, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 10, 0, 0, 0, 0, 1, 0, 6, 0, 137, 9, 251, 102, 4, 0, 0, 1, 1, 2, 0,
                 2, 6, 0, 11, 0, 0, 0, 0, 1, 0, 6, 0, 199, 188, 105, 42, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 12, 0, 0, 0, 0,
                 1, 0, 6, 0, 0, 194, 92, 66, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 13, 0, 0, 0, 0, 1, 0, 6, 0, 76, 24, 15, 135,
                 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 14, 0, 0, 0, 0, 1, 0, 6, 0, 96, 180, 69, 226, 4, 0, 0, 1, 1, 2, 0, 2, 6,
                 0, 15, 0, 0, 0, 0, 1, 0, 6, 0, 87, 31, 113, 83, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 234, 14, 67, 70, 2, 2, 0,
                 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 8, 0, 0, 0, 0, 1, 0, 6, 0, 140,
                 125, 195, 12, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 9, 0, 0, 0, 0, 1, 0, 6, 0, 55, 160, 110, 140, 4, 0, 0, 1,
                 1, 2, 0, 2, 6, 0, 10, 0, 0, 0, 0, 1, 0, 6, 0, 54, 101, 160, 252, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 11, 0,
                 0, 0, 0, 1, 0, 6, 0, 12, 156, 21, 243, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 12, 0, 0, 0, 0, 1, 0, 6, 0, 245,
                 105, 222, 0, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 13, 0, 0, 0, 0, 1, 0, 6, 0, 10, 158, 162, 183, 3, 0, 0, 1,
                 1, 2, 0, 2, 6, 0, 14, 0, 0, 0, 0, 1, 0, 6, 0, 106, 11, 194, 48, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 15, 0, 0,
                 0, 0, 1, 0, 6, 0, 237, 214, 167, 223, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 15, 22, 84, 176, 2, 2, 0, 2, 7, 2,
                 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 8, 0, 0, 0, 0, 1, 0, 6, 0, 74, 56, 68, 176,
                 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 9, 0, 0, 0, 0, 1, 0, 6, 0, 199, 87, 193, 121, 3, 0, 0, 1, 1, 2, 0, 2, 6,
                 0, 10, 0, 0, 0, 0, 1, 0, 6, 0, 182, 186, 151, 5, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 11, 0, 0, 0, 0, 1, 0, 6,
                 0, 81, 93, 193, 204, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 12, 0, 0, 0, 0, 1, 0, 6, 0, 109, 233, 39, 34, 3, 0,
                 0, 1, 2, 2, 0, 2, 6, 0, 13, 0, 0, 0, 0, 1, 0, 6, 0, 253, 135, 50, 223, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0,
                 14, 0, 0, 0, 0, 1, 0, 6, 0, 38, 233, 234, 217, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 15, 0, 0, 0, 0, 1, 0, 6,
                 0, 142, 248, 104, 10, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 156, 229, 69, 98, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0,
                 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 8, 0, 0, 0, 0, 1, 0, 6, 0, 212, 118, 240, 142, 3, 0, 0, 1,
                 2, 2, 0, 2, 6, 0, 9, 0, 0, 0, 0, 1, 0, 6, 0, 106, 150, 61, 240, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 10, 0, 0,
                 0, 0, 1, 0, 6, 0, 38, 34, 93, 182, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 11, 0, 0, 0, 0, 1, 0, 6, 0, 181, 229,
                 88, 95, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 12, 0, 0, 0, 0, 1, 0, 6, 0, 174, 0, 38, 96, 3, 0, 0, 1, 1, 2, 0,
                 2, 6, 0, 13, 0, 0, 0, 0, 1, 0, 6, 0, 44, 250, 113, 35, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 14, 0, 0, 0, 0, 1,
                 0, 6, 0, 133, 80, 90, 85, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 15, 0, 0, 0, 0, 1, 0, 6, 0, 28, 164, 239, 183,
                 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 98, 69, 68, 97, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6,
                 2, 0, 0, 0, 0, 6, 0, 8, 0, 0, 0, 0, 1, 0, 6, 0, 251, 237, 135, 199, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 9, 0,
                 0, 0, 0, 1, 0, 6, 0, 246, 4, 6, 69, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 10, 0, 0, 0, 0, 1, 0, 6, 0, 102, 200,
                 94, 251, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 11, 0, 0, 0, 0, 1, 0, 6, 0, 86, 38, 17, 101, 4, 0, 0, 1, 2, 2,
                 0, 2, 6, 0, 12, 0, 0, 0, 0, 1, 0, 6, 0, 252, 233, 105, 29, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 13, 0, 0, 0,
                 0, 1, 0, 6, 0, 237, 145, 10, 239, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 14, 0, 0, 0, 0, 1, 0, 6, 0, 71, 119,
                 249, 45, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 15, 0, 0, 0, 0, 1, 0, 6, 0, 217, 39, 54, 103, 3, 0, 0, 1, 2, 2,
                 0, 2, 6, 0, 34, 19, 23, 56, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6,
                 0, 8, 0, 0, 0, 0, 1, 0, 6, 0, 0, 66, 43, 106, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 9, 0, 0, 0, 0, 1, 0, 6, 0,
                 197, 157, 146, 143, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 10, 0, 0, 0, 0, 1, 0, 6, 0, 9, 249, 74, 86, 4, 0, 0,
                 1, 2, 2, 0, 2, 6, 0, 11, 0, 0, 0, 0, 1, 0, 6, 0, 24, 122, 165, 122, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 12,
                 0, 0, 0, 0, 1, 0, 6, 0, 74, 123, 49, 109, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 13, 0, 0, 0, 0, 1, 0, 6, 0,
                 157, 253, 199, 85, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 14, 0, 0, 0, 0, 1, 0, 6, 0, 160, 58, 114, 160, 3, 0,
                 0, 1, 1, 2, 0, 2, 6, 0, 15, 0, 0, 0, 0, 1, 0, 6, 0, 149, 154, 218, 16, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0,
                 11, 156, 110, 187, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 8, 0,
                 0, 0, 0, 1, 0, 6, 0, 206, 131, 247, 191, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 9, 0, 0, 0, 0, 1, 0, 6, 0, 105,
                 24, 131, 98, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 10, 0, 0, 0, 0, 1, 0, 6, 0, 19, 169, 208, 100, 3, 0, 0, 1,
                 1, 2, 0, 2, 6, 0, 11, 0, 0, 0, 0, 1, 0, 6, 0, 86, 48, 143, 235, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 12, 0, 0,
                 0, 0, 1, 0, 6, 0, 53, 73, 76, 108, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 13, 0, 0, 0, 0, 1, 0, 6, 0, 99, 4, 91,
                 56, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 14, 0, 0, 0, 0, 1, 0, 6, 0, 67, 144, 100, 110, 4, 0, 0, 1, 1, 2, 0,
                 2, 6, 0, 15, 0, 0, 0, 0, 1, 0, 6, 0, 229, 131, 113, 29, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 94, 245, 152,
                 105, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 16, 0, 0, 0, 0, 1,
                 0, 6, 0, 183, 197, 43, 231, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 17, 0, 0, 0, 0, 1, 0, 6, 0, 153, 247, 112,
                 30, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 18, 0, 0, 0, 0, 1, 0, 6, 0, 225, 182, 168, 65, 4, 0, 0, 1, 2, 2, 0,
                 2, 6, 0, 19, 0, 0, 0, 0, 1, 0, 6, 0, 161, 27, 62, 255, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 20, 0, 0, 0, 0, 1,
                 0, 6, 0, 238, 18, 201, 26, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 21, 0, 0, 0, 0, 1, 0, 6, 0, 237, 195, 198, 96,
                 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 22, 0, 0, 0, 0, 1, 0, 6, 0, 242, 182, 208, 26, 4, 0, 0, 1, 1, 2, 0, 2, 6,
                 0, 23, 0, 0, 0, 0, 1, 0, 6, 0, 59, 21, 92, 144, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 101, 64, 106, 93, 2, 2,
                 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 16, 0, 0, 0, 0, 1, 0, 6, 0, 27,
                 42, 174, 224, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 17, 0, 0, 0, 0, 1, 0, 6, 0, 134, 131, 98, 213, 4, 0, 0, 1,
                 2, 2, 0, 2, 6, 0, 18, 0, 0, 0, 0, 1, 0, 6, 0, 59, 171, 147, 162, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 19, 0,
                 0, 0, 0, 1, 0, 6, 0, 63, 17, 124, 2, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 20, 0, 0, 0, 0, 1, 0, 6, 0, 206, 68,
                 112, 209, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 21, 0, 0, 0, 0, 1, 0, 6, 0, 2, 128, 109, 134, 4, 0, 0, 1, 1, 2,
                 0, 2, 6, 0, 22, 0, 0, 0, 0, 1, 0, 6, 0, 122, 47, 67, 154, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 23, 0, 0, 0, 0,
                 1, 0, 6, 0, 142, 39, 60, 149, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 55, 81, 21, 244, 2, 2, 0, 2, 7, 2, 6, 0, 0,
                 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 16, 0, 0, 0, 0, 1, 0, 6, 0, 125, 249, 252, 16, 4, 0,
                 0, 1, 2, 2, 0, 2, 6, 0, 17, 0, 0, 0, 0, 1, 0, 6, 0, 238, 174, 252, 16, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0,
                 18, 0, 0, 0, 0, 1, 0, 6, 0, 78, 236, 102, 10, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 19, 0, 0, 0, 0, 1, 0, 6, 0,
                 214, 63, 71, 194, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 20, 0, 0, 0, 0, 1, 0, 6, 0, 83, 195, 165, 220, 4, 0, 0,
                 1, 2, 2, 0, 2, 6, 0, 21, 0, 0, 0, 0, 1, 0, 6, 0, 63, 228, 98, 222, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 22, 0,
                 0, 0, 0, 1, 0, 6, 0, 244, 184, 71, 129, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 23, 0, 0, 0, 0, 1, 0, 6, 0, 137,
                 94, 233, 146, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 81, 84, 5, 185, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1,
                 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 16, 0, 0, 0, 0, 1, 0, 6, 0, 187, 47, 57, 191, 3, 0, 0, 1, 1, 2, 0,
                 2, 6, 0, 17, 0, 0, 0, 0, 1, 0, 6, 0, 218, 125, 39, 74, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 18, 0, 0, 0, 0, 1,
                 0, 6, 0, 140, 57, 114, 216, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 19, 0, 0, 0, 0, 1, 0, 6, 0, 139, 242, 239,
                 217, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 20, 0, 0, 0, 0, 1, 0, 6, 0, 162, 141, 161, 189, 3, 0, 0, 1, 1, 2, 0,
                 2, 6, 0, 21, 0, 0, 0, 0, 1, 0, 6, 0, 152, 126, 193, 129, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 22, 0, 0, 0, 0,
                 1, 0, 6, 0, 17, 151, 204, 16, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 23, 0, 0, 0, 0, 1, 0, 6, 0, 216, 9, 101,
                 241, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 253, 72, 174, 221, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0,
                 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 16, 0, 0, 0, 0, 1, 0, 6, 0, 179, 90, 88, 98, 4, 0, 0, 1, 2, 2, 0, 2, 6,
                 0, 17, 0, 0, 0, 0, 1, 0, 6, 0, 61, 143, 238, 41, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 18, 0, 0, 0, 0, 1, 0, 6,
                 0, 26, 175, 126, 73, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 19, 0, 0, 0, 0, 1, 0, 6, 0, 247, 239, 29, 241, 4, 0,
                 0, 1, 1, 2, 0, 2, 6, 0, 20, 0, 0, 0, 0, 1, 0, 6, 0, 224, 84, 249, 106, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0,
                 21, 0, 0, 0, 0, 1, 0, 6, 0, 8, 148, 212, 227, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 22, 0, 0, 0, 0, 1, 0, 6, 0,
                 28, 33, 111, 207, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 23, 0, 0, 0, 0, 1, 0, 6, 0, 238, 154, 1, 9, 4, 0, 0, 1,
                 2, 2, 0, 2, 6, 0, 127, 250, 124, 168, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0,
                 0, 0, 6, 0, 16, 0, 0, 0, 0, 1, 0, 6, 0, 26, 96, 121, 117, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 17, 0, 0, 0, 0,
                 1, 0, 6, 0, 246, 65, 140, 120, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 18, 0, 0, 0, 0, 1, 0, 6, 0, 25, 184, 79,
                 8, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 19, 0, 0, 0, 0, 1, 0, 6, 0, 127, 136, 244, 26, 3, 0, 0, 1, 2, 2, 0, 2,
                 6, 0, 20, 0, 0, 0, 0, 1, 0, 6, 0, 188, 124, 39, 98, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 21, 0, 0, 0, 0, 1, 0,
                 6, 0, 55, 104, 155, 225, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 22, 0, 0, 0, 0, 1, 0, 6, 0, 62, 217, 68, 157, 3,
                 0, 0, 1, 2, 2, 0, 2, 6, 0, 23, 0, 0, 0, 0, 1, 0, 6, 0, 73, 66, 48, 248, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0,
                 103, 103, 147, 22, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 16, 0,
                 0, 0, 0, 1, 0, 6, 0, 162, 74, 94, 245, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 17, 0, 0, 0, 0, 1, 0, 6, 0, 27,
                 50, 185, 234, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 18, 0, 0, 0, 0, 1, 0, 6, 0, 23, 132, 198, 9, 3, 0, 0, 1, 1,
                 2, 0, 2, 6, 0, 19, 0, 0, 0, 0, 1, 0, 6, 0, 124, 9, 32, 95, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 20, 0, 0, 0,
                 0, 1, 0, 6, 0, 67, 44, 71, 91, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 21, 0, 0, 0, 0, 1, 0, 6, 0, 223, 200, 228,
                 230, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 22, 0, 0, 0, 0, 1, 0, 6, 0, 146, 15, 97, 65, 3, 0, 0, 1, 2, 2, 0, 2,
                 6, 0, 23, 0, 0, 0, 0, 1, 0, 6, 0, 130, 191, 202, 58, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 100, 164, 62, 43, 2,
                 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 16, 0, 0, 0, 0, 1, 0, 6, 0,
                 6, 207, 209, 129, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 17, 0, 0, 0, 0, 1, 0, 6, 0, 174, 7, 76, 37, 4, 0, 0, 1,
                 1, 2, 0, 2, 6, 0, 18, 0, 0, 0, 0, 1, 0, 6, 0, 246, 246, 65, 236, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 19, 0,
                 0, 0, 0, 1, 0, 6, 0, 35, 134, 103, 106, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 20, 0, 0, 0, 0, 1, 0, 6, 0, 66,
                 21, 72, 106, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 21, 0, 0, 0, 0, 1, 0, 6, 0, 228, 129, 149, 202, 3, 0, 0, 1,
                 1, 2, 0, 2, 6, 0, 22, 0, 0, 0, 0, 1, 0, 6, 0, 200, 40, 185, 175, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 23, 0,
                 0, 0, 0, 1, 0, 6, 0, 18, 221, 34, 127, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 27, 159, 93, 104, 2, 2, 0, 2, 7,
                 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 24, 0, 0, 0, 0, 1, 0, 6, 0, 27, 42, 27,
                 20, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 25, 0, 0, 0, 0, 1, 0, 6, 0, 233, 176, 18, 31, 4, 0, 0, 1, 1, 2, 0, 2,
                 6, 0, 26, 0, 0, 0, 0, 1, 0, 6, 0, 33, 39, 111, 88, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 27, 0, 0, 0, 0, 1, 0,
                 6, 0, 43, 20, 141, 2, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 28, 0, 0, 0, 0, 1, 0, 6, 0, 38, 129, 13, 18, 3, 0,
                 0, 1, 2, 2, 0, 2, 6, 0, 29, 0, 0, 0, 0, 1, 0, 6, 0, 175, 225, 211, 0, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 30,
                 0, 0, 0, 0, 1, 0, 6, 0, 174, 120, 123, 191, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 31, 0, 0, 0, 0, 1, 0, 6, 0,
                 60, 96, 127, 94, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 126, 12, 40, 136, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6,
                 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 24, 0, 0, 0, 0, 1, 0, 6, 0, 209, 254, 242, 219, 3, 0, 0, 1, 1,
                 2, 0, 2, 6, 0, 25, 0, 0, 0, 0, 1, 0, 6, 0, 157, 142, 60, 116, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 26, 0, 0,
                 0, 0, 1, 0, 6, 0, 114, 233, 45, 88, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 27, 0, 0, 0, 0, 1, 0, 6, 0, 74, 228,
                 38, 7, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 28, 0, 0, 0, 0, 1, 0, 6, 0, 61, 124, 195, 85, 3, 0, 0, 1, 2, 2, 0,
                 2, 6, 0, 29, 0, 0, 0, 0, 1, 0, 6, 0, 153, 111, 221, 75, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 30, 0, 0, 0, 0,
                 1, 0, 6, 0, 112, 46, 208, 151, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 31, 0, 0, 0, 0, 1, 0, 6, 0, 66, 175, 129,
                 136, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 244, 31, 124, 23, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0,
                 0, 6, 2, 0, 0, 0, 0, 6, 0, 24, 0, 0, 0, 0, 1, 0, 6, 0, 214, 49, 104, 96, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0,
                 25, 0, 0, 0, 0, 1, 0, 6, 0, 218, 149, 236, 205, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 26, 0, 0, 0, 0, 1, 0, 6,
                 0, 69, 35, 34, 130, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 27, 0, 0, 0, 0, 1, 0, 6, 0, 175, 118, 62, 193, 3, 0,
                 0, 1, 1, 2, 0, 2, 6, 0, 28, 0, 0, 0, 0, 1, 0, 6, 0, 44, 186, 89, 95, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 29,
                 0, 0, 0, 0, 1, 0, 6, 0, 253, 228, 104, 220, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 30, 0, 0, 0, 0, 1, 0, 6, 0,
                 89, 55, 208, 100, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 31, 0, 0, 0, 0, 1, 0, 6, 0, 179, 36, 204, 33, 3, 0, 0,
                 1, 1, 2, 0, 2, 6, 0, 89, 254, 13, 86, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0,
                 0, 0, 6, 0, 24, 0, 0, 0, 0, 1, 0, 6, 0, 177, 203, 255, 140, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 25, 0, 0, 0,
                 0, 1, 0, 6, 0, 126, 218, 80, 151, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 26, 0, 0, 0, 0, 1, 0, 6, 0, 221, 68,
                 16, 163, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 27, 0, 0, 0, 0, 1, 0, 6, 0, 31, 211, 128, 63, 4, 0, 0, 1, 1, 2,
                 0, 2, 6, 0, 28, 0, 0, 0, 0, 1, 0, 6, 0, 64, 105, 21, 163, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 29, 0, 0, 0, 0,
                 1, 0, 6, 0, 101, 202, 155, 104, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 30, 0, 0, 0, 0, 1, 0, 6, 0, 243, 216, 66,
                 246, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 31, 0, 0, 0, 0, 1, 0, 6, 0, 228, 196, 56, 52, 4, 0, 0, 1, 2, 2, 0,
                 2, 6, 0, 88, 249, 55, 224, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6,
                 0, 24, 0, 0, 0, 0, 1, 0, 6, 0, 138, 173, 204, 243, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 25, 0, 0, 0, 0, 1, 0,
                 6, 0, 17, 217, 68, 243, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 26, 0, 0, 0, 0, 1, 0, 6, 0, 173, 149, 231, 70, 3,
                 0, 0, 1, 1, 2, 0, 2, 6, 0, 27, 0, 0, 0, 0, 1, 0, 6, 0, 233, 63, 176, 203, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0,
                 28, 0, 0, 0, 0, 1, 0, 6, 0, 222, 43, 117, 47, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 29, 0, 0, 0, 0, 1, 0, 6, 0,
                 194, 163, 187, 44, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 30, 0, 0, 0, 0, 1, 0, 6, 0, 89, 185, 35, 87, 3, 0, 0,
                 1, 2, 2, 0, 2, 6, 0, 31, 0, 0, 0, 0, 1, 0, 6, 0, 204, 57, 98, 118, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 249,
                 222, 85, 187, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 24, 0, 0,
                 0, 0, 1, 0, 6, 0, 142, 10, 74, 193, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 25, 0, 0, 0, 0, 1, 0, 6, 0, 18, 219,
                 120, 0, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 26, 0, 0, 0, 0, 1, 0, 6, 0, 152, 182, 253, 1, 4, 0, 0, 1, 2, 2,
                 0, 2, 6, 0, 27, 0, 0, 0, 0, 1, 0, 6, 0, 128, 33, 77, 29, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 28, 0, 0, 0, 0,
                 1, 0, 6, 0, 61, 7, 153, 108, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 29, 0, 0, 0, 0, 1, 0, 6, 0, 66, 47, 157,
                 173, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 30, 0, 0, 0, 0, 1, 0, 6, 0, 42, 169, 50, 139, 4, 0, 0, 1, 1, 2, 0,
                 2, 6, 0, 31, 0, 0, 0, 0, 1, 0, 6, 0, 29, 29, 207, 161, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 231, 156, 91, 105,
                 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 24, 0, 0, 0, 0, 1, 0, 6,
                 0, 187, 235, 35, 69, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 25, 0, 0, 0, 0, 1, 0, 6, 0, 247, 3, 175, 65, 3, 0,
                 0, 1, 1, 2, 0, 2, 6, 0, 26, 0, 0, 0, 0, 1, 0, 6, 0, 15, 91, 208, 113, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 27,
                 0, 0, 0, 0, 1, 0, 6, 0, 184, 36, 148, 90, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 28, 0, 0, 0, 0, 1, 0, 6, 0,
                 213, 216, 108, 152, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 29, 0, 0, 0, 0, 1, 0, 6, 0, 234, 113, 9, 18, 3, 0, 0,
                 1, 1, 2, 0, 2, 6, 0, 30, 0, 0, 0, 0, 1, 0, 6, 0, 226, 154, 156, 136, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 31,
                 0, 0, 0, 0, 1, 0, 6, 0, 144, 75, 186, 135, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 140, 182, 225, 198, 2, 2, 0,
                 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 24, 0, 0, 0, 0, 1, 0, 6, 0, 100,
                 154, 110, 17, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 25, 0, 0, 0, 0, 1, 0, 6, 0, 103, 58, 98, 72, 4, 0, 0, 1, 2,
                 2, 0, 2, 6, 0, 26, 0, 0, 0, 0, 1, 0, 6, 0, 188, 78, 8, 136, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 27, 0, 0, 0,
                 0, 1, 0, 6, 0, 54, 220, 165, 244, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 28, 0, 0, 0, 0, 1, 0, 6, 0, 76, 59,
                 209, 74, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 29, 0, 0, 0, 0, 1, 0, 6, 0, 212, 198, 119, 145, 4, 0, 0, 1, 2,
                 2, 0, 2, 6, 0, 30, 0, 0, 0, 0, 1, 0, 6, 0, 213, 136, 144, 31, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 31, 0, 0,
                 0, 0, 1, 0, 6, 0, 135, 48, 182, 102, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 74, 148, 163, 228, 2, 2, 0, 2, 7, 2,
                 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 32, 0, 0, 0, 0, 1, 0, 6, 0, 190, 222, 66,
                 143, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 33, 0, 0, 0, 0, 1, 0, 6, 0, 188, 30, 210, 161, 4, 0, 0, 1, 2, 2, 0,
                 2, 6, 0, 34, 0, 0, 0, 0, 1, 0, 6, 0, 37, 144, 207, 55, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 35, 0, 0, 0, 0, 1,
                 0, 6, 0, 160, 162, 215, 177, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 36, 0, 0, 0, 0, 1, 0, 6, 0, 192, 26, 237,
                 166, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 37, 0, 0, 0, 0, 1, 0, 6, 0, 36, 255, 216, 76, 3, 0, 0, 1, 2, 2, 0,
                 2, 6, 0, 38, 0, 0, 0, 0, 1, 0, 6, 0, 176, 136, 106, 13, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 39, 0, 0, 0, 0,
                 1, 0, 6, 0, 101, 165, 251, 90, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 176, 221, 231, 214, 2, 2, 0, 2, 7, 2, 6,
                 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 32, 0, 0, 0, 0, 1, 0, 6, 0, 8, 192, 119, 227,
                 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 33, 0, 0, 0, 0, 1, 0, 6, 0, 50, 116, 216, 175, 3, 0, 0, 1, 1, 2, 0, 2, 6,
                 0, 34, 0, 0, 0, 0, 1, 0, 6, 0, 161, 7, 165, 1, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 35, 0, 0, 0, 0, 1, 0, 6,
                 0, 253, 52, 188, 29, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 36, 0, 0, 0, 0, 1, 0, 6, 0, 206, 163, 134, 223, 3,
                 0, 0, 1, 2, 2, 0, 2, 6, 0, 37, 0, 0, 0, 0, 1, 0, 6, 0, 33, 167, 3, 36, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0,
                 38, 0, 0, 0, 0, 1, 0, 6, 0, 174, 129, 255, 26, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 39, 0, 0, 0, 0, 1, 0, 6,
                 0, 73, 127, 98, 183, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 150, 187, 29, 212, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0,
                 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 32, 0, 0, 0, 0, 1, 0, 6, 0, 44, 217, 18, 43, 4, 0, 0, 1,
                 2, 2, 0, 2, 6, 0, 33, 0, 0, 0, 0, 1, 0, 6, 0, 25, 183, 227, 165, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 34, 0,
                 0, 0, 0, 1, 0, 6, 0, 169, 200, 129, 114, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 35, 0, 0, 0, 0, 1, 0, 6, 0, 214,
                 210, 20, 33, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 36, 0, 0, 0, 0, 1, 0, 6, 0, 228, 49, 178, 113, 3, 0, 0, 1,
                 1, 2, 0, 2, 6, 0, 37, 0, 0, 0, 0, 1, 0, 6, 0, 12, 244, 98, 109, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 38, 0, 0,
                 0, 0, 1, 0, 6, 0, 107, 33, 211, 186, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 39, 0, 0, 0, 0, 1, 0, 6, 0, 212, 49,
                 116, 112, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 224, 156, 20, 1, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0,
                 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 32, 0, 0, 0, 0, 1, 0, 6, 0, 44, 5, 228, 231, 3, 0, 0, 1, 1, 2, 0, 2,
                 6, 0, 33, 0, 0, 0, 0, 1, 0, 6, 0, 103, 103, 233, 59, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 34, 0, 0, 0, 0, 1,
                 0, 6, 0, 68, 158, 21, 93, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 35, 0, 0, 0, 0, 1, 0, 6, 0, 249, 39, 170, 59,
                 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 36, 0, 0, 0, 0, 1, 0, 6, 0, 94, 241, 117, 180, 4, 0, 0, 1, 1, 2, 0, 2, 6,
                 0, 37, 0, 0, 0, 0, 1, 0, 6, 0, 21, 177, 83, 105, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 38, 0, 0, 0, 0, 1, 0, 6,
                 0, 191, 233, 194, 161, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 39, 0, 0, 0, 0, 1, 0, 6, 0, 245, 241, 125, 125, 4,
                 0, 0, 1, 2, 2, 0, 2, 6, 0, 84, 8, 186, 167, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2,
                 0, 0, 0, 0, 6, 0, 32, 0, 0, 0, 0, 1, 0, 6, 0, 12, 205, 37, 55, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 33, 0, 0,
                 0, 0, 1, 0, 6, 0, 164, 251, 207, 10, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 34, 0, 0, 0, 0, 1, 0, 6, 0, 35, 24,
                 177, 41, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 35, 0, 0, 0, 0, 1, 0, 6, 0, 205, 7, 49, 74, 4, 0, 0, 1, 1, 2, 0,
                 2, 6, 0, 36, 0, 0, 0, 0, 1, 0, 6, 0, 102, 15, 78, 16, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 37, 0, 0, 0, 0, 1,
                 0, 6, 0, 96, 69, 126, 248, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 38, 0, 0, 0, 0, 1, 0, 6, 0, 233, 4, 38, 116,
                 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 39, 0, 0, 0, 0, 1, 0, 6, 0, 56, 216, 186, 155, 3, 0, 0, 1, 2, 2, 0, 2, 6,
                 0, 191, 160, 234, 29, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 32,
                 0, 0, 0, 0, 1, 0, 6, 0, 36, 110, 119, 203, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 33, 0, 0, 0, 0, 1, 0, 6, 0,
                 121, 225, 48, 137, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 34, 0, 0, 0, 0, 1, 0, 6, 0, 90, 128, 104, 65, 4, 0, 0,
                 1, 2, 2, 0, 2, 6, 0, 35, 0, 0, 0, 0, 1, 0, 6, 0, 221, 137, 172, 48, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 36,
                 0, 0, 0, 0, 1, 0, 6, 0, 237, 214, 167, 53, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 37, 0, 0, 0, 0, 1, 0, 6, 0,
                 179, 193, 88, 214, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 38, 0, 0, 0, 0, 1, 0, 6, 0, 68, 6, 52, 172, 3, 0, 0,
                 1, 2, 2, 0, 2, 6, 0, 39, 0, 0, 0, 0, 1, 0, 6, 0, 19, 168, 83, 132, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 39,
                 70, 221, 13, 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 32, 0, 0, 0,
                 0, 1, 0, 6, 0, 144, 246, 105, 123, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 33, 0, 0, 0, 0, 1, 0, 6, 0, 205, 154,
                 100, 11, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 34, 0, 0, 0, 0, 1, 0, 6, 0, 95, 140, 91, 2, 4, 0, 0, 1, 1, 2, 0,
                 2, 6, 0, 35, 0, 0, 0, 0, 1, 0, 6, 0, 187, 195, 127, 185, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 36, 0, 0, 0, 0,
                 1, 0, 6, 0, 17, 72, 202, 234, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 37, 0, 0, 0, 0, 1, 0, 6, 0, 221, 39, 228,
                 117, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 38, 0, 0, 0, 0, 1, 0, 6, 0, 210, 249, 234, 21, 4, 0, 0, 1, 1, 2, 0,
                 2, 6, 0, 39, 0, 0, 0, 0, 1, 0, 6, 0, 211, 117, 70, 25, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 223, 134, 167, 99,
                 2, 2, 0, 2, 7, 2, 6, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 6, 2, 0, 0, 0, 0, 6, 0, 32, 0, 0, 0, 0, 1, 0, 6,
                 0, 18, 117, 94, 226, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0, 33, 0, 0, 0, 0, 1, 0, 6, 0, 108, 175, 221, 156, 3,
                 0, 0, 1, 2, 2, 0, 2, 6, 0, 34, 0, 0, 0, 0, 1, 0, 6, 0, 225, 107, 27, 143, 3, 0, 0, 1, 2, 2, 0, 2, 6, 0,
                 35, 0, 0, 0, 0, 1, 0, 6, 0, 146, 154, 123, 245, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 36, 0, 0, 0, 0, 1, 0, 6,
                 0, 145, 149, 113, 125, 3, 0, 0, 1, 1, 2, 0, 2, 6, 0, 37, 0, 0, 0, 0, 1, 0, 6, 0, 86, 98, 40, 215, 3, 0,
                 0, 1, 1, 2, 0, 2, 6, 0, 38, 0, 0, 0, 0, 1, 0, 6, 0, 205, 43, 209, 81, 4, 0, 0, 1, 2, 2, 0, 2, 6, 0, 39,
                 0, 0, 0, 0, 1, 0, 6, 0, 94, 40, 155, 142, 4, 0, 0, 1, 1, 2, 0, 2, 6, 0, 147, 117, 143, 66, 2, 2, 0, 2,
                 7, 2, 8, 0, 0, 0])

solver = Solver()
input_str = [0 for _ in range(40)]
for i in range(40):
    input_str[i] = BitVec("input_%d" % i, 8)
    solver.add(input_str[i] <= 127)
    solver.add(input_str[i] >= 0)

stack = [0, 0, 0]
ptr = 0
while True:
    while True:
        while True:
            while True:
                while True:
                    while True:
                        while True:
                            while True:
                                while op_code[ptr] == 0:
                                    stack[op_code[ptr + 1]] = (16975111 * (op_code[ptr + 1] + 127)) ^ input_str[
                                        (16975111 * (op_code[ptr + 2] + 127)) ^ stack[op_code[ptr + 2]]]
                                    ptr += 3
                                if op_code[ptr] != 1:
                                    break
                                stack[op_code[ptr + 1]] = (16975111 * (op_code[ptr + 1] + 127)) ^ (
                                        (stack[op_code[ptr + 3]] ^ (16975111 * (op_code[ptr + 3] + 127)))
                                        + ((16975111 * (op_code[ptr + 2] + 127)) ^ stack[op_code[ptr + 2]]))
                                ptr += 4
                            if op_code[ptr] != 2:
                                break
                            stack[op_code[ptr + 1]] = (16975111 * (op_code[ptr + 1] + 127)) ^ (
                                    (stack[op_code[ptr + 3]] ^ (16975111 * (op_code[ptr + 3] + 127)))
                                    - ((16975111 * (op_code[ptr + 2] + 127)) ^ stack[op_code[ptr + 2]]))
                            ptr += 4
                        if op_code[ptr] != 3:
                            break
                        stack[op_code[ptr + 1]] = (16975111 * (op_code[ptr + 1] + 127)) ^ (
                                (stack[op_code[ptr + 3]] ^ (16975111 * (op_code[ptr + 3] + 127)))
                                * ((16975111 * (op_code[ptr + 2] + 127)) ^ stack[op_code[ptr + 2]]))
                        ptr += 4
                    if op_code[ptr] != 4:
                        break
                    stack[op_code[ptr + 1]] = (16975111 * (op_code[ptr + 1] + 127)) ^ stack[op_code[ptr + 3]] ^ (
                            0x1030507 * (op_code[ptr + 3] + 127)) ^ (16975111 * (op_code[ptr + 2] + 127)) ^ stack[
                                                 op_code[ptr + 2]]
                    ptr += 4
                if op_code[ptr] != 5:
                    break
                stack[op_code[ptr + 1]] = (16975111 * (op_code[ptr + 1] + 127)) ^ (
                        stack[op_code[ptr + 3]] ^ (0x1030507 * (op_code[ptr + 3] + 127))) & (
                                                  (0x1030507 * (op_code[ptr + 2] + 127)) ^ stack[op_code[ptr + 2]])
                ptr += 4
            if op_code[ptr] != 6:
                break
            stack[op_code[ptr + 1]] = (16975111 * (op_code[ptr + 1] + 127)) ^ u32(op_code[ptr + 2: ptr + 6])
            ptr += 6
        if op_code[ptr] != 7:
            break
        solver.add(stack[op_code[ptr + 1]] == 16975111 * (op_code[ptr + 1] + 127)) 
        ptr += 2
    if op_code[ptr] == 8:
        break

print(solver.check())
m = solver.model()
output_str = 'flag{'
for i in range(40):
    output_str += chr(m.eval(input_str[i]).as_long())
print(output_str)

直接成功

flag{repairing_control_flow_is_interesting}
分享到: QQ空间 新浪微博 微信 QQ facebook twitter
|推荐阅读
|发表评论
|评论列表
加载更多