Ideone.com

fork download

copy

import math
import random
import time
 
 
def play(gameState, memo={}):
    start_time = time.process_time()
    turn = gameState.currentTurn
    maxT = gameState.maxTurn
 
    INF = 10 ** 9
    WIN = 100000
    PLYLIM = 44
 
    W = gameState.width
    H = gameState.height
    goal_mode = gameState.goalMode
 
    walls_xy = frozenset((w.x, w.y) for w in gameState.walls)
    goals0_xy = frozenset((g.x, g.y) for g in gameState.goals) or frozenset([(W, H)])
    goals1_xy = frozenset((g.x, g.y) for g in gameState.enemyGoals) or frozenset([(1, 1)])
 
    # Bảng khắc chế: 0=R (Búa), 1=P (Bao), 2=S (Kéo)
    BT = ((False, False, True), (True, False, False), (False, True, False))
    PRED = (1, 2, 0)
    PREY = (2, 0, 1)
 
    ELIM1 = 65
    ELIM2 = 0
 
    # Nếu trận trước bị reset giữa chừng thì xóa cache cũ
    if turn <= 1 and 'tabs' in memo:
        memo.clear()
 
    map_sig = (W, H, walls_xy, goals0_xy, goals1_xy, goal_mode)
    tabs = memo.get('tabs')
 
    # Khởi tạo bảng tra cứu bản đồ (chạy 1 lần ở lượt đầu hoặc khi đổi map)
    if tabs is None or memo.get('map_sig') != map_sig:
        memo['map_sig'] = map_sig
        memo['tt'] = {}
        memo['hist'] = None
        memo['seen'] = {}
        memo['cfg'] = {}
 
        STRIDE = W + 2
        SIZE = (W + 2) * (H + 2)
        OFFS = (STRIDE + 1, STRIDE, 1, STRIDE - 1, -(STRIDE - 1), -1, -STRIDE, -(STRIDE + 1))
        DIRN = {
            STRIDE - 1: 1,
            STRIDE: 2,
            STRIDE + 1: 3,
            1: 4,
            -(STRIDE - 1): 5,
            -STRIDE: 6,
            -(STRIDE + 1): 7,
            -1: 8,
        }
 
        wall_set = frozenset(
            y * STRIDE + x for (x, y) in walls_xy if 1 <= x <= W and 1 <= y <= H
        )
        cells = [
            y * STRIDE + x
            for y in range(1, H + 1)
            for x in range(1, W + 1)
            if (y * STRIDE + x) not in wall_set
        ]
        valid_set = set(cells)
 
        GOAL0 = frozenset(y * STRIDE + x for (x, y) in goals0_xy if (y * STRIDE + x) in valid_set)
        GOAL1 = frozenset(y * STRIDE + x for (x, y) in goals1_xy if (y * STRIDE + x) in valid_set)
        GOAL = (GOAL0, GOAL1)
 
        nb0_set = {g + off for g in GOAL0 for off in OFFS if (g + off) in valid_set and (g + off) not in GOAL0}
        nb1_set = {g + off for g in GOAL1 for off in OFFS if (g + off) in valid_set and (g + off) not in GOAL1}
        NB = (tuple(nb0_set), tuple(nb1_set))
        DEF_SQ = (GOAL0 | nb0_set, GOAL1 | nb1_set)
 
        MAX_D = W + H + 12
 
        # BFS tính khoảng cách ngắn nhất né tường tới tập ô đích của ta (D0) và địch (D1)
        D0 = [MAX_D] * SIZE
        bfs_q = list(GOAL0)
        for g in GOAL0:
            D0[g] = 0
        head = 0
        while head < len(bfs_q):
            u = bfs_q[head]
            head += 1
            du = D0[u] + 1
            for off in OFFS:
                v = u + off
                if v in valid_set and du < D0[v]:
                    D0[v] = du
                    bfs_q.append(v)
 
        D1 = [MAX_D] * SIZE
        bfs_q = list(GOAL1)
        for g in GOAL1:
            D1[g] = 0
        head = 0
        while head < len(bfs_q):
            u = bfs_q[head]
            head += 1
            du = D1[u] + 1
            for off in OFFS:
                v = u + off
                if v in valid_set and du < D1[v]:
                    D1[v] = du
                    bfs_q.append(v)
 
        # BFS tính khoảng cách thực tế giữa mọi cặp ô hợp lệ để săn đuổi vòng qua vật cản
        DT = [[MAX_D] * SIZE for _ in range(SIZE)]
        MDT = [[MAX_D * 2] * SIZE for _ in range(SIZE)]
        for src in cells:
            row = DT[src]
            mrow = MDT[src]
            row[src] = 0
            mrow[src] = 0
            bfs_q = [src]
            head = 0
            while head < len(bfs_q):
                u = bfs_q[head]
                head += 1
                du = row[u] + 1
                for off in OFFS:
                    v = u + off
                    if v in valid_set and du < row[v]:
                        row[v] = du
                        mrow[v] = du * 2
                        bfs_q.append(v)
 
        max_d0 = max((D0[a] for a in cells if D0[a] < MAX_D), default=1)
        max_d1 = max((D1[a] for a in cells if D1[a] < MAX_D), default=1)
        ADV0 = [0] * SIZE
        ADV1 = [0] * SIZE
        CENTER = [0] * SIZE
        mid_x = (W + 1) * 0.5
        mid_y = (H + 1) * 0.5
        for a in cells:
            x = a % STRIDE
            y = a // STRIDE
            ADV0[a] = max(0, max_d0 - D0[a])
            ADV1[a] = max(0, max_d1 - D1[a])
            cx = abs(x - mid_x) / max(1.0, W / 9.0)
            cy = abs(y - mid_y) / max(1.0, H / 9.0)
            CENTER[a] = max(0, int(4 - max(cx, cy)))
 
        # Bảng nước đi hợp lệ sắp xếp sẵn theo độ giảm khoảng cách tới đích
        MTAB0 = [() for _ in range(SIZE)]
        MTAB1 = [() for _ in range(SIZE)]
        for a in cells:
            m0 = []
            m1 = []
            for off in OFFS:
                q = a + off
                if q in valid_set:
                    h_ix = a * SIZE + q
                    fw0_b = (D0[a] - D0[q]) * 2
                    fw1_b = (D1[a] - D1[q]) * 2
                    m0.append((q, fw0_b, h_ix, 1 if q in nb0_set else 0))
                    m1.append((q, fw1_b, h_ix, 1 if q in nb1_set else 0))
            m0.sort(key=lambda item: item[1], reverse=True)
            m1.sort(key=lambda item: item[1], reverse=True)
            MTAB0[a] = tuple(m0)
            MTAB1[a] = tuple(m1)
        MTAB = (tuple(MTAB0), tuple(MTAB1))
 
        # Bảng điểm thưởng khoảng cách tới đích (tự co giãn theo kích thước map)
        RT = tuple([0] + [int(950 * (0.60 ** (d - 1))) for d in range(1, MAX_D + 1)])
        UNSTOP_RT = tuple([0] + [int(1750 * (0.64 ** (d - 1))) for d in range(1, MAX_D + 1)])
 
        rz = random.Random(20260402)
        Z = tuple(tuple(rz.getrandbits(52) for _ in range(SIZE)) for _ in range(48))
        ZS = rz.getrandbits(52)
 
        tabs = (
            STRIDE, SIZE, MAX_D, OFFS, DIRN, wall_set, GOAL, NB, DEF_SQ,
            DT, MDT, ADV0, ADV1, D0, D1, CENTER, MTAB, RT, UNSTOP_RT, Z, ZS
        )
        memo['tabs'] = tabs
 
    (
        STRIDE, SIZE, MAX_D, OFFS, DIRN, wall_set, GOAL, NB, DEF_SQ,
        DT, MDT, ADV0, ADV1, D0, D1, CENTER, MTAB, RT, UNSTOP_RT, Z, ZS
    ) = tabs
 
    # Quản lý ngân sách CPU: tổng 180s/ván, tối đa 1s/nước (chốt ở 0.82s để an toàn)
    used = memo.get('used', 0.0)
    left = max(1, (maxT - turn) // 2 + 1)
    if turn <= 1:
        budget = 0.82
    else:
        budget = min(0.82, max(0.04, (160.0 - used) / min(left, 150)))
    deadline = start_time + budget
 
    # Dựng bàn cờ 1 chiều: ngoài biên và ô tường đen mang giá trị -1
    board = [-1] * SIZE
    for yy in range(1, H + 1):
        base_y = yy * STRIDE
        for xx in range(1, W + 1):
            pos = base_y + xx
            if pos not in wall_set:
                board[pos] = 0
 
    # Đánh chỉ số động cho quân hai bên (hỗ trợ map có số quân khác 9)
    ally_list = list(gameState.ally)
    opp_list = list(gameState.opponent)
    na_init = len(ally_list)
    nb_init = len(opp_list)
 
    ALLY_LO = 1
    ALLY_HI = na_init
    OPP_LO = na_init + 2
    OPP_HI = OPP_LO + nb_init - 1
    LO = (ALLY_LO, OPP_LO)
    HI = (ALLY_HI, OPP_HI)
 
    slot_cap = max(48, OPP_HI + 2)
    if len(Z) < slot_cap:
        rz = random.Random(20260402)
        Z = tuple(tuple(rz.getrandbits(52) for _ in range(SIZE)) for _ in range(slot_cap))
 
    tp = [0] * slot_cap
    ps = [-1] * slot_cap
    pid_of = [0] * slot_cap
    TI = {'R': 0, 'P': 1, 'S': 2}
    cnt = [0, 0]
 
    for idx_a, p in enumerate(ally_list):
        c = ALLY_LO + idx_a
        pid_of[c] = p.pid
        tp[c] = TI[p.Type]
        pos = p.y * STRIDE + p.x
        ps[c] = pos
        board[pos] = c
        cnt[0] += 1
 
    for idx_b, p in enumerate(opp_list):
        c = OPP_LO + idx_b
        pid_of[c] = p.pid
        tp[c] = TI[p.Type]
        pos = p.y * STRIDE + p.x
        ps[c] = pos
        board[pos] = c
        cnt[1] += 1
 
    tt = memo.get('tt')
    if tt is None or len(tt) > 120000:
        tt = {}
        memo['tt'] = tt
 
    hist_len = SIZE * SIZE
    HIST = memo.get('hist')
    if HIST is None or len(HIST) != hist_len:
        HIST = [0] * hist_len
        memo['hist'] = HIST
    else:
        for i in range(hist_len):
            if HIST[i]:
                HIST[i] >>= 1
 
    KILLER = [None] * 64
    nodes = [0]
    abort = [False]
 
    total = cnt[0] + cnt[1]
    if memo.get('prev_total') != total:
        memo['prev_total'] = total
        memo['capt_turn'] = turn
        memo['cfg'] = {}
    stag = (turn - memo.get('capt_turn', turn)) // 2
    ahead = cnt[0] > cnt[1]
    behind = cnt[0] < cnt[1]
 
    K = 5 + min(8, turn // 25)
    if not behind and stag > 16:
        K += min(7, (stag - 16) // 6)
    if behind:
        HW = 3
    elif stag > 16:
        HW = 11
    else:
        HW = 6
    if ahead and stag > 26:
        DP = (0, 220, 120, 55)
    else:
        DP = (0, 330, 175, 80)
 
    # Phân vai chiến thuật: DEFENDER (chặn đích nhà), RUNNER (đột phá), HUNTER (săn quân)
    roles = {}
    e_types_alive = [0, 0, 0]
    e_near_home = []
    e_near_away = [0, 0, 0]
    for c in range(OPP_LO, OPP_HI + 1):
        q = ps[c]
        if q >= 0:
            u = tp[c]
            e_types_alive[u] += 1
            if D1[q] <= 4:
                e_near_home.append((D1[q], q, u))
            if D0[q] <= 2:
                e_near_away[u] += 1
    e_near_home.sort()
 
    def_assigned = set()
    for d_h, q_h, u_h in e_near_home:
        need_t = PRED[u_h]
        best_c = 0
        best_d = 999
        for c in range(ALLY_LO, ALLY_HI + 1):
            p = ps[c]
            if p >= 0 and tp[c] == need_t and c not in def_assigned:
                d_c = D1[p]
                if d_c < best_d:
                    best_d = d_c
                    best_c = c
        if best_c:
            roles[best_c] = 'DEFENDER'
            def_assigned.add(best_c)
 
    if not def_assigned:
        best_c = 0
        best_d = 999
        for c in range(ALLY_LO, ALLY_HI + 1):
            p = ps[c]
            if p >= 0 and e_types_alive[PREY[tp[c]]] > 0:
                d_c = D1[p]
                if d_c < best_d:
                    best_d = d_c
                    best_c = c
        if best_c and best_d <= 3:
            roles[best_c] = 'DEFENDER'
            def_assigned.add(best_c)
 
    runner_cands = []
    for c in range(ALLY_LO, ALLY_HI + 1):
        p = ps[c]
        if p >= 0 and c not in def_assigned:
            t = tp[c]
            imm = 1 if e_types_alive[PRED[t]] == 0 else 0
            brk = 1 if e_near_away[PREY[t]] > 0 else 0
            runner_cands.append((D0[p] - 2 * imm - brk, -ADV0[p], c))
    runner_cands.sort()
    num_runners = max(2, len(GOAL[0])) if goal_mode == 1 else 2
    for idx_r in range(min(num_runners, len(runner_cands))):
        roles[runner_cands[idx_r][2]] = 'RUNNER'
    for c in range(ALLY_LO, ALLY_HI + 1):
        if ps[c] >= 0 and c not in roles:
            roles[c] = 'HUNTER'
 
    # Kiểm tra phe s có thể chạm đích thắng ngay trong 1 nước đi không
    def wins_now(s):
        lo = LO[s]
        hi = HI[s]
        gset = GOAL[s]
        if goal_mode == 0:
            for g in gset:
                v0 = board[g]
                if lo <= v0 <= hi:
                    return True
                if v0 == 0:
                    for off in OFFS:
                        v = board[g + off]
                        if lo <= v <= hi:
                            return True
                else:
                    t = tp[v0]
                    for off in OFFS:
                        v = board[g + off]
                        if lo <= v <= hi and BT[tp[v]][t]:
                            return True
            return False
        else:
            missing = [g for g in gset if not (lo <= board[g] <= hi)]
            if not missing:
                return True
            if len(missing) > 1:
                return False
            g = missing[0]
            v0 = board[g]
            for off in OFFS:
                src = g + off
                v = board[src]
                if lo <= v <= hi and src not in gset:
                    if v0 == 0 or BT[tp[v]][tp[v0]]:
                        return True
            return False
 
    # Sinh nước đi hợp lệ: mode=0 (tất cả), mode=1 (chỉ ăn quân), mode=2 (ăn quân + áp sát đích)
    def gen(s, mode):
        res = []
        lo = LO[s]
        hi = HI[s]
        elo = LO[1 - s]
        ehi = HI[1 - s]
        mtab = MTAB[s]
        gset = GOAL[s]
        egset = GOAL[1 - s]
        for c in range(lo, hi + 1):
            p = ps[c]
            if p < 0:
                continue
            t = tp[c]
            bt = BT[t]
            on_goal = (goal_mode == 1 and p in gset)
            for q, fw_b, h_ix, is_nb in mtab[p]:
                v = board[q]
                if v == 0:
                    if mode == 0:
                        h = HIST[h_ix]
                        pen_leave = -35 if (on_goal and q not in gset) else 0
                        res.append((fw_b + pen_leave + (h if h < 72 else 72), c, p, q, 0))
                    elif mode == 2 and is_nb:
                        for off in OFFS:
                            gq = q + off
                            if gq in gset:
                                vg = board[gq]
                                if vg == 0 or (elo <= vg <= ehi and bt[tp[vg]]):
                                    res.append((820 + fw_b, c, p, q, 0))
                                    break
                elif elo <= v <= ehi:
                    if bt[tp[v]]:
                        bonus = 90 if (q in egset or D1[q] <= 2) else 0
                        res.append((1050 + fw_b + bonus, c, p, q, v))
        return res
 
    # Hàm lượng giá thế cờ tĩnh từ góc nhìn phe s
    def evaluate_raw(s):
        A_p = []
        A_t = []
        B_p = []
        B_t = []
        cA0 = cA1 = cA2 = 0
        cB0 = cB1 = cB2 = 0
        for c in range(ALLY_LO, ALLY_HI + 1):
            p = ps[c]
            if p >= 0:
                t = tp[c]
                A_p.append(p)
                A_t.append(t)
                if t == 0:
                    cA0 += 1
                elif t == 1:
                    cA1 += 1
                else:
                    cA2 += 1
        for c in range(OPP_LO, OPP_HI + 1):
            p = ps[c]
            if p >= 0:
                t = tp[c]
                B_p.append(p)
                B_t.append(t)
                if t == 0:
                    cB0 += 1
                elif t == 1:
                    cB1 += 1
                else:
                    cB2 += 1
 
        na = len(A_p)
        nb = len(B_p)
        if na == 0:
            return -WIN + 100 if s == 0 else WIN - 100
        if nb == 0:
            return WIN - 100 if s == 0 else -WIN + 100
 
        cA = (cA0, cA1, cA2)
        cB = (cB0, cB1, cB2)
 
        # Hơn quân và lợi thế tuyệt đối khi địch mất sạch loại quân khắc chế
        v = 1050 * (na - nb) + 3200 * (na - nb) // (na + nb)
 
        for t in (0, 1, 2):
            pred = PRED[t]
            prey = PREY[t]
            ca = cA[t]
            cb = cB[t]
            if ca:
                if cB[pred] == 0:
                    v += ca * (500 if cB[t] == 0 else 360)
                elif cB[pred] == 1 and cA[prey] > 0:
                    v += ca * ELIM1
                elif ELIM2 and cB[pred] == 2 and cA[prey] >= 2:
                    v += ca * ELIM2
                v += ca * (80 * cB[prey] if cB[prey] else -50)
            if cb:
                if cA[pred] == 0:
                    v -= cb * (500 if cA[t] == 0 else 360)
                elif cA[pred] == 1 and cB[prey] > 0:
                    v -= cb * ELIM1
                elif ELIM2 and cA[pred] == 2 and cB[prey] >= 2:
                    v -= cb * ELIM2
                v -= cb * (80 * cA[prey] if cA[prey] else -50)
 
        # Điểm chiếm đóng đồng thời khi bản đồ bật goalMode == 1
        if goal_mode == 1:
            occ0 = 0
            for g in GOAL[0]:
                if ALLY_LO <= board[g] <= ALLY_HI:
                    occ0 += 1
            occ1 = 0
            for g in GOAL[1]:
                if OPP_LO <= board[g] <= OPP_HI:
                    occ1 += 1
            if occ0 == len(GOAL[0]):
                return WIN - 50 if s == 0 else -WIN + 50
            if occ1 == len(GOAL[1]):
                return -WIN + 50 if s == 0 else WIN - 50
            v += 900 * (occ0 - occ1)
 
        ha = [MAX_D] * na
        pa = [MAX_D] * na
        ma = [MAX_D * 2] * na
        inta = [999] * na
        hb = [MAX_D] * nb
        pb = [MAX_D] * nb
        mb = [MAX_D * 2] * nb
        intb = [999] * nb
 
        for i in range(na):
            p = A_p[i]
            t = A_t[i]
            d0p = D0[p]
            row = DT[p]
            mrow = MDT[p]
            bt = BT[t]
            for j in range(nb):
                q = B_p[j]
                u = B_t[j]
                d0q = D0[q]
                d1q = D1[q]
                if u == t:
                    if d0q <= d0p and d0q < inta[i]:
                        inta[i] = d0q
                    if D1[p] <= d1q and D1[p] < intb[j]:
                        intb[j] = D1[p]
                    continue
                d = row[q]
                md = mrow[q]
                if bt[u]:
                    if d < pa[i]:
                        pa[i] = d
                    if md < ma[i]:
                        ma[i] = md
                    if d < hb[j]:
                        hb[j] = d
                    if D1[p] <= d1q + 1 and D1[p] < intb[j]:
                        intb[j] = D1[p]
                else:
                    if d < ha[i]:
                        ha[i] = d
                    if d < pb[j]:
                        pb[j] = d
                    if md < mb[j]:
                        mb[j] = md
                    if d0q <= d0p + 1 and d0q < inta[i]:
                        inta[i] = d0q
 
        adv0 = 0
        thr0 = 0
        dg0 = 0
        hunt0 = 0
        hang0 = 0
        away_guard_b = [0, 0, 0]
        for j in range(nb):
            if D0[B_p[j]] <= 2:
                away_guard_b[B_t[j]] = 1
 
        max_unstop = len(UNSTOP_RT) - 1
        max_rt = len(RT) - 1
        hunt_range = max(10, (W + H) // 2 + 2)
 
        for i in range(na):
            p = A_p[i]
            t = A_t[i]
            ap = ADV0[p]
            if cB[PRED[t]] == 0:
                ap += ap >> 1
            if away_guard_b[PREY[t]]:
                ap += max(0, hunt_range - D0[p]) * 3
            adv0 += ap
 
            mp = pa[i]
            if mp < MAX_D:
                hunt0 += HW * max(0, hunt_range - mp) + max(0, hunt_range * 2 - ma[i])
            else:
                hunt0 += CENTER[p]
 
            mh = ha[i]
            if mh <= 3:
                pt = PREY[t]
                row = DT[p]
                prot = False
                for k in range(na):
                    if A_t[k] == pt and row[A_p[k]] <= 1:
                        prot = True
                        break
                if not prot:
                    if mh <= 1:
                        dg0 += DP[1] + (160 if s == 1 else 0)
                        hang0 += 1
                    else:
                        dg0 += DP[mh]
                elif mh <= 2:
                    hunt0 += 25
 
            d = D0[p]
            if inta[i] == 999:
                if d <= max_unstop:
                    tv = UNSTOP_RT[d]
                    if tv > thr0:
                        thr0 = tv
            elif d <= max_rt:
                tv = RT[d]
                if mh <= 2 or inta[i] <= d:
                    tv //= 3
                if tv > thr0:
                    thr0 = tv
 
        if hang0 >= 2:
            dg0 += 380 * (hang0 - 1)
 
        adv1 = 0
        thr1 = 0
        dg1 = 0
        hunt1 = 0
        hang1 = 0
        home_guard_a = [0, 0, 0]
        for i in range(na):
            if D1[A_p[i]] <= 2:
                home_guard_a[A_t[i]] = 1
 
        for j in range(nb):
            q = B_p[j]
            u = B_t[j]
            aq = ADV1[q]
            if cA[PRED[u]] == 0:
                aq += aq >> 1
            if home_guard_a[PREY[u]]:
                aq += max(0, hunt_range - D1[q]) * 3
            adv1 += aq
 
            mp = pb[j]
            if mp < MAX_D:
                hunt1 += HW * max(0, hunt_range - mp) + max(0, hunt_range * 2 - mb[j])
            else:
                hunt1 += CENTER[q]
 
            mh = hb[j]
            if mh <= 3:
                pt = PREY[u]
                row = DT[q]
                prot = False
                for k in range(nb):
                    if B_t[k] == pt and row[B_p[k]] <= 1:
                        prot = True
                        break
                if not prot:
                    if mh <= 1:
                        dg1 += DP[1] + (160 if s == 0 else 0)
                        hang1 += 1
                    else:
                        dg1 += DP[mh]
                elif mh <= 2:
                    hunt1 += 25
 
            d = D1[q]
            if intb[j] == 999:
                if d <= max_unstop:
                    tv = UNSTOP_RT[d]
                    if tv > thr1:
                        thr1 = tv
            elif d <= max_rt:
                tv = RT[d]
                if mh <= 2 or intb[j] <= d:
                    tv //= 3
                if tv > thr1:
                    thr1 = tv
 
        if hang1 >= 2:
            dg1 += 380 * (hang1 - 1)
 
        v += K * (adv0 - adv1) + (thr0 - thr1) - (dg0 - dg1) + (hunt0 - hunt1)
 
        # Phòng thủ vùng cờ nhà
        has_useful_def = False
        for i in range(na):
            if D1[A_p[i]] <= 2 and cB[PREY[A_t[i]]] > 0:
                has_useful_def = True
                break
 
        near_cnt = 0
        for j in range(nb):
            d = D1[B_p[j]]
            if d <= 2:
                v -= 520 * (3 - d)
                near_cnt += 1
                if intb[j] == 999:
                    v -= 450 * (3 - d)
            elif d == 3:
                v -= 110
                if intb[j] == 999:
                    v -= 220
            elif d == 4:
                v -= 35
 
        if near_cnt >= 2:
            v -= 420 * (near_cnt - 1)
        if near_cnt >= 1 and not has_useful_def:
            v -= 420 * near_cnt
        if has_useful_def:
            v += 135 + 105 * near_cnt
 
        return v if s == 0 else -v
 
    evc = {}
 
    def evaluate(s, h):
        r = evc.get(h)
        if r is None:
            r = evaluate_raw(s)
            evc[h] = r
        return r
 
    # Tìm kiếm tĩnh (Quiescence Search) giải quyết chuỗi ăn quân và đe dọa chạm đích
    def qsearch(s, alpha, beta, ply, qd, h):
        nodes[0] += 1
        if (nodes[0] & 63) == 0 and (time.process_time() > deadline or time.process_time() - start_time > 0.84):
            abort[0] = True
        if abort[0]:
            return 0
        if wins_now(s):
            return WIN - ply
        o = 1 - s
        in_chk = wins_now(o)
        if in_chk:
            if qd >= 4:
                return -WIN + ply + 1
            all_m = gen(s, 0)
            def_sq = DEF_SQ[o]
            evasions = [m for m in all_m if m[3] in def_sq]
            if not evasions:
                return -WIN + ply + 1
            evasions.sort(reverse=True)
            best = -WIN + ply + 1
            for m in evasions:
                c = m[1]
                p = m[2]
                q = m[3]
                cap = m[4]
                board[p] = 0
                board[q] = c
                ps[c] = q
                h2 = h ^ Z[c][p] ^ Z[c][q] ^ ZS
                if cap:
                    ps[cap] = -1
                    cnt[o] -= 1
                    h2 ^= Z[cap][q]
                still_w = wins_now(o)
                if not still_w:
                    if cap and cnt[o] == 0:
                        val = WIN - ply
                    else:
                        val = -qsearch(o, -beta, -alpha, ply + 1, qd + 1, h2)
                else:
                    val = -WIN + ply + 1
                if cap:
                    cnt[o] += 1
                    ps[cap] = q
                board[q] = cap
                board[p] = c
                ps[c] = p
                if abort[0]:
                    return 0
                if val > best:
                    best = val
                    if val > alpha:
                        alpha = val
                        if alpha >= beta:
                            break
            return best
 
        stand = evaluate(s, h)
        if stand >= beta:
            return stand
        if stand > alpha:
            alpha = stand
        if qd >= 6:
            return stand
 
        moves = gen(s, 2 if qd == 0 else 1)
        if not moves:
            return stand
        moves.sort(reverse=True)
        for m in moves:
            c = m[1]
            p = m[2]
            q = m[3]
            cap = m[4]
            board[p] = 0
            board[q] = c
            ps[c] = q
            h2 = h ^ Z[c][p] ^ Z[c][q] ^ ZS
            if cap:
                ps[cap] = -1
                cnt[o] -= 1
                h2 ^= Z[cap][q]
            if cap and cnt[o] == 0:
                val = WIN - ply
            else:
                val = -qsearch(o, -beta, -alpha, ply + 1, qd + 1, h2)
            if cap:
                cnt[o] += 1
                ps[cap] = q
            board[q] = cap
            board[p] = c
            ps[c] = p
            if abort[0]:
                return 0
            if val > stand:
                stand = val
                if val > alpha:
                    alpha = val
                    if alpha >= beta:
                        break
        return stand
 
    # Alpha-Beta PVS kết hợp bảng băm TT, Killer Heuristic và Late Move Reduction
    def search(s, depth, alpha, beta, ply, h):
        nodes[0] += 1
        if (nodes[0] & 63) == 0 and (time.process_time() > deadline or time.process_time() - start_time > 0.84):
            abort[0] = True
        if abort[0]:
            return 0
        if wins_now(s):
            return WIN - ply
        o = 1 - s
        in_chk = wins_now(o)
        if depth <= 0:
            if in_chk and ply < PLYLIM:
                depth = 1
            else:
                return qsearch(s, alpha, beta, ply, 0, h)
        a0 = alpha
        ttm = None
        e = tt.get(h)
        if e is not None:
            ed, ef, ev, em = e
            if ev > WIN - 1000:
                ev -= ply
            elif ev < -WIN + 1000:
                ev += ply
            ttm = em
            if ed >= depth:
                if ef == 0:
                    return ev
                if ef == 1:
                    if ev >= beta:
                        return ev
                elif ev <= alpha:
                    return ev
 
        moves = gen(s, 0)
        if not moves:
            return -WIN + ply + 1 if in_chk else evaluate(s, h)
        if in_chk:
            def_sq = DEF_SQ[o]
            moves = [m for m in moves if m[3] in def_sq]
            if not moves:
                return -WIN + ply + 1
 
        moves.sort(reverse=True)
        km = KILLER[ply] if ply < 64 else None
        if km is not None or ttm is not None:
            for i in range(len(moves)):
                m = moves[i]
                if ttm is not None and m[1] == ttm[0] and m[2] == ttm[1] and m[3] == ttm[2]:
                    if i:
                        moves.insert(0, moves.pop(i))
                    break
            if km is not None:
                for i in range(1, len(moves)):
                    m = moves[i]
                    if m[1] == km[0] and m[2] == km[1] and m[3] == km[2]:
                        moves.insert(1 if ttm is not None else 0, moves.pop(i))
                        break
 
        best = -WIN + ply + 1 if in_chk else -INF
        bm = None
        idx = 0
        nb_set = DEF_SQ[s]
        for m in moves:
            c = m[1]
            p = m[2]
            q = m[3]
            cap = m[4]
            board[p] = 0
            board[q] = c
            ps[c] = q
            h2 = h ^ Z[c][p] ^ Z[c][q] ^ ZS
            if cap:
                ps[cap] = -1
                cnt[o] -= 1
                h2 ^= Z[cap][q]
 
            if in_chk and wins_now(o):
                val = -WIN + ply + 1
            elif cap and cnt[o] == 0:
                val = WIN - ply
            else:
                if idx == 0:
                    val = -search(o, depth - 1, -beta, -alpha, ply + 1, h2)
                else:
                    red = 1 if (idx >= 4 and depth >= 3 and not cap and not in_chk and q not in nb_set) else 0
                    if idx >= 12 and depth >= 5 and red:
                        red = 2
                    val = -search(o, depth - 1 - red, -alpha - 1, -alpha, ply + 1, h2)
                    if val > alpha and not abort[0]:
                        val = -search(o, depth - 1, -beta, -alpha, ply + 1, h2)
 
            if cap:
                cnt[o] += 1
                ps[cap] = q
            board[q] = cap
            board[p] = c
            ps[c] = p
            if abort[0]:
                return 0
            if val > best:
                best = val
                bm = (c, p, q)
                if val > alpha:
                    alpha = val
                    if alpha >= beta:
                        if not cap:
                            HIST[p * SIZE + q] += depth * depth
                            if ply < 64:
                                KILLER[ply] = bm
                        break
            idx += 1
 
        sv = best
        if sv > WIN - 1000:
            sv += ply
        elif sv < -WIN + 1000:
            sv -= ply
        if best <= a0:
            fl = 2
        elif best >= beta:
            fl = 1
        else:
            fl = 0
        tt[h] = (depth, fl, sv, bm)
        return best
 
    # Chọn nước đi tối ưu bằng Iterative Deepening tại nút gốc
    def decide():
        root = gen(0, 0)
        if not root:
            return (0, 0)
 
        # Kiểm tra nước thắng ngay lập tức
        gset0 = GOAL[0]
        for m in root:
            c0 = m[1]
            p0 = m[2]
            q0 = m[3]
            cap0 = m[4]
            if cap0 and cnt[1] == 1:
                return (pid_of[c0], DIRN[q0 - p0])
            if q0 in gset0:
                if goal_mode == 0:
                    return (pid_of[c0], DIRN[q0 - p0])
                elif all((g == q0 or (ALLY_LO <= board[g] <= ALLY_HI and g != p0)) for g in gset0):
                    return (pid_of[c0], DIRN[q0 - p0])
 
        # Nếu địch đang dọa chạm đích ở lượt kế, lọc các nước phòng thủ bắt buộc
        if wins_now(1):
            safe = []
            for m in root:
                c0 = m[1]
                p0 = m[2]
                q0 = m[3]
                cap0 = m[4]
                board[p0] = 0
                board[q0] = c0
                ps[c0] = q0
                if cap0:
                    ps[cap0] = -1
                    cnt[1] -= 1
                if not wins_now(1):
                    safe.append(m)
                if cap0:
                    cnt[1] += 1
                    ps[cap0] = q0
                board[q0] = cap0
                board[p0] = c0
                ps[c0] = p0
            if safe:
                root = safe
 
        if len(root) == 1:
            return (pid_of[root[0][1]], DIRN[root[0][3] - root[0][2]])
 
        h0 = 0
        for c in range(1, OPP_HI + 1):
            if ps[c] >= 0:
                h0 ^= Z[c][ps[c]]
 
        seen = memo.setdefault('seen', {})
        cfg = memo.setdefault('cfg', {})
        pen_unit = 130 + 2 * min(turn, 200)
        cfg_unit = (45 + 4 * stag) * (0.25 if behind else 1.0)
        hunt_range = max(10, (W + H) // 2 + 2)
 
        order = []
        for m in root:
            c = m[1]
            p = m[2]
            q = m[3]
            cap = m[4]
            t = tp[c]
            pred_t = PRED[t]
            prey_t = PREY[t]
            role = roles.get(c, 'HUNTER')
            tb = m[0] * 10
            if cap:
                tb += 5000
 
            min_pred_p = 999
            min_pred_q = 999
            min_prey_q = 999
            row_p = DT[p]
            row_q = DT[q]
            for ec in range(OPP_LO, OPP_HI + 1):
                ep = ps[ec]
                if ep >= 0 and ec != cap:
                    et = tp[ec]
                    if et == pred_t:
                        if row_p[ep] < min_pred_p:
                            min_pred_p = row_p[ep]
                        if row_q[ep] < min_pred_q:
                            min_pred_q = row_q[ep]
                    elif et == prey_t:
                        if row_q[ep] < min_prey_q:
                            min_prey_q = row_q[ep]
 
            if min_pred_p == 1 and min_pred_q > 1:
                tb += 350
            if min_pred_q == 1:
                tb -= 600
 
            if role == 'RUNNER':
                tb += (D0[p] - D0[q]) * 45 + (ADV0[q] - ADV0[p]) * 20
            elif role == 'DEFENDER':
                tb += (D1[p] - D1[q]) * 35
            else:
                tb += max(0, hunt_range - min_prey_q) * 25
            order.append((tb, m))
        order.sort(reverse=True)
        order = [x[1] for x in order]
 
        # Phạt nhẹ các thế cờ lặp lại để tránh đi quẩn quanh
        pens = {}
        for m in order:
            c = m[1]
            p = m[2]
            q = m[3]
            cap = m[4]
            board[p] = 0
            board[q] = c
            ps[c] = q
            if cap:
                ps[cap] = -1
            key = tuple(ps)
            ck = tuple(ps[ALLY_LO:ALLY_HI + 1])
            if cap:
                ps[cap] = q
            board[q] = cap
            board[p] = c
            ps[c] = p
            pens[(c, p, q)] = min(750, int(pen_unit * seen.get(key, 0) + cfg_unit * cfg.get(ck, 0)))
 
        best_move = order[0]
        for depth in range(1, 42):
            best_adj = -INF
            cur_best = None
            done = 0
            vals = []
            for m in order:
                if time.process_time() - start_time > 0.84:
                    abort[0] = True
                    break
                c = m[1]
                p = m[2]
                q = m[3]
                cap = m[4]
                pen = pens[(c, p, q)]
                araw = best_adj + pen if best_adj > -INF else -INF
                board[p] = 0
                board[q] = c
                ps[c] = q
                h2 = h0 ^ Z[c][p] ^ Z[c][q] ^ ZS
                if cap:
                    ps[cap] = -1
                    cnt[1] -= 1
                    h2 ^= Z[cap][q]
                val = -search(1, depth - 1, -INF, -araw if araw > -INF else INF, 1, h2)
                if cap:
                    cnt[1] += 1
                    ps[cap] = q
                board[q] = cap
                board[p] = c
                ps[c] = p
                if abort[0]:
                    break
                done += 1
                adj = val - pen if val < WIN - 1000 else val
                vals.append((adj, m))
                if adj > best_adj:
                    best_adj = adj
                    cur_best = m
 
            if cur_best is not None and (not abort[0] or done >= 1):
                best_move = cur_best
                if not abort[0]:
                    vals.sort(key=lambda z: z[0], reverse=True)
                    order = [t_item[1] for t_item in vals]
                else:
                    order.remove(cur_best)
                    order.insert(0, cur_best)
            if abort[0]:
                break
            if best_adj > WIN - 1000 or best_adj < -WIN + 1000:
                break
            if time.process_time() > deadline or time.process_time() - start_time > 0.84:
                break
 
        c = best_move[1]
        p = best_move[2]
        q = best_move[3]
        cap = best_move[4]
        board[p] = 0
        board[q] = c
        ps[c] = q
        if cap:
            ps[cap] = -1
        key = tuple(ps)
        seen[key] = seen.get(key, 0) + 1
        ck = tuple(ps[ALLY_LO:ALLY_HI + 1])
        cfg[ck] = cfg.get(ck, 0) + 1
        return (pid_of[c], DIRN[q - p])
 
    try:
        res = decide()
    except Exception:
        # Nhánh dự phòng an toàn nếu gặp sự cố bất ngờ
        res = (0, 0)
        bestk = -INF
        dirs = ((-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0))
        for p in ally_list:
            for d in range(1, 9):
                dx, dy = dirs[d - 1]
                nx = p.x + dx
                ny = p.y + dy
                if nx < 1 or nx > W or ny < 1 or ny > H or (nx, ny) in walls_xy:
                    continue
                ok = True
                for a in ally_list:
                    if a.x == nx and a.y == ny:
                        ok = False
                for e in opp_list:
                    if e.x == nx and e.y == ny:
                        if not ((p.Type == 'R' and e.Type == 'S') or (p.Type == 'S' and e.Type == 'P') or (p.Type == 'P' and e.Type == 'R')):
                            ok = False
                if ok and ADV0[ny * STRIDE + nx] > bestk:
                    bestk = ADV0[ny * STRIDE + nx]
                    res = (p.pid, d)
 
    memo['used'] = used + (time.process_time() - start_time)
    return res

aW1wb3J0IG1hdGgKaW1wb3J0IHJhbmRvbQppbXBvcnQgdGltZQoKCmRlZiBwbGF5KGdhbWVTdGF0ZSwgbWVtbz17fSk6CiAgICBzdGFydF90aW1lID0gdGltZS5wcm9jZXNzX3RpbWUoKQogICAgdHVybiA9IGdhbWVTdGF0ZS5jdXJyZW50VHVybgogICAgbWF4VCA9IGdhbWVTdGF0ZS5tYXhUdXJuCgogICAgSU5GID0gMTAgKiogOQogICAgV0lOID0gMTAwMDAwCiAgICBQTFlMSU0gPSA0NAoKICAgIFcgPSBnYW1lU3RhdGUud2lkdGgKICAgIEggPSBnYW1lU3RhdGUuaGVpZ2h0CiAgICBnb2FsX21vZGUgPSBnYW1lU3RhdGUuZ29hbE1vZGUKCiAgICB3YWxsc194eSA9IGZyb3plbnNldCgody54LCB3LnkpIGZvciB3IGluIGdhbWVTdGF0ZS53YWxscykKICAgIGdvYWxzMF94eSA9IGZyb3plbnNldCgoZy54LCBnLnkpIGZvciBnIGluIGdhbWVTdGF0ZS5nb2Fscykgb3IgZnJvemVuc2V0KFsoVywgSCldKQogICAgZ29hbHMxX3h5ID0gZnJvemVuc2V0KChnLngsIGcueSkgZm9yIGcgaW4gZ2FtZVN0YXRlLmVuZW15R29hbHMpIG9yIGZyb3plbnNldChbKDEsIDEpXSkKCiAgICAjIELhuqNuZyBraOG6r2MgY2jhur86IDA9UiAoQsO6YSksIDE9UCAoQmFvKSwgMj1TIChLw6lvKQogICAgQlQgPSAoKEZhbHNlLCBGYWxzZSwgVHJ1ZSksIChUcnVlLCBGYWxzZSwgRmFsc2UpLCAoRmFsc2UsIFRydWUsIEZhbHNlKSkKICAgIFBSRUQgPSAoMSwgMiwgMCkKICAgIFBSRVkgPSAoMiwgMCwgMSkKCiAgICBFTElNMSA9IDY1CiAgICBFTElNMiA9IDAKCiAgICAjIE7hur91IHRy4bqtbiB0csaw4bubYyBi4buLIHJlc2V0IGdp4buvYSBjaOG7q25nIHRow6wgeMOzYSBjYWNoZSBjxakKICAgIGlmIHR1cm4gPD0gMSBhbmQgJ3RhYnMnIGluIG1lbW86CiAgICAgICAgbWVtby5jbGVhcigpCgogICAgbWFwX3NpZyA9IChXLCBILCB3YWxsc194eSwgZ29hbHMwX3h5LCBnb2FsczFfeHksIGdvYWxfbW9kZSkKICAgIHRhYnMgPSBtZW1vLmdldCgndGFicycpCgogICAgIyBLaOG7n2kgdOG6oW8gYuG6o25nIHRyYSBj4bupdSBi4bqjbiDEkeG7kyAoY2jhuqF5IDEgbOG6p24g4bufIGzGsOG7o3QgxJHhuqd1IGhv4bq3YyBraGkgxJHhu5VpIG1hcCkKICAgIGlmIHRhYnMgaXMgTm9uZSBvciBtZW1vLmdldCgnbWFwX3NpZycpICE9IG1hcF9zaWc6CiAgICAgICAgbWVtb1snbWFwX3NpZyddID0gbWFwX3NpZwogICAgICAgIG1lbW9bJ3R0J10gPSB7fQogICAgICAgIG1lbW9bJ2hpc3QnXSA9IE5vbmUKICAgICAgICBtZW1vWydzZWVuJ10gPSB7fQogICAgICAgIG1lbW9bJ2NmZyddID0ge30KCiAgICAgICAgU1RSSURFID0gVyArIDIKICAgICAgICBTSVpFID0gKFcgKyAyKSAqIChIICsgMikKICAgICAgICBPRkZTID0gKFNUUklERSArIDEsIFNUUklERSwgMSwgU1RSSURFIC0gMSwgLShTVFJJREUgLSAxKSwgLTEsIC1TVFJJREUsIC0oU1RSSURFICsgMSkpCiAgICAgICAgRElSTiA9IHsKICAgICAgICAgICAgU1RSSURFIC0gMTogMSwKICAgICAgICAgICAgU1RSSURFOiAyLAogICAgICAgICAgICBTVFJJREUgKyAxOiAzLAogICAgICAgICAgICAxOiA0LAogICAgICAgICAgICAtKFNUUklERSAtIDEpOiA1LAogICAgICAgICAgICAtU1RSSURFOiA2LAogICAgICAgICAgICAtKFNUUklERSArIDEpOiA3LAogICAgICAgICAgICAtMTogOCwKICAgICAgICB9CgogICAgICAgIHdhbGxfc2V0ID0gZnJvemVuc2V0KAogICAgICAgICAgICB5ICogU1RSSURFICsgeCBmb3IgKHgsIHkpIGluIHdhbGxzX3h5IGlmIDEgPD0geCA8PSBXIGFuZCAxIDw9IHkgPD0gSAogICAgICAgICkKICAgICAgICBjZWxscyA9IFsKICAgICAgICAgICAgeSAqIFNUUklERSArIHgKICAgICAgICAgICAgZm9yIHkgaW4gcmFuZ2UoMSwgSCArIDEpCiAgICAgICAgICAgIGZvciB4IGluIHJhbmdlKDEsIFcgKyAxKQogICAgICAgICAgICBpZiAoeSAqIFNUUklERSArIHgpIG5vdCBpbiB3YWxsX3NldAogICAgICAgIF0KICAgICAgICB2YWxpZF9zZXQgPSBzZXQoY2VsbHMpCgogICAgICAgIEdPQUwwID0gZnJvemVuc2V0KHkgKiBTVFJJREUgKyB4IGZvciAoeCwgeSkgaW4gZ29hbHMwX3h5IGlmICh5ICogU1RSSURFICsgeCkgaW4gdmFsaWRfc2V0KQogICAgICAgIEdPQUwxID0gZnJvemVuc2V0KHkgKiBTVFJJREUgKyB4IGZvciAoeCwgeSkgaW4gZ29hbHMxX3h5IGlmICh5ICogU1RSSURFICsgeCkgaW4gdmFsaWRfc2V0KQogICAgICAgIEdPQUwgPSAoR09BTDAsIEdPQUwxKQoKICAgICAgICBuYjBfc2V0ID0ge2cgKyBvZmYgZm9yIGcgaW4gR09BTDAgZm9yIG9mZiBpbiBPRkZTIGlmIChnICsgb2ZmKSBpbiB2YWxpZF9zZXQgYW5kIChnICsgb2ZmKSBub3QgaW4gR09BTDB9CiAgICAgICAgbmIxX3NldCA9IHtnICsgb2ZmIGZvciBnIGluIEdPQUwxIGZvciBvZmYgaW4gT0ZGUyBpZiAoZyArIG9mZikgaW4gdmFsaWRfc2V0IGFuZCAoZyArIG9mZikgbm90IGluIEdPQUwxfQogICAgICAgIE5CID0gKHR1cGxlKG5iMF9zZXQpLCB0dXBsZShuYjFfc2V0KSkKICAgICAgICBERUZfU1EgPSAoR09BTDAgfCBuYjBfc2V0LCBHT0FMMSB8IG5iMV9zZXQpCgogICAgICAgIE1BWF9EID0gVyArIEggKyAxMgoKICAgICAgICAjIEJGUyB0w61uaCBraG/huqNuZyBjw6FjaCBuZ+G6r24gbmjhuqV0IG7DqSB0xrDhu51uZyB04bubaSB04bqtcCDDtCDEkcOtY2ggY+G7p2EgdGEgKEQwKSB2w6AgxJHhu4tjaCAoRDEpCiAgICAgICAgRDAgPSBbTUFYX0RdICogU0laRQogICAgICAgIGJmc19xID0gbGlzdChHT0FMMCkKICAgICAgICBmb3IgZyBpbiBHT0FMMDoKICAgICAgICAgICAgRDBbZ10gPSAwCiAgICAgICAgaGVhZCA9IDAKICAgICAgICB3aGlsZSBoZWFkIDwgbGVuKGJmc19xKToKICAgICAgICAgICAgdSA9IGJmc19xW2hlYWRdCiAgICAgICAgICAgIGhlYWQgKz0gMQogICAgICAgICAgICBkdSA9IEQwW3VdICsgMQogICAgICAgICAgICBmb3Igb2ZmIGluIE9GRlM6CiAgICAgICAgICAgICAgICB2ID0gdSArIG9mZgogICAgICAgICAgICAgICAgaWYgdiBpbiB2YWxpZF9zZXQgYW5kIGR1IDwgRDBbdl06CiAgICAgICAgICAgICAgICAgICAgRDBbdl0gPSBkdQogICAgICAgICAgICAgICAgICAgIGJmc19xLmFwcGVuZCh2KQoKICAgICAgICBEMSA9IFtNQVhfRF0gKiBTSVpFCiAgICAgICAgYmZzX3EgPSBsaXN0KEdPQUwxKQogICAgICAgIGZvciBnIGluIEdPQUwxOgogICAgICAgICAgICBEMVtnXSA9IDAKICAgICAgICBoZWFkID0gMAogICAgICAgIHdoaWxlIGhlYWQgPCBsZW4oYmZzX3EpOgogICAgICAgICAgICB1ID0gYmZzX3FbaGVhZF0KICAgICAgICAgICAgaGVhZCArPSAxCiAgICAgICAgICAgIGR1ID0gRDFbdV0gKyAxCiAgICAgICAgICAgIGZvciBvZmYgaW4gT0ZGUzoKICAgICAgICAgICAgICAgIHYgPSB1ICsgb2ZmCiAgICAgICAgICAgICAgICBpZiB2IGluIHZhbGlkX3NldCBhbmQgZHUgPCBEMVt2XToKICAgICAgICAgICAgICAgICAgICBEMVt2XSA9IGR1CiAgICAgICAgICAgICAgICAgICAgYmZzX3EuYXBwZW5kKHYpCgogICAgICAgICMgQkZTIHTDrW5oIGtob+G6o25nIGPDoWNoIHRo4buxYyB04bq/IGdp4buvYSBt4buNaSBj4bq3cCDDtCBo4bujcCBs4buHIMSR4buDIHPEg24gxJF14buVaSB2w7JuZyBxdWEgduG6rXQgY+G6o24KICAgICAgICBEVCA9IFtbTUFYX0RdICogU0laRSBmb3IgXyBpbiByYW5nZShTSVpFKV0KICAgICAgICBNRFQgPSBbW01BWF9EICogMl0gKiBTSVpFIGZvciBfIGluIHJhbmdlKFNJWkUpXQogICAgICAgIGZvciBzcmMgaW4gY2VsbHM6CiAgICAgICAgICAgIHJvdyA9IERUW3NyY10KICAgICAgICAgICAgbXJvdyA9IE1EVFtzcmNdCiAgICAgICAgICAgIHJvd1tzcmNdID0gMAogICAgICAgICAgICBtcm93W3NyY10gPSAwCiAgICAgICAgICAgIGJmc19xID0gW3NyY10KICAgICAgICAgICAgaGVhZCA9IDAKICAgICAgICAgICAgd2hpbGUgaGVhZCA8IGxlbihiZnNfcSk6CiAgICAgICAgICAgICAgICB1ID0gYmZzX3FbaGVhZF0KICAgICAgICAgICAgICAgIGhlYWQgKz0gMQogICAgICAgICAgICAgICAgZHUgPSByb3dbdV0gKyAxCiAgICAgICAgICAgICAgICBmb3Igb2ZmIGluIE9GRlM6CiAgICAgICAgICAgICAgICAgICAgdiA9IHUgKyBvZmYKICAgICAgICAgICAgICAgICAgICBpZiB2IGluIHZhbGlkX3NldCBhbmQgZHUgPCByb3dbdl06CiAgICAgICAgICAgICAgICAgICAgICAgIHJvd1t2XSA9IGR1CiAgICAgICAgICAgICAgICAgICAgICAgIG1yb3dbdl0gPSBkdSAqIDIKICAgICAgICAgICAgICAgICAgICAgICAgYmZzX3EuYXBwZW5kKHYpCgogICAgICAgIG1heF9kMCA9IG1heCgoRDBbYV0gZm9yIGEgaW4gY2VsbHMgaWYgRDBbYV0gPCBNQVhfRCksIGRlZmF1bHQ9MSkKICAgICAgICBtYXhfZDEgPSBtYXgoKEQxW2FdIGZvciBhIGluIGNlbGxzIGlmIEQxW2FdIDwgTUFYX0QpLCBkZWZhdWx0PTEpCiAgICAgICAgQURWMCA9IFswXSAqIFNJWkUKICAgICAgICBBRFYxID0gWzBdICogU0laRQogICAgICAgIENFTlRFUiA9IFswXSAqIFNJWkUKICAgICAgICBtaWRfeCA9IChXICsgMSkgKiAwLjUKICAgICAgICBtaWRfeSA9IChIICsgMSkgKiAwLjUKICAgICAgICBmb3IgYSBpbiBjZWxsczoKICAgICAgICAgICAgeCA9IGEgJSBTVFJJREUKICAgICAgICAgICAgeSA9IGEgLy8gU1RSSURFCiAgICAgICAgICAgIEFEVjBbYV0gPSBtYXgoMCwgbWF4X2QwIC0gRDBbYV0pCiAgICAgICAgICAgIEFEVjFbYV0gPSBtYXgoMCwgbWF4X2QxIC0gRDFbYV0pCiAgICAgICAgICAgIGN4ID0gYWJzKHggLSBtaWRfeCkgLyBtYXgoMS4wLCBXIC8gOS4wKQogICAgICAgICAgICBjeSA9IGFicyh5IC0gbWlkX3kpIC8gbWF4KDEuMCwgSCAvIDkuMCkKICAgICAgICAgICAgQ0VOVEVSW2FdID0gbWF4KDAsIGludCg0IC0gbWF4KGN4LCBjeSkpKQoKICAgICAgICAjIELhuqNuZyBuxrDhu5tjIMSRaSBo4bujcCBs4buHIHPhuq9wIHjhur9wIHPhurVuIHRoZW8gxJHhu5kgZ2nhuqNtIGtob+G6o25nIGPDoWNoIHThu5tpIMSRw61jaAogICAgICAgIE1UQUIwID0gWygpIGZvciBfIGluIHJhbmdlKFNJWkUpXQogICAgICAgIE1UQUIxID0gWygpIGZvciBfIGluIHJhbmdlKFNJWkUpXQogICAgICAgIGZvciBhIGluIGNlbGxzOgogICAgICAgICAgICBtMCA9IFtdCiAgICAgICAgICAgIG0xID0gW10KICAgICAgICAgICAgZm9yIG9mZiBpbiBPRkZTOgogICAgICAgICAgICAgICAgcSA9IGEgKyBvZmYKICAgICAgICAgICAgICAgIGlmIHEgaW4gdmFsaWRfc2V0OgogICAgICAgICAgICAgICAgICAgIGhfaXggPSBhICogU0laRSArIHEKICAgICAgICAgICAgICAgICAgICBmdzBfYiA9IChEMFthXSAtIEQwW3FdKSAqIDIKICAgICAgICAgICAgICAgICAgICBmdzFfYiA9IChEMVthXSAtIEQxW3FdKSAqIDIKICAgICAgICAgICAgICAgICAgICBtMC5hcHBlbmQoKHEsIGZ3MF9iLCBoX2l4LCAxIGlmIHEgaW4gbmIwX3NldCBlbHNlIDApKQogICAgICAgICAgICAgICAgICAgIG0xLmFwcGVuZCgocSwgZncxX2IsIGhfaXgsIDEgaWYgcSBpbiBuYjFfc2V0IGVsc2UgMCkpCiAgICAgICAgICAgIG0wLnNvcnQoa2V5PWxhbWJkYSBpdGVtOiBpdGVtWzFdLCByZXZlcnNlPVRydWUpCiAgICAgICAgICAgIG0xLnNvcnQoa2V5PWxhbWJkYSBpdGVtOiBpdGVtWzFdLCByZXZlcnNlPVRydWUpCiAgICAgICAgICAgIE1UQUIwW2FdID0gdHVwbGUobTApCiAgICAgICAgICAgIE1UQUIxW2FdID0gdHVwbGUobTEpCiAgICAgICAgTVRBQiA9ICh0dXBsZShNVEFCMCksIHR1cGxlKE1UQUIxKSkKCiAgICAgICAgIyBC4bqjbmcgxJFp4buDbSB0aMaw4bufbmcga2hv4bqjbmcgY8OhY2ggdOG7m2kgxJHDrWNoICh04buxIGNvIGdpw6NuIHRoZW8ga8OtY2ggdGjGsOG7m2MgbWFwKQogICAgICAgIFJUID0gdHVwbGUoWzBdICsgW2ludCg5NTAgKiAoMC42MCAqKiAoZCAtIDEpKSkgZm9yIGQgaW4gcmFuZ2UoMSwgTUFYX0QgKyAxKV0pCiAgICAgICAgVU5TVE9QX1JUID0gdHVwbGUoWzBdICsgW2ludCgxNzUwICogKDAuNjQgKiogKGQgLSAxKSkpIGZvciBkIGluIHJhbmdlKDEsIE1BWF9EICsgMSldKQoKICAgICAgICByeiA9IHJhbmRvbS5SYW5kb20oMjAyNjA0MDIpCiAgICAgICAgWiA9IHR1cGxlKHR1cGxlKHJ6LmdldHJhbmRiaXRzKDUyKSBmb3IgXyBpbiByYW5nZShTSVpFKSkgZm9yIF8gaW4gcmFuZ2UoNDgpKQogICAgICAgIFpTID0gcnouZ2V0cmFuZGJpdHMoNTIpCgogICAgICAgIHRhYnMgPSAoCiAgICAgICAgICAgIFNUUklERSwgU0laRSwgTUFYX0QsIE9GRlMsIERJUk4sIHdhbGxfc2V0LCBHT0FMLCBOQiwgREVGX1NRLAogICAgICAgICAgICBEVCwgTURULCBBRFYwLCBBRFYxLCBEMCwgRDEsIENFTlRFUiwgTVRBQiwgUlQsIFVOU1RPUF9SVCwgWiwgWlMKICAgICAgICApCiAgICAgICAgbWVtb1sndGFicyddID0gdGFicwoKICAgICgKICAgICAgICBTVFJJREUsIFNJWkUsIE1BWF9ELCBPRkZTLCBESVJOLCB3YWxsX3NldCwgR09BTCwgTkIsIERFRl9TUSwKICAgICAgICBEVCwgTURULCBBRFYwLCBBRFYxLCBEMCwgRDEsIENFTlRFUiwgTVRBQiwgUlQsIFVOU1RPUF9SVCwgWiwgWlMKICAgICkgPSB0YWJzCgogICAgIyBRdeG6o24gbMO9IG5nw6JuIHPDoWNoIENQVTogdOG7lW5nIDE4MHMvdsOhbiwgdOG7kWkgxJFhIDFzL27GsOG7m2MgKGNo4buRdCDhu58gMC44MnMgxJHhu4MgYW4gdG/DoG4pCiAgICB1c2VkID0gbWVtby5nZXQoJ3VzZWQnLCAwLjApCiAgICBsZWZ0ID0gbWF4KDEsIChtYXhUIC0gdHVybikgLy8gMiArIDEpCiAgICBpZiB0dXJuIDw9IDE6CiAgICAgICAgYnVkZ2V0ID0gMC44MgogICAgZWxzZToKICAgICAgICBidWRnZXQgPSBtaW4oMC44MiwgbWF4KDAuMDQsICgxNjAuMCAtIHVzZWQpIC8gbWluKGxlZnQsIDE1MCkpKQogICAgZGVhZGxpbmUgPSBzdGFydF90aW1lICsgYnVkZ2V0CgogICAgIyBE4buxbmcgYsOgbiBj4budIDEgY2hp4buBdTogbmdvw6BpIGJpw6puIHbDoCDDtCB0xrDhu51uZyDEkWVuIG1hbmcgZ2nDoSB0cuG7iyAtMQogICAgYm9hcmQgPSBbLTFdICogU0laRQogICAgZm9yIHl5IGluIHJhbmdlKDEsIEggKyAxKToKICAgICAgICBiYXNlX3kgPSB5eSAqIFNUUklERQogICAgICAgIGZvciB4eCBpbiByYW5nZSgxLCBXICsgMSk6CiAgICAgICAgICAgIHBvcyA9IGJhc2VfeSArIHh4CiAgICAgICAgICAgIGlmIHBvcyBub3QgaW4gd2FsbF9zZXQ6CiAgICAgICAgICAgICAgICBib2FyZFtwb3NdID0gMAoKICAgICMgxJDDoW5oIGNo4buJIHPhu5EgxJHhu5luZyBjaG8gcXXDom4gaGFpIGLDqm4gKGjhu5cgdHLhu6MgbWFwIGPDsyBz4buRIHF1w6JuIGtow6FjIDkpCiAgICBhbGx5X2xpc3QgPSBsaXN0KGdhbWVTdGF0ZS5hbGx5KQogICAgb3BwX2xpc3QgPSBsaXN0KGdhbWVTdGF0ZS5vcHBvbmVudCkKICAgIG5hX2luaXQgPSBsZW4oYWxseV9saXN0KQogICAgbmJfaW5pdCA9IGxlbihvcHBfbGlzdCkKCiAgICBBTExZX0xPID0gMQogICAgQUxMWV9ISSA9IG5hX2luaXQKICAgIE9QUF9MTyA9IG5hX2luaXQgKyAyCiAgICBPUFBfSEkgPSBPUFBfTE8gKyBuYl9pbml0IC0gMQogICAgTE8gPSAoQUxMWV9MTywgT1BQX0xPKQogICAgSEkgPSAoQUxMWV9ISSwgT1BQX0hJKQoKICAgIHNsb3RfY2FwID0gbWF4KDQ4LCBPUFBfSEkgKyAyKQogICAgaWYgbGVuKFopIDwgc2xvdF9jYXA6CiAgICAgICAgcnogPSByYW5kb20uUmFuZG9tKDIwMjYwNDAyKQogICAgICAgIFogPSB0dXBsZSh0dXBsZShyei5nZXRyYW5kYml0cyg1MikgZm9yIF8gaW4gcmFuZ2UoU0laRSkpIGZvciBfIGluIHJhbmdlKHNsb3RfY2FwKSkKCiAgICB0cCA9IFswXSAqIHNsb3RfY2FwCiAgICBwcyA9IFstMV0gKiBzbG90X2NhcAogICAgcGlkX29mID0gWzBdICogc2xvdF9jYXAKICAgIFRJID0geydSJzogMCwgJ1AnOiAxLCAnUyc6IDJ9CiAgICBjbnQgPSBbMCwgMF0KCiAgICBmb3IgaWR4X2EsIHAgaW4gZW51bWVyYXRlKGFsbHlfbGlzdCk6CiAgICAgICAgYyA9IEFMTFlfTE8gKyBpZHhfYQogICAgICAgIHBpZF9vZltjXSA9IHAucGlkCiAgICAgICAgdHBbY10gPSBUSVtwLlR5cGVdCiAgICAgICAgcG9zID0gcC55ICogU1RSSURFICsgcC54CiAgICAgICAgcHNbY10gPSBwb3MKICAgICAgICBib2FyZFtwb3NdID0gYwogICAgICAgIGNudFswXSArPSAxCgogICAgZm9yIGlkeF9iLCBwIGluIGVudW1lcmF0ZShvcHBfbGlzdCk6CiAgICAgICAgYyA9IE9QUF9MTyArIGlkeF9iCiAgICAgICAgcGlkX29mW2NdID0gcC5waWQKICAgICAgICB0cFtjXSA9IFRJW3AuVHlwZV0KICAgICAgICBwb3MgPSBwLnkgKiBTVFJJREUgKyBwLngKICAgICAgICBwc1tjXSA9IHBvcwogICAgICAgIGJvYXJkW3Bvc10gPSBjCiAgICAgICAgY250WzFdICs9IDEKCiAgICB0dCA9IG1lbW8uZ2V0KCd0dCcpCiAgICBpZiB0dCBpcyBOb25lIG9yIGxlbih0dCkgPiAxMjAwMDA6CiAgICAgICAgdHQgPSB7fQogICAgICAgIG1lbW9bJ3R0J10gPSB0dAoKICAgIGhpc3RfbGVuID0gU0laRSAqIFNJWkUKICAgIEhJU1QgPSBtZW1vLmdldCgnaGlzdCcpCiAgICBpZiBISVNUIGlzIE5vbmUgb3IgbGVuKEhJU1QpICE9IGhpc3RfbGVuOgogICAgICAgIEhJU1QgPSBbMF0gKiBoaXN0X2xlbgogICAgICAgIG1lbW9bJ2hpc3QnXSA9IEhJU1QKICAgIGVsc2U6CiAgICAgICAgZm9yIGkgaW4gcmFuZ2UoaGlzdF9sZW4pOgogICAgICAgICAgICBpZiBISVNUW2ldOgogICAgICAgICAgICAgICAgSElTVFtpXSA+Pj0gMQoKICAgIEtJTExFUiA9IFtOb25lXSAqIDY0CiAgICBub2RlcyA9IFswXQogICAgYWJvcnQgPSBbRmFsc2VdCgogICAgdG90YWwgPSBjbnRbMF0gKyBjbnRbMV0KICAgIGlmIG1lbW8uZ2V0KCdwcmV2X3RvdGFsJykgIT0gdG90YWw6CiAgICAgICAgbWVtb1sncHJldl90b3RhbCddID0gdG90YWwKICAgICAgICBtZW1vWydjYXB0X3R1cm4nXSA9IHR1cm4KICAgICAgICBtZW1vWydjZmcnXSA9IHt9CiAgICBzdGFnID0gKHR1cm4gLSBtZW1vLmdldCgnY2FwdF90dXJuJywgdHVybikpIC8vIDIKICAgIGFoZWFkID0gY250WzBdID4gY250WzFdCiAgICBiZWhpbmQgPSBjbnRbMF0gPCBjbnRbMV0KCiAgICBLID0gNSArIG1pbig4LCB0dXJuIC8vIDI1KQogICAgaWYgbm90IGJlaGluZCBhbmQgc3RhZyA+IDE2OgogICAgICAgIEsgKz0gbWluKDcsIChzdGFnIC0gMTYpIC8vIDYpCiAgICBpZiBiZWhpbmQ6CiAgICAgICAgSFcgPSAzCiAgICBlbGlmIHN0YWcgPiAxNjoKICAgICAgICBIVyA9IDExCiAgICBlbHNlOgogICAgICAgIEhXID0gNgogICAgaWYgYWhlYWQgYW5kIHN0YWcgPiAyNjoKICAgICAgICBEUCA9ICgwLCAyMjAsIDEyMCwgNTUpCiAgICBlbHNlOgogICAgICAgIERQID0gKDAsIDMzMCwgMTc1LCA4MCkKCiAgICAjIFBow6JuIHZhaSBjaGnhur9uIHRodeG6rXQ6IERFRkVOREVSIChjaOG6t24gxJHDrWNoIG5ow6ApLCBSVU5ORVIgKMSR4buZdCBwaMOhKSwgSFVOVEVSIChzxINuIHF1w6JuKQogICAgcm9sZXMgPSB7fQogICAgZV90eXBlc19hbGl2ZSA9IFswLCAwLCAwXQogICAgZV9uZWFyX2hvbWUgPSBbXQogICAgZV9uZWFyX2F3YXkgPSBbMCwgMCwgMF0KICAgIGZvciBjIGluIHJhbmdlKE9QUF9MTywgT1BQX0hJICsgMSk6CiAgICAgICAgcSA9IHBzW2NdCiAgICAgICAgaWYgcSA+PSAwOgogICAgICAgICAgICB1ID0gdHBbY10KICAgICAgICAgICAgZV90eXBlc19hbGl2ZVt1XSArPSAxCiAgICAgICAgICAgIGlmIEQxW3FdIDw9IDQ6CiAgICAgICAgICAgICAgICBlX25lYXJfaG9tZS5hcHBlbmQoKEQxW3FdLCBxLCB1KSkKICAgICAgICAgICAgaWYgRDBbcV0gPD0gMjoKICAgICAgICAgICAgICAgIGVfbmVhcl9hd2F5W3VdICs9IDEKICAgIGVfbmVhcl9ob21lLnNvcnQoKQoKICAgIGRlZl9hc3NpZ25lZCA9IHNldCgpCiAgICBmb3IgZF9oLCBxX2gsIHVfaCBpbiBlX25lYXJfaG9tZToKICAgICAgICBuZWVkX3QgPSBQUkVEW3VfaF0KICAgICAgICBiZXN0X2MgPSAwCiAgICAgICAgYmVzdF9kID0gOTk5CiAgICAgICAgZm9yIGMgaW4gcmFuZ2UoQUxMWV9MTywgQUxMWV9ISSArIDEpOgogICAgICAgICAgICBwID0gcHNbY10KICAgICAgICAgICAgaWYgcCA+PSAwIGFuZCB0cFtjXSA9PSBuZWVkX3QgYW5kIGMgbm90IGluIGRlZl9hc3NpZ25lZDoKICAgICAgICAgICAgICAgIGRfYyA9IEQxW3BdCiAgICAgICAgICAgICAgICBpZiBkX2MgPCBiZXN0X2Q6CiAgICAgICAgICAgICAgICAgICAgYmVzdF9kID0gZF9jCiAgICAgICAgICAgICAgICAgICAgYmVzdF9jID0gYwogICAgICAgIGlmIGJlc3RfYzoKICAgICAgICAgICAgcm9sZXNbYmVzdF9jXSA9ICdERUZFTkRFUicKICAgICAgICAgICAgZGVmX2Fzc2lnbmVkLmFkZChiZXN0X2MpCgogICAgaWYgbm90IGRlZl9hc3NpZ25lZDoKICAgICAgICBiZXN0X2MgPSAwCiAgICAgICAgYmVzdF9kID0gOTk5CiAgICAgICAgZm9yIGMgaW4gcmFuZ2UoQUxMWV9MTywgQUxMWV9ISSArIDEpOgogICAgICAgICAgICBwID0gcHNbY10KICAgICAgICAgICAgaWYgcCA+PSAwIGFuZCBlX3R5cGVzX2FsaXZlW1BSRVlbdHBbY11dXSA+IDA6CiAgICAgICAgICAgICAgICBkX2MgPSBEMVtwXQogICAgICAgICAgICAgICAgaWYgZF9jIDwgYmVzdF9kOgogICAgICAgICAgICAgICAgICAgIGJlc3RfZCA9IGRfYwogICAgICAgICAgICAgICAgICAgIGJlc3RfYyA9IGMKICAgICAgICBpZiBiZXN0X2MgYW5kIGJlc3RfZCA8PSAzOgogICAgICAgICAgICByb2xlc1tiZXN0X2NdID0gJ0RFRkVOREVSJwogICAgICAgICAgICBkZWZfYXNzaWduZWQuYWRkKGJlc3RfYykKCiAgICBydW5uZXJfY2FuZHMgPSBbXQogICAgZm9yIGMgaW4gcmFuZ2UoQUxMWV9MTywgQUxMWV9ISSArIDEpOgogICAgICAgIHAgPSBwc1tjXQogICAgICAgIGlmIHAgPj0gMCBhbmQgYyBub3QgaW4gZGVmX2Fzc2lnbmVkOgogICAgICAgICAgICB0ID0gdHBbY10KICAgICAgICAgICAgaW1tID0gMSBpZiBlX3R5cGVzX2FsaXZlW1BSRURbdF1dID09IDAgZWxzZSAwCiAgICAgICAgICAgIGJyayA9IDEgaWYgZV9uZWFyX2F3YXlbUFJFWVt0XV0gPiAwIGVsc2UgMAogICAgICAgICAgICBydW5uZXJfY2FuZHMuYXBwZW5kKChEMFtwXSAtIDIgKiBpbW0gLSBicmssIC1BRFYwW3BdLCBjKSkKICAgIHJ1bm5lcl9jYW5kcy5zb3J0KCkKICAgIG51bV9ydW5uZXJzID0gbWF4KDIsIGxlbihHT0FMWzBdKSkgaWYgZ29hbF9tb2RlID09IDEgZWxzZSAyCiAgICBmb3IgaWR4X3IgaW4gcmFuZ2UobWluKG51bV9ydW5uZXJzLCBsZW4ocnVubmVyX2NhbmRzKSkpOgogICAgICAgIHJvbGVzW3J1bm5lcl9jYW5kc1tpZHhfcl1bMl1dID0gJ1JVTk5FUicKICAgIGZvciBjIGluIHJhbmdlKEFMTFlfTE8sIEFMTFlfSEkgKyAxKToKICAgICAgICBpZiBwc1tjXSA+PSAwIGFuZCBjIG5vdCBpbiByb2xlczoKICAgICAgICAgICAgcm9sZXNbY10gPSAnSFVOVEVSJwoKICAgICMgS2nhu4NtIHRyYSBwaGUgcyBjw7MgdGjhu4MgY2jhuqFtIMSRw61jaCB0aOG6r25nIG5nYXkgdHJvbmcgMSBuxrDhu5tjIMSRaSBraMO0bmcKICAgIGRlZiB3aW5zX25vdyhzKToKICAgICAgICBsbyA9IExPW3NdCiAgICAgICAgaGkgPSBISVtzXQogICAgICAgIGdzZXQgPSBHT0FMW3NdCiAgICAgICAgaWYgZ29hbF9tb2RlID09IDA6CiAgICAgICAgICAgIGZvciBnIGluIGdzZXQ6CiAgICAgICAgICAgICAgICB2MCA9IGJvYXJkW2ddCiAgICAgICAgICAgICAgICBpZiBsbyA8PSB2MCA8PSBoaToKICAgICAgICAgICAgICAgICAgICByZXR1cm4gVHJ1ZQogICAgICAgICAgICAgICAgaWYgdjAgPT0gMDoKICAgICAgICAgICAgICAgICAgICBmb3Igb2ZmIGluIE9GRlM6CiAgICAgICAgICAgICAgICAgICAgICAgIHYgPSBib2FyZFtnICsgb2ZmXQogICAgICAgICAgICAgICAgICAgICAgICBpZiBsbyA8PSB2IDw9IGhpOgogICAgICAgICAgICAgICAgICAgICAgICAgICAgcmV0dXJuIFRydWUKICAgICAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICAgICAgdCA9IHRwW3YwXQogICAgICAgICAgICAgICAgICAgIGZvciBvZmYgaW4gT0ZGUzoKICAgICAgICAgICAgICAgICAgICAgICAgdiA9IGJvYXJkW2cgKyBvZmZdCiAgICAgICAgICAgICAgICAgICAgICAgIGlmIGxvIDw9IHYgPD0gaGkgYW5kIEJUW3RwW3ZdXVt0XToKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJldHVybiBUcnVlCiAgICAgICAgICAgIHJldHVybiBGYWxzZQogICAgICAgIGVsc2U6CiAgICAgICAgICAgIG1pc3NpbmcgPSBbZyBmb3IgZyBpbiBnc2V0IGlmIG5vdCAobG8gPD0gYm9hcmRbZ10gPD0gaGkpXQogICAgICAgICAgICBpZiBub3QgbWlzc2luZzoKICAgICAgICAgICAgICAgIHJldHVybiBUcnVlCiAgICAgICAgICAgIGlmIGxlbihtaXNzaW5nKSA+IDE6CiAgICAgICAgICAgICAgICByZXR1cm4gRmFsc2UKICAgICAgICAgICAgZyA9IG1pc3NpbmdbMF0KICAgICAgICAgICAgdjAgPSBib2FyZFtnXQogICAgICAgICAgICBmb3Igb2ZmIGluIE9GRlM6CiAgICAgICAgICAgICAgICBzcmMgPSBnICsgb2ZmCiAgICAgICAgICAgICAgICB2ID0gYm9hcmRbc3JjXQogICAgICAgICAgICAgICAgaWYgbG8gPD0gdiA8PSBoaSBhbmQgc3JjIG5vdCBpbiBnc2V0OgogICAgICAgICAgICAgICAgICAgIGlmIHYwID09IDAgb3IgQlRbdHBbdl1dW3RwW3YwXV06CiAgICAgICAgICAgICAgICAgICAgICAgIHJldHVybiBUcnVlCiAgICAgICAgICAgIHJldHVybiBGYWxzZQoKICAgICMgU2luaCBuxrDhu5tjIMSRaSBo4bujcCBs4buHOiBtb2RlPTAgKHThuqV0IGPhuqMpLCBtb2RlPTEgKGNo4buJIMSDbiBxdcOibiksIG1vZGU9MiAoxINuIHF1w6JuICsgw6FwIHPDoXQgxJHDrWNoKQogICAgZGVmIGdlbihzLCBtb2RlKToKICAgICAgICByZXMgPSBbXQogICAgICAgIGxvID0gTE9bc10KICAgICAgICBoaSA9IEhJW3NdCiAgICAgICAgZWxvID0gTE9bMSAtIHNdCiAgICAgICAgZWhpID0gSElbMSAtIHNdCiAgICAgICAgbXRhYiA9IE1UQUJbc10KICAgICAgICBnc2V0ID0gR09BTFtzXQogICAgICAgIGVnc2V0ID0gR09BTFsxIC0gc10KICAgICAgICBmb3IgYyBpbiByYW5nZShsbywgaGkgKyAxKToKICAgICAgICAgICAgcCA9IHBzW2NdCiAgICAgICAgICAgIGlmIHAgPCAwOgogICAgICAgICAgICAgICAgY29udGludWUKICAgICAgICAgICAgdCA9IHRwW2NdCiAgICAgICAgICAgIGJ0ID0gQlRbdF0KICAgICAgICAgICAgb25fZ29hbCA9IChnb2FsX21vZGUgPT0gMSBhbmQgcCBpbiBnc2V0KQogICAgICAgICAgICBmb3IgcSwgZndfYiwgaF9peCwgaXNfbmIgaW4gbXRhYltwXToKICAgICAgICAgICAgICAgIHYgPSBib2FyZFtxXQogICAgICAgICAgICAgICAgaWYgdiA9PSAwOgogICAgICAgICAgICAgICAgICAgIGlmIG1vZGUgPT0gMDoKICAgICAgICAgICAgICAgICAgICAgICAgaCA9IEhJU1RbaF9peF0KICAgICAgICAgICAgICAgICAgICAgICAgcGVuX2xlYXZlID0gLTM1IGlmIChvbl9nb2FsIGFuZCBxIG5vdCBpbiBnc2V0KSBlbHNlIDAKICAgICAgICAgICAgICAgICAgICAgICAgcmVzLmFwcGVuZCgoZndfYiArIHBlbl9sZWF2ZSArIChoIGlmIGggPCA3MiBlbHNlIDcyKSwgYywgcCwgcSwgMCkpCiAgICAgICAgICAgICAgICAgICAgZWxpZiBtb2RlID09IDIgYW5kIGlzX25iOgogICAgICAgICAgICAgICAgICAgICAgICBmb3Igb2ZmIGluIE9GRlM6CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBncSA9IHEgKyBvZmYKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmIGdxIGluIGdzZXQ6CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgdmcgPSBib2FyZFtncV0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZiB2ZyA9PSAwIG9yIChlbG8gPD0gdmcgPD0gZWhpIGFuZCBidFt0cFt2Z11dKToKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcmVzLmFwcGVuZCgoODIwICsgZndfYiwgYywgcCwgcSwgMCkpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJyZWFrCiAgICAgICAgICAgICAgICBlbGlmIGVsbyA8PSB2IDw9IGVoaToKICAgICAgICAgICAgICAgICAgICBpZiBidFt0cFt2XV06CiAgICAgICAgICAgICAgICAgICAgICAgIGJvbnVzID0gOTAgaWYgKHEgaW4gZWdzZXQgb3IgRDFbcV0gPD0gMikgZWxzZSAwCiAgICAgICAgICAgICAgICAgICAgICAgIHJlcy5hcHBlbmQoKDEwNTAgKyBmd19iICsgYm9udXMsIGMsIHAsIHEsIHYpKQogICAgICAgIHJldHVybiByZXMKCiAgICAjIEjDoG0gbMaw4bujbmcgZ2nDoSB0aOG6vyBj4budIHTEqW5oIHThu6sgZ8OzYyBuaMOsbiBwaGUgcwogICAgZGVmIGV2YWx1YXRlX3JhdyhzKToKICAgICAgICBBX3AgPSBbXQogICAgICAgIEFfdCA9IFtdCiAgICAgICAgQl9wID0gW10KICAgICAgICBCX3QgPSBbXQogICAgICAgIGNBMCA9IGNBMSA9IGNBMiA9IDAKICAgICAgICBjQjAgPSBjQjEgPSBjQjIgPSAwCiAgICAgICAgZm9yIGMgaW4gcmFuZ2UoQUxMWV9MTywgQUxMWV9ISSArIDEpOgogICAgICAgICAgICBwID0gcHNbY10KICAgICAgICAgICAgaWYgcCA+PSAwOgogICAgICAgICAgICAgICAgdCA9IHRwW2NdCiAgICAgICAgICAgICAgICBBX3AuYXBwZW5kKHApCiAgICAgICAgICAgICAgICBBX3QuYXBwZW5kKHQpCiAgICAgICAgICAgICAgICBpZiB0ID09IDA6CiAgICAgICAgICAgICAgICAgICAgY0EwICs9IDEKICAgICAgICAgICAgICAgIGVsaWYgdCA9PSAxOgogICAgICAgICAgICAgICAgICAgIGNBMSArPSAxCiAgICAgICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgICAgIGNBMiArPSAxCiAgICAgICAgZm9yIGMgaW4gcmFuZ2UoT1BQX0xPLCBPUFBfSEkgKyAxKToKICAgICAgICAgICAgcCA9IHBzW2NdCiAgICAgICAgICAgIGlmIHAgPj0gMDoKICAgICAgICAgICAgICAgIHQgPSB0cFtjXQogICAgICAgICAgICAgICAgQl9wLmFwcGVuZChwKQogICAgICAgICAgICAgICAgQl90LmFwcGVuZCh0KQogICAgICAgICAgICAgICAgaWYgdCA9PSAwOgogICAgICAgICAgICAgICAgICAgIGNCMCArPSAxCiAgICAgICAgICAgICAgICBlbGlmIHQgPT0gMToKICAgICAgICAgICAgICAgICAgICBjQjEgKz0gMQogICAgICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgICAgICBjQjIgKz0gMQoKICAgICAgICBuYSA9IGxlbihBX3ApCiAgICAgICAgbmIgPSBsZW4oQl9wKQogICAgICAgIGlmIG5hID09IDA6CiAgICAgICAgICAgIHJldHVybiAtV0lOICsgMTAwIGlmIHMgPT0gMCBlbHNlIFdJTiAtIDEwMAogICAgICAgIGlmIG5iID09IDA6CiAgICAgICAgICAgIHJldHVybiBXSU4gLSAxMDAgaWYgcyA9PSAwIGVsc2UgLVdJTiArIDEwMAoKICAgICAgICBjQSA9IChjQTAsIGNBMSwgY0EyKQogICAgICAgIGNCID0gKGNCMCwgY0IxLCBjQjIpCgogICAgICAgICMgSMahbiBxdcOibiB2w6AgbOG7o2kgdGjhur8gdHV54buHdCDEkeG7kWkga2hpIMSR4buLY2ggbeG6pXQgc+G6oWNoIGxv4bqhaSBxdcOibiBraOG6r2MgY2jhur8KICAgICAgICB2ID0gMTA1MCAqIChuYSAtIG5iKSArIDMyMDAgKiAobmEgLSBuYikgLy8gKG5hICsgbmIpCgogICAgICAgIGZvciB0IGluICgwLCAxLCAyKToKICAgICAgICAgICAgcHJlZCA9IFBSRURbdF0KICAgICAgICAgICAgcHJleSA9IFBSRVlbdF0KICAgICAgICAgICAgY2EgPSBjQVt0XQogICAgICAgICAgICBjYiA9IGNCW3RdCiAgICAgICAgICAgIGlmIGNhOgogICAgICAgICAgICAgICAgaWYgY0JbcHJlZF0gPT0gMDoKICAgICAgICAgICAgICAgICAgICB2ICs9IGNhICogKDUwMCBpZiBjQlt0XSA9PSAwIGVsc2UgMzYwKQogICAgICAgICAgICAgICAgZWxpZiBjQltwcmVkXSA9PSAxIGFuZCBjQVtwcmV5XSA+IDA6CiAgICAgICAgICAgICAgICAgICAgdiArPSBjYSAqIEVMSU0xCiAgICAgICAgICAgICAgICBlbGlmIEVMSU0yIGFuZCBjQltwcmVkXSA9PSAyIGFuZCBjQVtwcmV5XSA+PSAyOgogICAgICAgICAgICAgICAgICAgIHYgKz0gY2EgKiBFTElNMgogICAgICAgICAgICAgICAgdiArPSBjYSAqICg4MCAqIGNCW3ByZXldIGlmIGNCW3ByZXldIGVsc2UgLTUwKQogICAgICAgICAgICBpZiBjYjoKICAgICAgICAgICAgICAgIGlmIGNBW3ByZWRdID09IDA6CiAgICAgICAgICAgICAgICAgICAgdiAtPSBjYiAqICg1MDAgaWYgY0FbdF0gPT0gMCBlbHNlIDM2MCkKICAgICAgICAgICAgICAgIGVsaWYgY0FbcHJlZF0gPT0gMSBhbmQgY0JbcHJleV0gPiAwOgogICAgICAgICAgICAgICAgICAgIHYgLT0gY2IgKiBFTElNMQogICAgICAgICAgICAgICAgZWxpZiBFTElNMiBhbmQgY0FbcHJlZF0gPT0gMiBhbmQgY0JbcHJleV0gPj0gMjoKICAgICAgICAgICAgICAgICAgICB2IC09IGNiICogRUxJTTIKICAgICAgICAgICAgICAgIHYgLT0gY2IgKiAoODAgKiBjQVtwcmV5XSBpZiBjQVtwcmV5XSBlbHNlIC01MCkKCiAgICAgICAgIyDEkGnhu4NtIGNoaeG6v20gxJHDs25nIMSR4buTbmcgdGjhu51pIGtoaSBi4bqjbiDEkeG7kyBi4bqtdCBnb2FsTW9kZSA9PSAxCiAgICAgICAgaWYgZ29hbF9tb2RlID09IDE6CiAgICAgICAgICAgIG9jYzAgPSAwCiAgICAgICAgICAgIGZvciBnIGluIEdPQUxbMF06CiAgICAgICAgICAgICAgICBpZiBBTExZX0xPIDw9IGJvYXJkW2ddIDw9IEFMTFlfSEk6CiAgICAgICAgICAgICAgICAgICAgb2NjMCArPSAxCiAgICAgICAgICAgIG9jYzEgPSAwCiAgICAgICAgICAgIGZvciBnIGluIEdPQUxbMV06CiAgICAgICAgICAgICAgICBpZiBPUFBfTE8gPD0gYm9hcmRbZ10gPD0gT1BQX0hJOgogICAgICAgICAgICAgICAgICAgIG9jYzEgKz0gMQogICAgICAgICAgICBpZiBvY2MwID09IGxlbihHT0FMWzBdKToKICAgICAgICAgICAgICAgIHJldHVybiBXSU4gLSA1MCBpZiBzID09IDAgZWxzZSAtV0lOICsgNTAKICAgICAgICAgICAgaWYgb2NjMSA9PSBsZW4oR09BTFsxXSk6CiAgICAgICAgICAgICAgICByZXR1cm4gLVdJTiArIDUwIGlmIHMgPT0gMCBlbHNlIFdJTiAtIDUwCiAgICAgICAgICAgIHYgKz0gOTAwICogKG9jYzAgLSBvY2MxKQoKICAgICAgICBoYSA9IFtNQVhfRF0gKiBuYQogICAgICAgIHBhID0gW01BWF9EXSAqIG5hCiAgICAgICAgbWEgPSBbTUFYX0QgKiAyXSAqIG5hCiAgICAgICAgaW50YSA9IFs5OTldICogbmEKICAgICAgICBoYiA9IFtNQVhfRF0gKiBuYgogICAgICAgIHBiID0gW01BWF9EXSAqIG5iCiAgICAgICAgbWIgPSBbTUFYX0QgKiAyXSAqIG5iCiAgICAgICAgaW50YiA9IFs5OTldICogbmIKCiAgICAgICAgZm9yIGkgaW4gcmFuZ2UobmEpOgogICAgICAgICAgICBwID0gQV9wW2ldCiAgICAgICAgICAgIHQgPSBBX3RbaV0KICAgICAgICAgICAgZDBwID0gRDBbcF0KICAgICAgICAgICAgcm93ID0gRFRbcF0KICAgICAgICAgICAgbXJvdyA9IE1EVFtwXQogICAgICAgICAgICBidCA9IEJUW3RdCiAgICAgICAgICAgIGZvciBqIGluIHJhbmdlKG5iKToKICAgICAgICAgICAgICAgIHEgPSBCX3Bbal0KICAgICAgICAgICAgICAgIHUgPSBCX3Rbal0KICAgICAgICAgICAgICAgIGQwcSA9IEQwW3FdCiAgICAgICAgICAgICAgICBkMXEgPSBEMVtxXQogICAgICAgICAgICAgICAgaWYgdSA9PSB0OgogICAgICAgICAgICAgICAgICAgIGlmIGQwcSA8PSBkMHAgYW5kIGQwcSA8IGludGFbaV06CiAgICAgICAgICAgICAgICAgICAgICAgIGludGFbaV0gPSBkMHEKICAgICAgICAgICAgICAgICAgICBpZiBEMVtwXSA8PSBkMXEgYW5kIEQxW3BdIDwgaW50YltqXToKICAgICAgICAgICAgICAgICAgICAgICAgaW50YltqXSA9IEQxW3BdCiAgICAgICAgICAgICAgICAgICAgY29udGludWUKICAgICAgICAgICAgICAgIGQgPSByb3dbcV0KICAgICAgICAgICAgICAgIG1kID0gbXJvd1txXQogICAgICAgICAgICAgICAgaWYgYnRbdV06CiAgICAgICAgICAgICAgICAgICAgaWYgZCA8IHBhW2ldOgogICAgICAgICAgICAgICAgICAgICAgICBwYVtpXSA9IGQKICAgICAgICAgICAgICAgICAgICBpZiBtZCA8IG1hW2ldOgogICAgICAgICAgICAgICAgICAgICAgICBtYVtpXSA9IG1kCiAgICAgICAgICAgICAgICAgICAgaWYgZCA8IGhiW2pdOgogICAgICAgICAgICAgICAgICAgICAgICBoYltqXSA9IGQKICAgICAgICAgICAgICAgICAgICBpZiBEMVtwXSA8PSBkMXEgKyAxIGFuZCBEMVtwXSA8IGludGJbal06CiAgICAgICAgICAgICAgICAgICAgICAgIGludGJbal0gPSBEMVtwXQogICAgICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgICAgICBpZiBkIDwgaGFbaV06CiAgICAgICAgICAgICAgICAgICAgICAgIGhhW2ldID0gZAogICAgICAgICAgICAgICAgICAgIGlmIGQgPCBwYltqXToKICAgICAgICAgICAgICAgICAgICAgICAgcGJbal0gPSBkCiAgICAgICAgICAgICAgICAgICAgaWYgbWQgPCBtYltqXToKICAgICAgICAgICAgICAgICAgICAgICAgbWJbal0gPSBtZAogICAgICAgICAgICAgICAgICAgIGlmIGQwcSA8PSBkMHAgKyAxIGFuZCBkMHEgPCBpbnRhW2ldOgogICAgICAgICAgICAgICAgICAgICAgICBpbnRhW2ldID0gZDBxCgogICAgICAgIGFkdjAgPSAwCiAgICAgICAgdGhyMCA9IDAKICAgICAgICBkZzAgPSAwCiAgICAgICAgaHVudDAgPSAwCiAgICAgICAgaGFuZzAgPSAwCiAgICAgICAgYXdheV9ndWFyZF9iID0gWzAsIDAsIDBdCiAgICAgICAgZm9yIGogaW4gcmFuZ2UobmIpOgogICAgICAgICAgICBpZiBEMFtCX3Bbal1dIDw9IDI6CiAgICAgICAgICAgICAgICBhd2F5X2d1YXJkX2JbQl90W2pdXSA9IDEKCiAgICAgICAgbWF4X3Vuc3RvcCA9IGxlbihVTlNUT1BfUlQpIC0gMQogICAgICAgIG1heF9ydCA9IGxlbihSVCkgLSAxCiAgICAgICAgaHVudF9yYW5nZSA9IG1heCgxMCwgKFcgKyBIKSAvLyAyICsgMikKCiAgICAgICAgZm9yIGkgaW4gcmFuZ2UobmEpOgogICAgICAgICAgICBwID0gQV9wW2ldCiAgICAgICAgICAgIHQgPSBBX3RbaV0KICAgICAgICAgICAgYXAgPSBBRFYwW3BdCiAgICAgICAgICAgIGlmIGNCW1BSRURbdF1dID09IDA6CiAgICAgICAgICAgICAgICBhcCArPSBhcCA+PiAxCiAgICAgICAgICAgIGlmIGF3YXlfZ3VhcmRfYltQUkVZW3RdXToKICAgICAgICAgICAgICAgIGFwICs9IG1heCgwLCBodW50X3JhbmdlIC0gRDBbcF0pICogMwogICAgICAgICAgICBhZHYwICs9IGFwCgogICAgICAgICAgICBtcCA9IHBhW2ldCiAgICAgICAgICAgIGlmIG1wIDwgTUFYX0Q6CiAgICAgICAgICAgICAgICBodW50MCArPSBIVyAqIG1heCgwLCBodW50X3JhbmdlIC0gbXApICsgbWF4KDAsIGh1bnRfcmFuZ2UgKiAyIC0gbWFbaV0pCiAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICBodW50MCArPSBDRU5URVJbcF0KCiAgICAgICAgICAgIG1oID0gaGFbaV0KICAgICAgICAgICAgaWYgbWggPD0gMzoKICAgICAgICAgICAgICAgIHB0ID0gUFJFWVt0XQogICAgICAgICAgICAgICAgcm93ID0gRFRbcF0KICAgICAgICAgICAgICAgIHByb3QgPSBGYWxzZQogICAgICAgICAgICAgICAgZm9yIGsgaW4gcmFuZ2UobmEpOgogICAgICAgICAgICAgICAgICAgIGlmIEFfdFtrXSA9PSBwdCBhbmQgcm93W0FfcFtrXV0gPD0gMToKICAgICAgICAgICAgICAgICAgICAgICAgcHJvdCA9IFRydWUKICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWsKICAgICAgICAgICAgICAgIGlmIG5vdCBwcm90OgogICAgICAgICAgICAgICAgICAgIGlmIG1oIDw9IDE6CiAgICAgICAgICAgICAgICAgICAgICAgIGRnMCArPSBEUFsxXSArICgxNjAgaWYgcyA9PSAxIGVsc2UgMCkKICAgICAgICAgICAgICAgICAgICAgICAgaGFuZzAgKz0gMQogICAgICAgICAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICAgICAgICAgIGRnMCArPSBEUFttaF0KICAgICAgICAgICAgICAgIGVsaWYgbWggPD0gMjoKICAgICAgICAgICAgICAgICAgICBodW50MCArPSAyNQoKICAgICAgICAgICAgZCA9IEQwW3BdCiAgICAgICAgICAgIGlmIGludGFbaV0gPT0gOTk5OgogICAgICAgICAgICAgICAgaWYgZCA8PSBtYXhfdW5zdG9wOgogICAgICAgICAgICAgICAgICAgIHR2ID0gVU5TVE9QX1JUW2RdCiAgICAgICAgICAgICAgICAgICAgaWYgdHYgPiB0aHIwOgogICAgICAgICAgICAgICAgICAgICAgICB0aHIwID0gdHYKICAgICAgICAgICAgZWxpZiBkIDw9IG1heF9ydDoKICAgICAgICAgICAgICAgIHR2ID0gUlRbZF0KICAgICAgICAgICAgICAgIGlmIG1oIDw9IDIgb3IgaW50YVtpXSA8PSBkOgogICAgICAgICAgICAgICAgICAgIHR2IC8vPSAzCiAgICAgICAgICAgICAgICBpZiB0diA+IHRocjA6CiAgICAgICAgICAgICAgICAgICAgdGhyMCA9IHR2CgogICAgICAgIGlmIGhhbmcwID49IDI6CiAgICAgICAgICAgIGRnMCArPSAzODAgKiAoaGFuZzAgLSAxKQoKICAgICAgICBhZHYxID0gMAogICAgICAgIHRocjEgPSAwCiAgICAgICAgZGcxID0gMAogICAgICAgIGh1bnQxID0gMAogICAgICAgIGhhbmcxID0gMAogICAgICAgIGhvbWVfZ3VhcmRfYSA9IFswLCAwLCAwXQogICAgICAgIGZvciBpIGluIHJhbmdlKG5hKToKICAgICAgICAgICAgaWYgRDFbQV9wW2ldXSA8PSAyOgogICAgICAgICAgICAgICAgaG9tZV9ndWFyZF9hW0FfdFtpXV0gPSAxCgogICAgICAgIGZvciBqIGluIHJhbmdlKG5iKToKICAgICAgICAgICAgcSA9IEJfcFtqXQogICAgICAgICAgICB1ID0gQl90W2pdCiAgICAgICAgICAgIGFxID0gQURWMVtxXQogICAgICAgICAgICBpZiBjQVtQUkVEW3VdXSA9PSAwOgogICAgICAgICAgICAgICAgYXEgKz0gYXEgPj4gMQogICAgICAgICAgICBpZiBob21lX2d1YXJkX2FbUFJFWVt1XV06CiAgICAgICAgICAgICAgICBhcSArPSBtYXgoMCwgaHVudF9yYW5nZSAtIEQxW3FdKSAqIDMKICAgICAgICAgICAgYWR2MSArPSBhcQoKICAgICAgICAgICAgbXAgPSBwYltqXQogICAgICAgICAgICBpZiBtcCA8IE1BWF9EOgogICAgICAgICAgICAgICAgaHVudDEgKz0gSFcgKiBtYXgoMCwgaHVudF9yYW5nZSAtIG1wKSArIG1heCgwLCBodW50X3JhbmdlICogMiAtIG1iW2pdKQogICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgaHVudDEgKz0gQ0VOVEVSW3FdCgogICAgICAgICAgICBtaCA9IGhiW2pdCiAgICAgICAgICAgIGlmIG1oIDw9IDM6CiAgICAgICAgICAgICAgICBwdCA9IFBSRVlbdV0KICAgICAgICAgICAgICAgIHJvdyA9IERUW3FdCiAgICAgICAgICAgICAgICBwcm90ID0gRmFsc2UKICAgICAgICAgICAgICAgIGZvciBrIGluIHJhbmdlKG5iKToKICAgICAgICAgICAgICAgICAgICBpZiBCX3Rba10gPT0gcHQgYW5kIHJvd1tCX3Bba11dIDw9IDE6CiAgICAgICAgICAgICAgICAgICAgICAgIHByb3QgPSBUcnVlCiAgICAgICAgICAgICAgICAgICAgICAgIGJyZWFrCiAgICAgICAgICAgICAgICBpZiBub3QgcHJvdDoKICAgICAgICAgICAgICAgICAgICBpZiBtaCA8PSAxOgogICAgICAgICAgICAgICAgICAgICAgICBkZzEgKz0gRFBbMV0gKyAoMTYwIGlmIHMgPT0gMCBlbHNlIDApCiAgICAgICAgICAgICAgICAgICAgICAgIGhhbmcxICs9IDEKICAgICAgICAgICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgICAgICAgICBkZzEgKz0gRFBbbWhdCiAgICAgICAgICAgICAgICBlbGlmIG1oIDw9IDI6CiAgICAgICAgICAgICAgICAgICAgaHVudDEgKz0gMjUKCiAgICAgICAgICAgIGQgPSBEMVtxXQogICAgICAgICAgICBpZiBpbnRiW2pdID09IDk5OToKICAgICAgICAgICAgICAgIGlmIGQgPD0gbWF4X3Vuc3RvcDoKICAgICAgICAgICAgICAgICAgICB0diA9IFVOU1RPUF9SVFtkXQogICAgICAgICAgICAgICAgICAgIGlmIHR2ID4gdGhyMToKICAgICAgICAgICAgICAgICAgICAgICAgdGhyMSA9IHR2CiAgICAgICAgICAgIGVsaWYgZCA8PSBtYXhfcnQ6CiAgICAgICAgICAgICAgICB0diA9IFJUW2RdCiAgICAgICAgICAgICAgICBpZiBtaCA8PSAyIG9yIGludGJbal0gPD0gZDoKICAgICAgICAgICAgICAgICAgICB0diAvLz0gMwogICAgICAgICAgICAgICAgaWYgdHYgPiB0aHIxOgogICAgICAgICAgICAgICAgICAgIHRocjEgPSB0dgoKICAgICAgICBpZiBoYW5nMSA+PSAyOgogICAgICAgICAgICBkZzEgKz0gMzgwICogKGhhbmcxIC0gMSkKCiAgICAgICAgdiArPSBLICogKGFkdjAgLSBhZHYxKSArICh0aHIwIC0gdGhyMSkgLSAoZGcwIC0gZGcxKSArIChodW50MCAtIGh1bnQxKQoKICAgICAgICAjIFBow7JuZyB0aOG7pyB2w7luZyBj4budIG5ow6AKICAgICAgICBoYXNfdXNlZnVsX2RlZiA9IEZhbHNlCiAgICAgICAgZm9yIGkgaW4gcmFuZ2UobmEpOgogICAgICAgICAgICBpZiBEMVtBX3BbaV1dIDw9IDIgYW5kIGNCW1BSRVlbQV90W2ldXV0gPiAwOgogICAgICAgICAgICAgICAgaGFzX3VzZWZ1bF9kZWYgPSBUcnVlCiAgICAgICAgICAgICAgICBicmVhawoKICAgICAgICBuZWFyX2NudCA9IDAKICAgICAgICBmb3IgaiBpbiByYW5nZShuYik6CiAgICAgICAgICAgIGQgPSBEMVtCX3Bbal1dCiAgICAgICAgICAgIGlmIGQgPD0gMjoKICAgICAgICAgICAgICAgIHYgLT0gNTIwICogKDMgLSBkKQogICAgICAgICAgICAgICAgbmVhcl9jbnQgKz0gMQogICAgICAgICAgICAgICAgaWYgaW50YltqXSA9PSA5OTk6CiAgICAgICAgICAgICAgICAgICAgdiAtPSA0NTAgKiAoMyAtIGQpCiAgICAgICAgICAgIGVsaWYgZCA9PSAzOgogICAgICAgICAgICAgICAgdiAtPSAxMTAKICAgICAgICAgICAgICAgIGlmIGludGJbal0gPT0gOTk5OgogICAgICAgICAgICAgICAgICAgIHYgLT0gMjIwCiAgICAgICAgICAgIGVsaWYgZCA9PSA0OgogICAgICAgICAgICAgICAgdiAtPSAzNQoKICAgICAgICBpZiBuZWFyX2NudCA+PSAyOgogICAgICAgICAgICB2IC09IDQyMCAqIChuZWFyX2NudCAtIDEpCiAgICAgICAgaWYgbmVhcl9jbnQgPj0gMSBhbmQgbm90IGhhc191c2VmdWxfZGVmOgogICAgICAgICAgICB2IC09IDQyMCAqIG5lYXJfY250CiAgICAgICAgaWYgaGFzX3VzZWZ1bF9kZWY6CiAgICAgICAgICAgIHYgKz0gMTM1ICsgMTA1ICogbmVhcl9jbnQKCiAgICAgICAgcmV0dXJuIHYgaWYgcyA9PSAwIGVsc2UgLXYKCiAgICBldmMgPSB7fQoKICAgIGRlZiBldmFsdWF0ZShzLCBoKToKICAgICAgICByID0gZXZjLmdldChoKQogICAgICAgIGlmIHIgaXMgTm9uZToKICAgICAgICAgICAgciA9IGV2YWx1YXRlX3JhdyhzKQogICAgICAgICAgICBldmNbaF0gPSByCiAgICAgICAgcmV0dXJuIHIKCiAgICAjIFTDrG0ga2nhur9tIHTEqW5oIChRdWllc2NlbmNlIFNlYXJjaCkgZ2nhuqNpIHF1eeG6v3QgY2h14buXaSDEg24gcXXDom4gdsOgIMSRZSBk4buNYSBjaOG6oW0gxJHDrWNoCiAgICBkZWYgcXNlYXJjaChzLCBhbHBoYSwgYmV0YSwgcGx5LCBxZCwgaCk6CiAgICAgICAgbm9kZXNbMF0gKz0gMQogICAgICAgIGlmIChub2Rlc1swXSAmIDYzKSA9PSAwIGFuZCAodGltZS5wcm9jZXNzX3RpbWUoKSA+IGRlYWRsaW5lIG9yIHRpbWUucHJvY2Vzc190aW1lKCkgLSBzdGFydF90aW1lID4gMC44NCk6CiAgICAgICAgICAgIGFib3J0WzBdID0gVHJ1ZQogICAgICAgIGlmIGFib3J0WzBdOgogICAgICAgICAgICByZXR1cm4gMAogICAgICAgIGlmIHdpbnNfbm93KHMpOgogICAgICAgICAgICByZXR1cm4gV0lOIC0gcGx5CiAgICAgICAgbyA9IDEgLSBzCiAgICAgICAgaW5fY2hrID0gd2luc19ub3cobykKICAgICAgICBpZiBpbl9jaGs6CiAgICAgICAgICAgIGlmIHFkID49IDQ6CiAgICAgICAgICAgICAgICByZXR1cm4gLVdJTiArIHBseSArIDEKICAgICAgICAgICAgYWxsX20gPSBnZW4ocywgMCkKICAgICAgICAgICAgZGVmX3NxID0gREVGX1NRW29dCiAgICAgICAgICAgIGV2YXNpb25zID0gW20gZm9yIG0gaW4gYWxsX20gaWYgbVszXSBpbiBkZWZfc3FdCiAgICAgICAgICAgIGlmIG5vdCBldmFzaW9uczoKICAgICAgICAgICAgICAgIHJldHVybiAtV0lOICsgcGx5ICsgMQogICAgICAgICAgICBldmFzaW9ucy5zb3J0KHJldmVyc2U9VHJ1ZSkKICAgICAgICAgICAgYmVzdCA9IC1XSU4gKyBwbHkgKyAxCiAgICAgICAgICAgIGZvciBtIGluIGV2YXNpb25zOgogICAgICAgICAgICAgICAgYyA9IG1bMV0KICAgICAgICAgICAgICAgIHAgPSBtWzJdCiAgICAgICAgICAgICAgICBxID0gbVszXQogICAgICAgICAgICAgICAgY2FwID0gbVs0XQogICAgICAgICAgICAgICAgYm9hcmRbcF0gPSAwCiAgICAgICAgICAgICAgICBib2FyZFtxXSA9IGMKICAgICAgICAgICAgICAgIHBzW2NdID0gcQogICAgICAgICAgICAgICAgaDIgPSBoIF4gWltjXVtwXSBeIFpbY11bcV0gXiBaUwogICAgICAgICAgICAgICAgaWYgY2FwOgogICAgICAgICAgICAgICAgICAgIHBzW2NhcF0gPSAtMQogICAgICAgICAgICAgICAgICAgIGNudFtvXSAtPSAxCiAgICAgICAgICAgICAgICAgICAgaDIgXj0gWltjYXBdW3FdCiAgICAgICAgICAgICAgICBzdGlsbF93ID0gd2luc19ub3cobykKICAgICAgICAgICAgICAgIGlmIG5vdCBzdGlsbF93OgogICAgICAgICAgICAgICAgICAgIGlmIGNhcCBhbmQgY250W29dID09IDA6CiAgICAgICAgICAgICAgICAgICAgICAgIHZhbCA9IFdJTiAtIHBseQogICAgICAgICAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICAgICAgICAgIHZhbCA9IC1xc2VhcmNoKG8sIC1iZXRhLCAtYWxwaGEsIHBseSArIDEsIHFkICsgMSwgaDIpCiAgICAgICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgICAgIHZhbCA9IC1XSU4gKyBwbHkgKyAxCiAgICAgICAgICAgICAgICBpZiBjYXA6CiAgICAgICAgICAgICAgICAgICAgY250W29dICs9IDEKICAgICAgICAgICAgICAgICAgICBwc1tjYXBdID0gcQogICAgICAgICAgICAgICAgYm9hcmRbcV0gPSBjYXAKICAgICAgICAgICAgICAgIGJvYXJkW3BdID0gYwogICAgICAgICAgICAgICAgcHNbY10gPSBwCiAgICAgICAgICAgICAgICBpZiBhYm9ydFswXToKICAgICAgICAgICAgICAgICAgICByZXR1cm4gMAogICAgICAgICAgICAgICAgaWYgdmFsID4gYmVzdDoKICAgICAgICAgICAgICAgICAgICBiZXN0ID0gdmFsCiAgICAgICAgICAgICAgICAgICAgaWYgdmFsID4gYWxwaGE6CiAgICAgICAgICAgICAgICAgICAgICAgIGFscGhhID0gdmFsCiAgICAgICAgICAgICAgICAgICAgICAgIGlmIGFscGhhID49IGJldGE6CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBicmVhawogICAgICAgICAgICByZXR1cm4gYmVzdAoKICAgICAgICBzdGFuZCA9IGV2YWx1YXRlKHMsIGgpCiAgICAgICAgaWYgc3RhbmQgPj0gYmV0YToKICAgICAgICAgICAgcmV0dXJuIHN0YW5kCiAgICAgICAgaWYgc3RhbmQgPiBhbHBoYToKICAgICAgICAgICAgYWxwaGEgPSBzdGFuZAogICAgICAgIGlmIHFkID49IDY6CiAgICAgICAgICAgIHJldHVybiBzdGFuZAoKICAgICAgICBtb3ZlcyA9IGdlbihzLCAyIGlmIHFkID09IDAgZWxzZSAxKQogICAgICAgIGlmIG5vdCBtb3ZlczoKICAgICAgICAgICAgcmV0dXJuIHN0YW5kCiAgICAgICAgbW92ZXMuc29ydChyZXZlcnNlPVRydWUpCiAgICAgICAgZm9yIG0gaW4gbW92ZXM6CiAgICAgICAgICAgIGMgPSBtWzFdCiAgICAgICAgICAgIHAgPSBtWzJdCiAgICAgICAgICAgIHEgPSBtWzNdCiAgICAgICAgICAgIGNhcCA9IG1bNF0KICAgICAgICAgICAgYm9hcmRbcF0gPSAwCiAgICAgICAgICAgIGJvYXJkW3FdID0gYwogICAgICAgICAgICBwc1tjXSA9IHEKICAgICAgICAgICAgaDIgPSBoIF4gWltjXVtwXSBeIFpbY11bcV0gXiBaUwogICAgICAgICAgICBpZiBjYXA6CiAgICAgICAgICAgICAgICBwc1tjYXBdID0gLTEKICAgICAgICAgICAgICAgIGNudFtvXSAtPSAxCiAgICAgICAgICAgICAgICBoMiBePSBaW2NhcF1bcV0KICAgICAgICAgICAgaWYgY2FwIGFuZCBjbnRbb10gPT0gMDoKICAgICAgICAgICAgICAgIHZhbCA9IFdJTiAtIHBseQogICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgdmFsID0gLXFzZWFyY2gobywgLWJldGEsIC1hbHBoYSwgcGx5ICsgMSwgcWQgKyAxLCBoMikKICAgICAgICAgICAgaWYgY2FwOgogICAgICAgICAgICAgICAgY250W29dICs9IDEKICAgICAgICAgICAgICAgIHBzW2NhcF0gPSBxCiAgICAgICAgICAgIGJvYXJkW3FdID0gY2FwCiAgICAgICAgICAgIGJvYXJkW3BdID0gYwogICAgICAgICAgICBwc1tjXSA9IHAKICAgICAgICAgICAgaWYgYWJvcnRbMF06CiAgICAgICAgICAgICAgICByZXR1cm4gMAogICAgICAgICAgICBpZiB2YWwgPiBzdGFuZDoKICAgICAgICAgICAgICAgIHN0YW5kID0gdmFsCiAgICAgICAgICAgICAgICBpZiB2YWwgPiBhbHBoYToKICAgICAgICAgICAgICAgICAgICBhbHBoYSA9IHZhbAogICAgICAgICAgICAgICAgICAgIGlmIGFscGhhID49IGJldGE6CiAgICAgICAgICAgICAgICAgICAgICAgIGJyZWFrCiAgICAgICAgcmV0dXJuIHN0YW5kCgogICAgIyBBbHBoYS1CZXRhIFBWUyBr4bq/dCBo4bujcCBi4bqjbmcgYsSDbSBUVCwgS2lsbGVyIEhldXJpc3RpYyB2w6AgTGF0ZSBNb3ZlIFJlZHVjdGlvbgogICAgZGVmIHNlYXJjaChzLCBkZXB0aCwgYWxwaGEsIGJldGEsIHBseSwgaCk6CiAgICAgICAgbm9kZXNbMF0gKz0gMQogICAgICAgIGlmIChub2Rlc1swXSAmIDYzKSA9PSAwIGFuZCAodGltZS5wcm9jZXNzX3RpbWUoKSA+IGRlYWRsaW5lIG9yIHRpbWUucHJvY2Vzc190aW1lKCkgLSBzdGFydF90aW1lID4gMC44NCk6CiAgICAgICAgICAgIGFib3J0WzBdID0gVHJ1ZQogICAgICAgIGlmIGFib3J0WzBdOgogICAgICAgICAgICByZXR1cm4gMAogICAgICAgIGlmIHdpbnNfbm93KHMpOgogICAgICAgICAgICByZXR1cm4gV0lOIC0gcGx5CiAgICAgICAgbyA9IDEgLSBzCiAgICAgICAgaW5fY2hrID0gd2luc19ub3cobykKICAgICAgICBpZiBkZXB0aCA8PSAwOgogICAgICAgICAgICBpZiBpbl9jaGsgYW5kIHBseSA8IFBMWUxJTToKICAgICAgICAgICAgICAgIGRlcHRoID0gMQogICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgcmV0dXJuIHFzZWFyY2gocywgYWxwaGEsIGJldGEsIHBseSwgMCwgaCkKICAgICAgICBhMCA9IGFscGhhCiAgICAgICAgdHRtID0gTm9uZQogICAgICAgIGUgPSB0dC5nZXQoaCkKICAgICAgICBpZiBlIGlzIG5vdCBOb25lOgogICAgICAgICAgICBlZCwgZWYsIGV2LCBlbSA9IGUKICAgICAgICAgICAgaWYgZXYgPiBXSU4gLSAxMDAwOgogICAgICAgICAgICAgICAgZXYgLT0gcGx5CiAgICAgICAgICAgIGVsaWYgZXYgPCAtV0lOICsgMTAwMDoKICAgICAgICAgICAgICAgIGV2ICs9IHBseQogICAgICAgICAgICB0dG0gPSBlbQogICAgICAgICAgICBpZiBlZCA+PSBkZXB0aDoKICAgICAgICAgICAgICAgIGlmIGVmID09IDA6CiAgICAgICAgICAgICAgICAgICAgcmV0dXJuIGV2CiAgICAgICAgICAgICAgICBpZiBlZiA9PSAxOgogICAgICAgICAgICAgICAgICAgIGlmIGV2ID49IGJldGE6CiAgICAgICAgICAgICAgICAgICAgICAgIHJldHVybiBldgogICAgICAgICAgICAgICAgZWxpZiBldiA8PSBhbHBoYToKICAgICAgICAgICAgICAgICAgICByZXR1cm4gZXYKCiAgICAgICAgbW92ZXMgPSBnZW4ocywgMCkKICAgICAgICBpZiBub3QgbW92ZXM6CiAgICAgICAgICAgIHJldHVybiAtV0lOICsgcGx5ICsgMSBpZiBpbl9jaGsgZWxzZSBldmFsdWF0ZShzLCBoKQogICAgICAgIGlmIGluX2NoazoKICAgICAgICAgICAgZGVmX3NxID0gREVGX1NRW29dCiAgICAgICAgICAgIG1vdmVzID0gW20gZm9yIG0gaW4gbW92ZXMgaWYgbVszXSBpbiBkZWZfc3FdCiAgICAgICAgICAgIGlmIG5vdCBtb3ZlczoKICAgICAgICAgICAgICAgIHJldHVybiAtV0lOICsgcGx5ICsgMQoKICAgICAgICBtb3Zlcy5zb3J0KHJldmVyc2U9VHJ1ZSkKICAgICAgICBrbSA9IEtJTExFUltwbHldIGlmIHBseSA8IDY0IGVsc2UgTm9uZQogICAgICAgIGlmIGttIGlzIG5vdCBOb25lIG9yIHR0bSBpcyBub3QgTm9uZToKICAgICAgICAgICAgZm9yIGkgaW4gcmFuZ2UobGVuKG1vdmVzKSk6CiAgICAgICAgICAgICAgICBtID0gbW92ZXNbaV0KICAgICAgICAgICAgICAgIGlmIHR0bSBpcyBub3QgTm9uZSBhbmQgbVsxXSA9PSB0dG1bMF0gYW5kIG1bMl0gPT0gdHRtWzFdIGFuZCBtWzNdID09IHR0bVsyXToKICAgICAgICAgICAgICAgICAgICBpZiBpOgogICAgICAgICAgICAgICAgICAgICAgICBtb3Zlcy5pbnNlcnQoMCwgbW92ZXMucG9wKGkpKQogICAgICAgICAgICAgICAgICAgIGJyZWFrCiAgICAgICAgICAgIGlmIGttIGlzIG5vdCBOb25lOgogICAgICAgICAgICAgICAgZm9yIGkgaW4gcmFuZ2UoMSwgbGVuKG1vdmVzKSk6CiAgICAgICAgICAgICAgICAgICAgbSA9IG1vdmVzW2ldCiAgICAgICAgICAgICAgICAgICAgaWYgbVsxXSA9PSBrbVswXSBhbmQgbVsyXSA9PSBrbVsxXSBhbmQgbVszXSA9PSBrbVsyXToKICAgICAgICAgICAgICAgICAgICAgICAgbW92ZXMuaW5zZXJ0KDEgaWYgdHRtIGlzIG5vdCBOb25lIGVsc2UgMCwgbW92ZXMucG9wKGkpKQogICAgICAgICAgICAgICAgICAgICAgICBicmVhawoKICAgICAgICBiZXN0ID0gLVdJTiArIHBseSArIDEgaWYgaW5fY2hrIGVsc2UgLUlORgogICAgICAgIGJtID0gTm9uZQogICAgICAgIGlkeCA9IDAKICAgICAgICBuYl9zZXQgPSBERUZfU1Fbc10KICAgICAgICBmb3IgbSBpbiBtb3ZlczoKICAgICAgICAgICAgYyA9IG1bMV0KICAgICAgICAgICAgcCA9IG1bMl0KICAgICAgICAgICAgcSA9IG1bM10KICAgICAgICAgICAgY2FwID0gbVs0XQogICAgICAgICAgICBib2FyZFtwXSA9IDAKICAgICAgICAgICAgYm9hcmRbcV0gPSBjCiAgICAgICAgICAgIHBzW2NdID0gcQogICAgICAgICAgICBoMiA9IGggXiBaW2NdW3BdIF4gWltjXVtxXSBeIFpTCiAgICAgICAgICAgIGlmIGNhcDoKICAgICAgICAgICAgICAgIHBzW2NhcF0gPSAtMQogICAgICAgICAgICAgICAgY250W29dIC09IDEKICAgICAgICAgICAgICAgIGgyIF49IFpbY2FwXVtxXQoKICAgICAgICAgICAgaWYgaW5fY2hrIGFuZCB3aW5zX25vdyhvKToKICAgICAgICAgICAgICAgIHZhbCA9IC1XSU4gKyBwbHkgKyAxCiAgICAgICAgICAgIGVsaWYgY2FwIGFuZCBjbnRbb10gPT0gMDoKICAgICAgICAgICAgICAgIHZhbCA9IFdJTiAtIHBseQogICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgaWYgaWR4ID09IDA6CiAgICAgICAgICAgICAgICAgICAgdmFsID0gLXNlYXJjaChvLCBkZXB0aCAtIDEsIC1iZXRhLCAtYWxwaGEsIHBseSArIDEsIGgyKQogICAgICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgICAgICByZWQgPSAxIGlmIChpZHggPj0gNCBhbmQgZGVwdGggPj0gMyBhbmQgbm90IGNhcCBhbmQgbm90IGluX2NoayBhbmQgcSBub3QgaW4gbmJfc2V0KSBlbHNlIDAKICAgICAgICAgICAgICAgICAgICBpZiBpZHggPj0gMTIgYW5kIGRlcHRoID49IDUgYW5kIHJlZDoKICAgICAgICAgICAgICAgICAgICAgICAgcmVkID0gMgogICAgICAgICAgICAgICAgICAgIHZhbCA9IC1zZWFyY2gobywgZGVwdGggLSAxIC0gcmVkLCAtYWxwaGEgLSAxLCAtYWxwaGEsIHBseSArIDEsIGgyKQogICAgICAgICAgICAgICAgICAgIGlmIHZhbCA+IGFscGhhIGFuZCBub3QgYWJvcnRbMF06CiAgICAgICAgICAgICAgICAgICAgICAgIHZhbCA9IC1zZWFyY2gobywgZGVwdGggLSAxLCAtYmV0YSwgLWFscGhhLCBwbHkgKyAxLCBoMikKCiAgICAgICAgICAgIGlmIGNhcDoKICAgICAgICAgICAgICAgIGNudFtvXSArPSAxCiAgICAgICAgICAgICAgICBwc1tjYXBdID0gcQogICAgICAgICAgICBib2FyZFtxXSA9IGNhcAogICAgICAgICAgICBib2FyZFtwXSA9IGMKICAgICAgICAgICAgcHNbY10gPSBwCiAgICAgICAgICAgIGlmIGFib3J0WzBdOgogICAgICAgICAgICAgICAgcmV0dXJuIDAKICAgICAgICAgICAgaWYgdmFsID4gYmVzdDoKICAgICAgICAgICAgICAgIGJlc3QgPSB2YWwKICAgICAgICAgICAgICAgIGJtID0gKGMsIHAsIHEpCiAgICAgICAgICAgICAgICBpZiB2YWwgPiBhbHBoYToKICAgICAgICAgICAgICAgICAgICBhbHBoYSA9IHZhbAogICAgICAgICAgICAgICAgICAgIGlmIGFscGhhID49IGJldGE6CiAgICAgICAgICAgICAgICAgICAgICAgIGlmIG5vdCBjYXA6CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBISVNUW3AgKiBTSVpFICsgcV0gKz0gZGVwdGggKiBkZXB0aAogICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYgcGx5IDwgNjQ6CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgS0lMTEVSW3BseV0gPSBibQogICAgICAgICAgICAgICAgICAgICAgICBicmVhawogICAgICAgICAgICBpZHggKz0gMQoKICAgICAgICBzdiA9IGJlc3QKICAgICAgICBpZiBzdiA+IFdJTiAtIDEwMDA6CiAgICAgICAgICAgIHN2ICs9IHBseQogICAgICAgIGVsaWYgc3YgPCAtV0lOICsgMTAwMDoKICAgICAgICAgICAgc3YgLT0gcGx5CiAgICAgICAgaWYgYmVzdCA8PSBhMDoKICAgICAgICAgICAgZmwgPSAyCiAgICAgICAgZWxpZiBiZXN0ID49IGJldGE6CiAgICAgICAgICAgIGZsID0gMQogICAgICAgIGVsc2U6CiAgICAgICAgICAgIGZsID0gMAogICAgICAgIHR0W2hdID0gKGRlcHRoLCBmbCwgc3YsIGJtKQogICAgICAgIHJldHVybiBiZXN0CgogICAgIyBDaOG7jW4gbsaw4bubYyDEkWkgdOG7kWkgxrB1IGLhurFuZyBJdGVyYXRpdmUgRGVlcGVuaW5nIHThuqFpIG7DunQgZ+G7kWMKICAgIGRlZiBkZWNpZGUoKToKICAgICAgICByb290ID0gZ2VuKDAsIDApCiAgICAgICAgaWYgbm90IHJvb3Q6CiAgICAgICAgICAgIHJldHVybiAoMCwgMCkKCiAgICAgICAgIyBLaeG7g20gdHJhIG7GsOG7m2MgdGjhuq9uZyBuZ2F5IGzhuq1wIHThu6ljCiAgICAgICAgZ3NldDAgPSBHT0FMWzBdCiAgICAgICAgZm9yIG0gaW4gcm9vdDoKICAgICAgICAgICAgYzAgPSBtWzFdCiAgICAgICAgICAgIHAwID0gbVsyXQogICAgICAgICAgICBxMCA9IG1bM10KICAgICAgICAgICAgY2FwMCA9IG1bNF0KICAgICAgICAgICAgaWYgY2FwMCBhbmQgY250WzFdID09IDE6CiAgICAgICAgICAgICAgICByZXR1cm4gKHBpZF9vZltjMF0sIERJUk5bcTAgLSBwMF0pCiAgICAgICAgICAgIGlmIHEwIGluIGdzZXQwOgogICAgICAgICAgICAgICAgaWYgZ29hbF9tb2RlID09IDA6CiAgICAgICAgICAgICAgICAgICAgcmV0dXJuIChwaWRfb2ZbYzBdLCBESVJOW3EwIC0gcDBdKQogICAgICAgICAgICAgICAgZWxpZiBhbGwoKGcgPT0gcTAgb3IgKEFMTFlfTE8gPD0gYm9hcmRbZ10gPD0gQUxMWV9ISSBhbmQgZyAhPSBwMCkpIGZvciBnIGluIGdzZXQwKToKICAgICAgICAgICAgICAgICAgICByZXR1cm4gKHBpZF9vZltjMF0sIERJUk5bcTAgLSBwMF0pCgogICAgICAgICMgTuG6v3UgxJHhu4tjaCDEkWFuZyBk4buNYSBjaOG6oW0gxJHDrWNoIOG7nyBsxrDhu6N0IGvhur8sIGzhu41jIGPDoWMgbsaw4bubYyBwaMOybmcgdGjhu6cgYuG6r3QgYnXhu5ljCiAgICAgICAgaWYgd2luc19ub3coMSk6CiAgICAgICAgICAgIHNhZmUgPSBbXQogICAgICAgICAgICBmb3IgbSBpbiByb290OgogICAgICAgICAgICAgICAgYzAgPSBtWzFdCiAgICAgICAgICAgICAgICBwMCA9IG1bMl0KICAgICAgICAgICAgICAgIHEwID0gbVszXQogICAgICAgICAgICAgICAgY2FwMCA9IG1bNF0KICAgICAgICAgICAgICAgIGJvYXJkW3AwXSA9IDAKICAgICAgICAgICAgICAgIGJvYXJkW3EwXSA9IGMwCiAgICAgICAgICAgICAgICBwc1tjMF0gPSBxMAogICAgICAgICAgICAgICAgaWYgY2FwMDoKICAgICAgICAgICAgICAgICAgICBwc1tjYXAwXSA9IC0xCiAgICAgICAgICAgICAgICAgICAgY250WzFdIC09IDEKICAgICAgICAgICAgICAgIGlmIG5vdCB3aW5zX25vdygxKToKICAgICAgICAgICAgICAgICAgICBzYWZlLmFwcGVuZChtKQogICAgICAgICAgICAgICAgaWYgY2FwMDoKICAgICAgICAgICAgICAgICAgICBjbnRbMV0gKz0gMQogICAgICAgICAgICAgICAgICAgIHBzW2NhcDBdID0gcTAKICAgICAgICAgICAgICAgIGJvYXJkW3EwXSA9IGNhcDAKICAgICAgICAgICAgICAgIGJvYXJkW3AwXSA9IGMwCiAgICAgICAgICAgICAgICBwc1tjMF0gPSBwMAogICAgICAgICAgICBpZiBzYWZlOgogICAgICAgICAgICAgICAgcm9vdCA9IHNhZmUKCiAgICAgICAgaWYgbGVuKHJvb3QpID09IDE6CiAgICAgICAgICAgIHJldHVybiAocGlkX29mW3Jvb3RbMF1bMV1dLCBESVJOW3Jvb3RbMF1bM10gLSByb290WzBdWzJdXSkKCiAgICAgICAgaDAgPSAwCiAgICAgICAgZm9yIGMgaW4gcmFuZ2UoMSwgT1BQX0hJICsgMSk6CiAgICAgICAgICAgIGlmIHBzW2NdID49IDA6CiAgICAgICAgICAgICAgICBoMCBePSBaW2NdW3BzW2NdXQoKICAgICAgICBzZWVuID0gbWVtby5zZXRkZWZhdWx0KCdzZWVuJywge30pCiAgICAgICAgY2ZnID0gbWVtby5zZXRkZWZhdWx0KCdjZmcnLCB7fSkKICAgICAgICBwZW5fdW5pdCA9IDEzMCArIDIgKiBtaW4odHVybiwgMjAwKQogICAgICAgIGNmZ191bml0ID0gKDQ1ICsgNCAqIHN0YWcpICogKDAuMjUgaWYgYmVoaW5kIGVsc2UgMS4wKQogICAgICAgIGh1bnRfcmFuZ2UgPSBtYXgoMTAsIChXICsgSCkgLy8gMiArIDIpCgogICAgICAgIG9yZGVyID0gW10KICAgICAgICBmb3IgbSBpbiByb290OgogICAgICAgICAgICBjID0gbVsxXQogICAgICAgICAgICBwID0gbVsyXQogICAgICAgICAgICBxID0gbVszXQogICAgICAgICAgICBjYXAgPSBtWzRdCiAgICAgICAgICAgIHQgPSB0cFtjXQogICAgICAgICAgICBwcmVkX3QgPSBQUkVEW3RdCiAgICAgICAgICAgIHByZXlfdCA9IFBSRVlbdF0KICAgICAgICAgICAgcm9sZSA9IHJvbGVzLmdldChjLCAnSFVOVEVSJykKICAgICAgICAgICAgdGIgPSBtWzBdICogMTAKICAgICAgICAgICAgaWYgY2FwOgogICAgICAgICAgICAgICAgdGIgKz0gNTAwMAoKICAgICAgICAgICAgbWluX3ByZWRfcCA9IDk5OQogICAgICAgICAgICBtaW5fcHJlZF9xID0gOTk5CiAgICAgICAgICAgIG1pbl9wcmV5X3EgPSA5OTkKICAgICAgICAgICAgcm93X3AgPSBEVFtwXQogICAgICAgICAgICByb3dfcSA9IERUW3FdCiAgICAgICAgICAgIGZvciBlYyBpbiByYW5nZShPUFBfTE8sIE9QUF9ISSArIDEpOgogICAgICAgICAgICAgICAgZXAgPSBwc1tlY10KICAgICAgICAgICAgICAgIGlmIGVwID49IDAgYW5kIGVjICE9IGNhcDoKICAgICAgICAgICAgICAgICAgICBldCA9IHRwW2VjXQogICAgICAgICAgICAgICAgICAgIGlmIGV0ID09IHByZWRfdDoKICAgICAgICAgICAgICAgICAgICAgICAgaWYgcm93X3BbZXBdIDwgbWluX3ByZWRfcDoKICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1pbl9wcmVkX3AgPSByb3dfcFtlcF0KICAgICAgICAgICAgICAgICAgICAgICAgaWYgcm93X3FbZXBdIDwgbWluX3ByZWRfcToKICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1pbl9wcmVkX3EgPSByb3dfcVtlcF0KICAgICAgICAgICAgICAgICAgICBlbGlmIGV0ID09IHByZXlfdDoKICAgICAgICAgICAgICAgICAgICAgICAgaWYgcm93X3FbZXBdIDwgbWluX3ByZXlfcToKICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1pbl9wcmV5X3EgPSByb3dfcVtlcF0KCiAgICAgICAgICAgIGlmIG1pbl9wcmVkX3AgPT0gMSBhbmQgbWluX3ByZWRfcSA+IDE6CiAgICAgICAgICAgICAgICB0YiArPSAzNTAKICAgICAgICAgICAgaWYgbWluX3ByZWRfcSA9PSAxOgogICAgICAgICAgICAgICAgdGIgLT0gNjAwCgogICAgICAgICAgICBpZiByb2xlID09ICdSVU5ORVInOgogICAgICAgICAgICAgICAgdGIgKz0gKEQwW3BdIC0gRDBbcV0pICogNDUgKyAoQURWMFtxXSAtIEFEVjBbcF0pICogMjAKICAgICAgICAgICAgZWxpZiByb2xlID09ICdERUZFTkRFUic6CiAgICAgICAgICAgICAgICB0YiArPSAoRDFbcF0gLSBEMVtxXSkgKiAzNQogICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgdGIgKz0gbWF4KDAsIGh1bnRfcmFuZ2UgLSBtaW5fcHJleV9xKSAqIDI1CiAgICAgICAgICAgIG9yZGVyLmFwcGVuZCgodGIsIG0pKQogICAgICAgIG9yZGVyLnNvcnQocmV2ZXJzZT1UcnVlKQogICAgICAgIG9yZGVyID0gW3hbMV0gZm9yIHggaW4gb3JkZXJdCgogICAgICAgICMgUGjhuqF0IG5o4bq5IGPDoWMgdGjhur8gY+G7nSBs4bq3cCBs4bqhaSDEkeG7gyB0csOhbmggxJFpIHF14bqpbiBxdWFuaAogICAgICAgIHBlbnMgPSB7fQogICAgICAgIGZvciBtIGluIG9yZGVyOgogICAgICAgICAgICBjID0gbVsxXQogICAgICAgICAgICBwID0gbVsyXQogICAgICAgICAgICBxID0gbVszXQogICAgICAgICAgICBjYXAgPSBtWzRdCiAgICAgICAgICAgIGJvYXJkW3BdID0gMAogICAgICAgICAgICBib2FyZFtxXSA9IGMKICAgICAgICAgICAgcHNbY10gPSBxCiAgICAgICAgICAgIGlmIGNhcDoKICAgICAgICAgICAgICAgIHBzW2NhcF0gPSAtMQogICAgICAgICAgICBrZXkgPSB0dXBsZShwcykKICAgICAgICAgICAgY2sgPSB0dXBsZShwc1tBTExZX0xPOkFMTFlfSEkgKyAxXSkKICAgICAgICAgICAgaWYgY2FwOgogICAgICAgICAgICAgICAgcHNbY2FwXSA9IHEKICAgICAgICAgICAgYm9hcmRbcV0gPSBjYXAKICAgICAgICAgICAgYm9hcmRbcF0gPSBjCiAgICAgICAgICAgIHBzW2NdID0gcAogICAgICAgICAgICBwZW5zWyhjLCBwLCBxKV0gPSBtaW4oNzUwLCBpbnQocGVuX3VuaXQgKiBzZWVuLmdldChrZXksIDApICsgY2ZnX3VuaXQgKiBjZmcuZ2V0KGNrLCAwKSkpCgogICAgICAgIGJlc3RfbW92ZSA9IG9yZGVyWzBdCiAgICAgICAgZm9yIGRlcHRoIGluIHJhbmdlKDEsIDQyKToKICAgICAgICAgICAgYmVzdF9hZGogPSAtSU5GCiAgICAgICAgICAgIGN1cl9iZXN0ID0gTm9uZQogICAgICAgICAgICBkb25lID0gMAogICAgICAgICAgICB2YWxzID0gW10KICAgICAgICAgICAgZm9yIG0gaW4gb3JkZXI6CiAgICAgICAgICAgICAgICBpZiB0aW1lLnByb2Nlc3NfdGltZSgpIC0gc3RhcnRfdGltZSA+IDAuODQ6CiAgICAgICAgICAgICAgICAgICAgYWJvcnRbMF0gPSBUcnVlCiAgICAgICAgICAgICAgICAgICAgYnJlYWsKICAgICAgICAgICAgICAgIGMgPSBtWzFdCiAgICAgICAgICAgICAgICBwID0gbVsyXQogICAgICAgICAgICAgICAgcSA9IG1bM10KICAgICAgICAgICAgICAgIGNhcCA9IG1bNF0KICAgICAgICAgICAgICAgIHBlbiA9IHBlbnNbKGMsIHAsIHEpXQogICAgICAgICAgICAgICAgYXJhdyA9IGJlc3RfYWRqICsgcGVuIGlmIGJlc3RfYWRqID4gLUlORiBlbHNlIC1JTkYKICAgICAgICAgICAgICAgIGJvYXJkW3BdID0gMAogICAgICAgICAgICAgICAgYm9hcmRbcV0gPSBjCiAgICAgICAgICAgICAgICBwc1tjXSA9IHEKICAgICAgICAgICAgICAgIGgyID0gaDAgXiBaW2NdW3BdIF4gWltjXVtxXSBeIFpTCiAgICAgICAgICAgICAgICBpZiBjYXA6CiAgICAgICAgICAgICAgICAgICAgcHNbY2FwXSA9IC0xCiAgICAgICAgICAgICAgICAgICAgY250WzFdIC09IDEKICAgICAgICAgICAgICAgICAgICBoMiBePSBaW2NhcF1bcV0KICAgICAgICAgICAgICAgIHZhbCA9IC1zZWFyY2goMSwgZGVwdGggLSAxLCAtSU5GLCAtYXJhdyBpZiBhcmF3ID4gLUlORiBlbHNlIElORiwgMSwgaDIpCiAgICAgICAgICAgICAgICBpZiBjYXA6CiAgICAgICAgICAgICAgICAgICAgY250WzFdICs9IDEKICAgICAgICAgICAgICAgICAgICBwc1tjYXBdID0gcQogICAgICAgICAgICAgICAgYm9hcmRbcV0gPSBjYXAKICAgICAgICAgICAgICAgIGJvYXJkW3BdID0gYwogICAgICAgICAgICAgICAgcHNbY10gPSBwCiAgICAgICAgICAgICAgICBpZiBhYm9ydFswXToKICAgICAgICAgICAgICAgICAgICBicmVhawogICAgICAgICAgICAgICAgZG9uZSArPSAxCiAgICAgICAgICAgICAgICBhZGogPSB2YWwgLSBwZW4gaWYgdmFsIDwgV0lOIC0gMTAwMCBlbHNlIHZhbAogICAgICAgICAgICAgICAgdmFscy5hcHBlbmQoKGFkaiwgbSkpCiAgICAgICAgICAgICAgICBpZiBhZGogPiBiZXN0X2FkajoKICAgICAgICAgICAgICAgICAgICBiZXN0X2FkaiA9IGFkagogICAgICAgICAgICAgICAgICAgIGN1cl9iZXN0ID0gbQoKICAgICAgICAgICAgaWYgY3VyX2Jlc3QgaXMgbm90IE5vbmUgYW5kIChub3QgYWJvcnRbMF0gb3IgZG9uZSA+PSAxKToKICAgICAgICAgICAgICAgIGJlc3RfbW92ZSA9IGN1cl9iZXN0CiAgICAgICAgICAgICAgICBpZiBub3QgYWJvcnRbMF06CiAgICAgICAgICAgICAgICAgICAgdmFscy5zb3J0KGtleT1sYW1iZGEgejogelswXSwgcmV2ZXJzZT1UcnVlKQogICAgICAgICAgICAgICAgICAgIG9yZGVyID0gW3RfaXRlbVsxXSBmb3IgdF9pdGVtIGluIHZhbHNdCiAgICAgICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgICAgIG9yZGVyLnJlbW92ZShjdXJfYmVzdCkKICAgICAgICAgICAgICAgICAgICBvcmRlci5pbnNlcnQoMCwgY3VyX2Jlc3QpCiAgICAgICAgICAgIGlmIGFib3J0WzBdOgogICAgICAgICAgICAgICAgYnJlYWsKICAgICAgICAgICAgaWYgYmVzdF9hZGogPiBXSU4gLSAxMDAwIG9yIGJlc3RfYWRqIDwgLVdJTiArIDEwMDA6CiAgICAgICAgICAgICAgICBicmVhawogICAgICAgICAgICBpZiB0aW1lLnByb2Nlc3NfdGltZSgpID4gZGVhZGxpbmUgb3IgdGltZS5wcm9jZXNzX3RpbWUoKSAtIHN0YXJ0X3RpbWUgPiAwLjg0OgogICAgICAgICAgICAgICAgYnJlYWsKCiAgICAgICAgYyA9IGJlc3RfbW92ZVsxXQogICAgICAgIHAgPSBiZXN0X21vdmVbMl0KICAgICAgICBxID0gYmVzdF9tb3ZlWzNdCiAgICAgICAgY2FwID0gYmVzdF9tb3ZlWzRdCiAgICAgICAgYm9hcmRbcF0gPSAwCiAgICAgICAgYm9hcmRbcV0gPSBjCiAgICAgICAgcHNbY10gPSBxCiAgICAgICAgaWYgY2FwOgogICAgICAgICAgICBwc1tjYXBdID0gLTEKICAgICAgICBrZXkgPSB0dXBsZShwcykKICAgICAgICBzZWVuW2tleV0gPSBzZWVuLmdldChrZXksIDApICsgMQogICAgICAgIGNrID0gdHVwbGUocHNbQUxMWV9MTzpBTExZX0hJICsgMV0pCiAgICAgICAgY2ZnW2NrXSA9IGNmZy5nZXQoY2ssIDApICsgMQogICAgICAgIHJldHVybiAocGlkX29mW2NdLCBESVJOW3EgLSBwXSkKCiAgICB0cnk6CiAgICAgICAgcmVzID0gZGVjaWRlKCkKICAgIGV4Y2VwdCBFeGNlcHRpb246CiAgICAgICAgIyBOaMOhbmggZOG7sSBwaMOybmcgYW4gdG/DoG4gbuG6v3UgZ+G6t3Agc+G7sSBj4buRIGLhuqV0IG5n4budCiAgICAgICAgcmVzID0gKDAsIDApCiAgICAgICAgYmVzdGsgPSAtSU5GCiAgICAgICAgZGlycyA9ICgoLTEsIDEpLCAoMCwgMSksICgxLCAxKSwgKDEsIDApLCAoMSwgLTEpLCAoMCwgLTEpLCAoLTEsIC0xKSwgKC0xLCAwKSkKICAgICAgICBmb3IgcCBpbiBhbGx5X2xpc3Q6CiAgICAgICAgICAgIGZvciBkIGluIHJhbmdlKDEsIDkpOgogICAgICAgICAgICAgICAgZHgsIGR5ID0gZGlyc1tkIC0gMV0KICAgICAgICAgICAgICAgIG54ID0gcC54ICsgZHgKICAgICAgICAgICAgICAgIG55ID0gcC55ICsgZHkKICAgICAgICAgICAgICAgIGlmIG54IDwgMSBvciBueCA+IFcgb3IgbnkgPCAxIG9yIG55ID4gSCBvciAobngsIG55KSBpbiB3YWxsc194eToKICAgICAgICAgICAgICAgICAgICBjb250aW51ZQogICAgICAgICAgICAgICAgb2sgPSBUcnVlCiAgICAgICAgICAgICAgICBmb3IgYSBpbiBhbGx5X2xpc3Q6CiAgICAgICAgICAgICAgICAgICAgaWYgYS54ID09IG54IGFuZCBhLnkgPT0gbnk6CiAgICAgICAgICAgICAgICAgICAgICAgIG9rID0gRmFsc2UKICAgICAgICAgICAgICAgIGZvciBlIGluIG9wcF9saXN0OgogICAgICAgICAgICAgICAgICAgIGlmIGUueCA9PSBueCBhbmQgZS55ID09IG55OgogICAgICAgICAgICAgICAgICAgICAgICBpZiBub3QgKChwLlR5cGUgPT0gJ1InIGFuZCBlLlR5cGUgPT0gJ1MnKSBvciAocC5UeXBlID09ICdTJyBhbmQgZS5UeXBlID09ICdQJykgb3IgKHAuVHlwZSA9PSAnUCcgYW5kIGUuVHlwZSA9PSAnUicpKToKICAgICAgICAgICAgICAgICAgICAgICAgICAgIG9rID0gRmFsc2UKICAgICAgICAgICAgICAgIGlmIG9rIGFuZCBBRFYwW255ICogU1RSSURFICsgbnhdID4gYmVzdGs6CiAgICAgICAgICAgICAgICAgICAgYmVzdGsgPSBBRFYwW255ICogU1RSSURFICsgbnhdCiAgICAgICAgICAgICAgICAgICAgcmVzID0gKHAucGlkLCBkKQoKICAgIG1lbW9bJ3VzZWQnXSA9IHVzZWQgKyAodGltZS5wcm9jZXNzX3RpbWUoKSAtIHN0YXJ0X3RpbWUpCiAgICByZXR1cm4gcmVz

Success #stdin #stdout 0.07s 14392KB

stdin

copy

Standard input is empty

stdout

copy

Standard output is empty

https://ideone.com/sF489s

language:

Python 3 (python 3.12)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language