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 = 20
    H = 9
    STRIDE = 22
    SIZE = 242
 
    OFFS = (23, 22, 1, 21, -21, -1, -22, -23)
    DIRN = {21: 1, 22: 2, 23: 3, 1: 4, -21: 5, -22: 6, -23: 7, -1: 8}
 
    BT = ((False, False, True), (True, False, False), (False, True, False))
    PRED = (1, 2, 0)
    PREY = (2, 0, 1)
    LO = (1, 11)
 
    # Mở rộng bảng trọng số chạy đua lên 24 bước cho chiều dài map 20x9
    RT = (
        0, 920, 520, 290, 170, 100, 65, 45, 32, 24,
        18, 14, 10, 8, 6, 4, 3, 2, 1, 0, 0, 0, 0, 0, 0
    )
    UNSTOP_RT = (
        0, 1650, 1050, 680, 440, 290, 195, 135, 95, 68,
        48, 34, 24, 17, 12, 8, 5, 3, 1, 0, 0, 0, 0, 0, 0
    )
 
    PASS_ON = True
    PASS_SLEEP = 3.4
    PASS_ROOT = 10
    PASS_IN = 8
    ELIM1 = 65
    ELIM2 = 0
    PASSM = (-1, 0, -1, -1, 0)
 
    # Xác định hướng xuất phát (trái hay phải khi xoay 180 độ)
    ally_list = list(gameState.ally)
    left_side = (sum(p.x for p in ally_list) <= 10 * max(1, len(ally_list)))
 
    restarted = ('tabs' not in memo) and turn > 1
    if restarted:
        memo['pc'] = 3
 
    tabs = memo.get('tabs')
    if tabs is None or memo.get('left_side') != left_side:
        memo['left_side'] = left_side
 
        # Đặt cứng 2 khối tường đen (7x3 ô) và dải 5 cờ mục tiêu của map 20x9
        if left_side:
            WALL_SET = frozenset(
                y * STRIDE + x for x in range(13, 20) for y in (1, 2, 3, 7, 8, 9)
            )
            GOAL0 = frozenset(y * STRIDE + 20 for y in range(3, 8))
            GOAL1 = frozenset(y * STRIDE + 12 for y in range(3, 8))
        else:
            WALL_SET = frozenset(
                y * STRIDE + x for x in range(2, 9) for y in (1, 2, 3, 7, 8, 9)
            )
            GOAL0 = frozenset(y * STRIDE + 1 for y in range(3, 8))
            GOAL1 = frozenset(y * STRIDE + 9 for y in range(3, 8))
 
        GOAL = (GOAL0, GOAL1)
        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)
 
        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)
 
        # BFS tính khoảng cách ngắn nhất vòng qua tường tới dải 5 cờ (D0, D1)
        MAX_D = 40
        D0 = [MAX_D] * SIZE
        dq = deque(GOAL0)
        for g in GOAL0:
            D0[g] = 0
        while dq:
            u = dq.popleft()
            du = D0[u] + 1
            for off in OFFS:
                v = u + off
                if v in valid_set and du < D0[v]:
                    D0[v] = du
                    dq.append(v)
 
        D1 = [MAX_D] * SIZE
        dq = deque(GOAL1)
        for g in GOAL1:
            D1[g] = 0
        while dq:
            u = dq.popleft()
            du = D1[u] + 1
            for off in OFFS:
                v = u + off
                if v in valid_set and du < D1[v]:
                    D1[v] = du
                    dq.append(v)
 
        # BFS tính khoảng cách săn đuổi né tường giữa mọi cặp ô hợp lệ (DT, MDT)
        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
            dq = deque([src])
            while dq:
                u = dq.popleft()
                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
                        dq.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
        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 - 10.5)
            cy = abs(y - 5.0)
            CENTER[a] = max(0, int(4 - max(cx / 2.0, cy)))
 
        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))
 
        rz = random.Random(20260402)
        Z = tuple(tuple(rz.getrandbits(52) for _ in range(SIZE)) for _ in range(20))
        ZS = rz.getrandbits(52)
        PASSK = rz.getrandbits(52)
        tabs = (WALL_SET, GOAL, NB, DEF_SQ, DT, MDT, ADV0, ADV1, D0, D1, CENTER, MTAB, Z, ZS, PASSK)
        memo['tabs'] = tabs
 
    WALL_SET, GOAL, NB, DEF_SQ, DT, MDT, ADV0, ADV1, D0, D1, CENTER, MTAB, Z, ZS, PASSK = tabs
 
    used = memo.get('used', 0.0)
    left = max(1, (maxT - turn) // 2 + 1)
    if turn <= 1:
        budget = 0.82
    else:
        budget = min(0.81, max(0.04, (155.0 - used) / min(left, 150)))
    deadline = start_time + budget
 
    # Dựng bàn cờ 20x9: ngoài biên và ô tường đen đều là -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
 
    tp = [0] * 20
    ps = [-1] * 20
    TI = {'R': 0, 'P': 1, 'S': 2}
    cnt = [0, 0]
    for p in ally_list:
        c = p.pid
        tp[c] = TI[p.Type]
        pos = p.y * STRIDE + p.x
        ps[c] = pos
        board[pos] = c
        cnt[0] += 1
    for p in gameState.opponent:
        c = 10 + 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 or turn <= 1:
        tt = {}
        memo['tt'] = tt
 
    HIST_SIZE = SIZE * SIZE
    HIST = memo.get('hist')
    if HIST is None or len(HIST) != HIST_SIZE or turn <= 1:
        HIST = [0] * HIST_SIZE
        memo['hist'] = HIST
    else:
        for i in range(HIST_SIZE):
            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)
 
    roles = {}
    e_types_alive = [0, 0, 0]
    e_near_home = []
    e_near_away = [0, 0, 0]
    for c in range(11, 20):
        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 = 99
        for c in range(1, 10):
            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 = 99
        for c in range(1, 10):
            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(1, 10):
        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()
    for idx_r in range(min(2, len(runner_cands))):
        roles[runner_cands[idx_r][2]] = 'RUNNER'
    for c in range(1, 10):
        if ps[c] >= 0 and c not in roles:
            roles[c] = 'HUNTER'
    memo['roles'] = roles
 
    def wins_now(s):
        lo = LO[s]
        hi = lo + 8
        for g in GOAL[s]:
            v0 = board[g]
            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
 
    def gen(s, mode):
        res = []
        lo = LO[s]
        elo = LO[1 - s]
        ehi = elo + 8
        mtab = MTAB[s]
        gset = GOAL[s]
        egset = GOAL[1 - s]
        for c in range(lo, lo + 9):
            p = ps[c]
            if p < 0:
                continue
            t = tp[c]
            bt = BT[t]
            for q, fw_b, h_ix, is_nb in mtab[p]:
                v = board[q]
                if v == 0:
                    if mode == 0:
                        h = HIST[h_ix]
                        res.append((fw_b + (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:
                    ut = tp[v]
                    if bt[ut]:
                        res.append((1050 + fw_b + (90 if q in egset or D1[q] <= 2 else 0), c, p, q, v))
        return res
 
    def evaluate_raw(s):
        A_p = []
        A_t = []
        B_p = []
        B_t = []
        cA0 = cA1 = cA2 = 0
        cB0 = cB1 = cB2 = 0
        for c in range(1, 10):
            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(11, 20):
            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)
 
        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)
 
        far_d = 40
        ha = [far_d] * na
        pa = [far_d] * na
        ma = [far_d * 2] * na
        inta = [99] * na
        hb = [far_d] * nb
        pb = [far_d] * nb
        mb = [far_d * 2] * nb
        intb = [99] * 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
 
        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, 14 - D0[p]) * 3
            adv0 += ap
 
            mp = pa[i]
            if mp < far_d:
                hunt0 += HW * max(0, 16 - mp) + max(0, 32 - 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] == 99:
                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, 14 - D1[q]) * 3
            adv1 += aq
 
            mp = pb[j]
            if mp < far_d:
                hunt1 += HW * max(0, 16 - mp) + max(0, 32 - 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] == 99:
                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)
 
        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] == 99:
                    v -= 450 * (3 - d)
            elif d == 3:
                v -= 110
                if intb[j] == 99:
                    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
 
    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.85):
            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
 
    def search(s, depth, alpha, beta, ply, h, pp=0):
        nodes[0] += 1
        if (nodes[0] & 63) == 0 and (time.process_time() > deadline or time.process_time() - start_time > 0.85):
            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
        hk = (h ^ PASSK) if pp else h
        e = tt.get(hk)
        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
 
        if PASS_ON and not pp and not in_chk and alpha < beta and ply < 40:
            val = -search(o, depth - 1, -beta - PASS_IN, -alpha - PASS_IN, ply + 1, h ^ ZS, 1) - PASS_IN
            if abort[0]:
                return 0
            if val > best:
                best = val
                bm = None
                if val > alpha:
                    alpha = val
 
        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[hk] = (depth, fl, sv, bm)
        return best
 
    def decide():
        root = gen(0, 0)
        if not root:
            return (0, 0)
 
        gset0 = GOAL[0]
        for m in root:
            if m[3] in gset0 or (m[4] and cnt[1] == 1):
                return (m[1], DIRN[m[3] - m[2]])
 
        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 (root[0][1], DIRN[root[0][3] - root[0][2]])
 
        h0 = 0
        for c in range(1, 20):
            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)
 
        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 = 99
            min_pred_q = 99
            min_prey_q = 99
            row_p = DT[p]
            row_q = DT[q]
            for ec in range(11, 20):
                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, 18 - min_prey_q) * 25
            order.append((tb, m))
        order.sort(reverse=True)
        order = [x[1] for x in order]
 
        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[1:10])
            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)))
 
        can_pass = (
            PASS_ON and turn > 1 and memo.get('pc', 0) < 2 and (155.0 - used) > 15
            and not wins_now(1) and not wins_now(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.85:
                    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 can_pass and cur_best is not None and not abort[0]:
                araw = best_adj + PASS_ROOT if best_adj > -INF else -INF
                val = -search(1, depth - 1, -INF, -araw if araw > -INF else INF, 1, h0 ^ ZS, 1)
                if not abort[0]:
                    adj = val - PASS_ROOT if val < WIN - 1000 else val
                    vals.append((adj, PASSM))
                    if adj > best_adj:
                        best_adj = adj
                        cur_best = PASSM
 
            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 if t_item[1] is not PASSM]
                elif cur_best is not PASSM:
                    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.85:
                break
 
        if best_move is PASSM:
            memo['pc'] = memo.get('pc', 0) + 1
            memo['used'] = used + (time.process_time() - start_time)
            time.sleep(PASS_SLEEP)
            return (0, 0)
 
        memo['pc'] = 0
        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[1:10])
        cfg[ck] = cfg.get(ck, 0) + 1
        return (c, DIRN[q - p])
 
    try:
        res = decide()
    except Exception:
        res = (0, 0)
        bestk = -INF
        for p in gameState.ally:
            for d in range(1, 9):
                dx, dy = ((-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0))[d - 1]
                nx = p.x + dx
                ny = p.y + dy
                if nx < 1 or nx > W or ny < 1 or ny > H or (ny * STRIDE + nx) in WALL_SET:
                    continue
                ok = True
                for a in gameState.ally:
                    if a.x == nx and a.y == ny:
                        ok = False
                for e in gameState.opponent:
                    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

aW1wb3J0IG1hdGgKaW1wb3J0IHJhbmRvbQppbXBvcnQgdGltZQoKCmRlZiBwbGF5KGdhbWVTdGF0ZSwgbWVtbz17fSk6CiAgICBzdGFydF90aW1lID0gdGltZS5wcm9jZXNzX3RpbWUoKQogICAgdHVybiA9IGdhbWVTdGF0ZS5jdXJyZW50VHVybgogICAgbWF4VCA9IGdhbWVTdGF0ZS5tYXhUdXJuCgogICAgSU5GID0gMTAgKiogOQogICAgV0lOID0gMTAwMDAwCiAgICBQTFlMSU0gPSA0NAoKCgogICAgVyA9IDIwCiAgICBIID0gOQogICAgU1RSSURFID0gMjIKICAgIFNJWkUgPSAyNDIKCiAgICBPRkZTID0gKDIzLCAyMiwgMSwgMjEsIC0yMSwgLTEsIC0yMiwgLTIzKQogICAgRElSTiA9IHsyMTogMSwgMjI6IDIsIDIzOiAzLCAxOiA0LCAtMjE6IDUsIC0yMjogNiwgLTIzOiA3LCAtMTogOH0KCiAgICBCVCA9ICgoRmFsc2UsIEZhbHNlLCBUcnVlKSwgKFRydWUsIEZhbHNlLCBGYWxzZSksIChGYWxzZSwgVHJ1ZSwgRmFsc2UpKQogICAgUFJFRCA9ICgxLCAyLCAwKQogICAgUFJFWSA9ICgyLCAwLCAxKQogICAgTE8gPSAoMSwgMTEpCgogICAgIyBN4bufIHLhu5luZyBi4bqjbmcgdHLhu41uZyBz4buRIGNo4bqheSDEkXVhIGzDqm4gMjQgYsaw4bubYyBjaG8gY2hp4buBdSBkw6BpIG1hcCAyMHg5CiAgICBSVCA9ICgKICAgICAgICAwLCA5MjAsIDUyMCwgMjkwLCAxNzAsIDEwMCwgNjUsIDQ1LCAzMiwgMjQsCiAgICAgICAgMTgsIDE0LCAxMCwgOCwgNiwgNCwgMywgMiwgMSwgMCwgMCwgMCwgMCwgMCwgMAogICAgKQogICAgVU5TVE9QX1JUID0gKAogICAgICAgIDAsIDE2NTAsIDEwNTAsIDY4MCwgNDQwLCAyOTAsIDE5NSwgMTM1LCA5NSwgNjgsCiAgICAgICAgNDgsIDM0LCAyNCwgMTcsIDEyLCA4LCA1LCAzLCAxLCAwLCAwLCAwLCAwLCAwLCAwCiAgICApCgogICAgUEFTU19PTiA9IFRydWUKICAgIFBBU1NfU0xFRVAgPSAzLjQKICAgIFBBU1NfUk9PVCA9IDEwCiAgICBQQVNTX0lOID0gOAogICAgRUxJTTEgPSA2NQogICAgRUxJTTIgPSAwCiAgICBQQVNTTSA9ICgtMSwgMCwgLTEsIC0xLCAwKQoKICAgICMgWMOhYyDEkeG7i25oIGjGsOG7m25nIHh14bqldCBwaMOhdCAodHLDoWkgaGF5IHBo4bqjaSBraGkgeG9heSAxODAgxJHhu5kpCiAgICBhbGx5X2xpc3QgPSBsaXN0KGdhbWVTdGF0ZS5hbGx5KQogICAgbGVmdF9zaWRlID0gKHN1bShwLnggZm9yIHAgaW4gYWxseV9saXN0KSA8PSAxMCAqIG1heCgxLCBsZW4oYWxseV9saXN0KSkpCgogICAgcmVzdGFydGVkID0gKCd0YWJzJyBub3QgaW4gbWVtbykgYW5kIHR1cm4gPiAxCiAgICBpZiByZXN0YXJ0ZWQ6CiAgICAgICAgbWVtb1sncGMnXSA9IDMKCiAgICB0YWJzID0gbWVtby5nZXQoJ3RhYnMnKQogICAgaWYgdGFicyBpcyBOb25lIG9yIG1lbW8uZ2V0KCdsZWZ0X3NpZGUnKSAhPSBsZWZ0X3NpZGU6CiAgICAgICAgbWVtb1snbGVmdF9zaWRlJ10gPSBsZWZ0X3NpZGUKCiAgICAgICAgIyDEkOG6t3QgY+G7qW5nIDIga2jhu5FpIHTGsOG7nW5nIMSRZW4gKDd4MyDDtCkgdsOgIGThuqNpIDUgY+G7nSBt4bulYyB0acOqdSBj4bunYSBtYXAgMjB4OQogICAgICAgIGlmIGxlZnRfc2lkZToKICAgICAgICAgICAgV0FMTF9TRVQgPSBmcm96ZW5zZXQoCiAgICAgICAgICAgICAgICB5ICogU1RSSURFICsgeCBmb3IgeCBpbiByYW5nZSgxMywgMjApIGZvciB5IGluICgxLCAyLCAzLCA3LCA4LCA5KQogICAgICAgICAgICApCiAgICAgICAgICAgIEdPQUwwID0gZnJvemVuc2V0KHkgKiBTVFJJREUgKyAyMCBmb3IgeSBpbiByYW5nZSgzLCA4KSkKICAgICAgICAgICAgR09BTDEgPSBmcm96ZW5zZXQoeSAqIFNUUklERSArIDEyIGZvciB5IGluIHJhbmdlKDMsIDgpKQogICAgICAgIGVsc2U6CiAgICAgICAgICAgIFdBTExfU0VUID0gZnJvemVuc2V0KAogICAgICAgICAgICAgICAgeSAqIFNUUklERSArIHggZm9yIHggaW4gcmFuZ2UoMiwgOSkgZm9yIHkgaW4gKDEsIDIsIDMsIDcsIDgsIDkpCiAgICAgICAgICAgICkKICAgICAgICAgICAgR09BTDAgPSBmcm96ZW5zZXQoeSAqIFNUUklERSArIDEgZm9yIHkgaW4gcmFuZ2UoMywgOCkpCiAgICAgICAgICAgIEdPQUwxID0gZnJvemVuc2V0KHkgKiBTVFJJREUgKyA5IGZvciB5IGluIHJhbmdlKDMsIDgpKQoKICAgICAgICBHT0FMID0gKEdPQUwwLCBHT0FMMSkKICAgICAgICBjZWxscyA9IFsKICAgICAgICAgICAgeSAqIFNUUklERSArIHgKICAgICAgICAgICAgZm9yIHkgaW4gcmFuZ2UoMSwgSCArIDEpCiAgICAgICAgICAgIGZvciB4IGluIHJhbmdlKDEsIFcgKyAxKQogICAgICAgICAgICBpZiAoeSAqIFNUUklERSArIHgpIG5vdCBpbiBXQUxMX1NFVAogICAgICAgIF0KICAgICAgICB2YWxpZF9zZXQgPSBzZXQoY2VsbHMpCgogICAgICAgIG5iMF9zZXQgPSB7ZyArIG9mZiBmb3IgZyBpbiBHT0FMMCBmb3Igb2ZmIGluIE9GRlMgaWYgKGcgKyBvZmYpIGluIHZhbGlkX3NldCBhbmQgKGcgKyBvZmYpIG5vdCBpbiBHT0FMMH0KICAgICAgICBuYjFfc2V0ID0ge2cgKyBvZmYgZm9yIGcgaW4gR09BTDEgZm9yIG9mZiBpbiBPRkZTIGlmIChnICsgb2ZmKSBpbiB2YWxpZF9zZXQgYW5kIChnICsgb2ZmKSBub3QgaW4gR09BTDF9CiAgICAgICAgTkIgPSAodHVwbGUobmIwX3NldCksIHR1cGxlKG5iMV9zZXQpKQogICAgICAgIERFRl9TUSA9IChHT0FMMCB8IG5iMF9zZXQsIEdPQUwxIHwgbmIxX3NldCkKCiAgICAgICAgIyBCRlMgdMOtbmgga2hv4bqjbmcgY8OhY2ggbmfhuq9uIG5o4bqldCB2w7JuZyBxdWEgdMaw4budbmcgdOG7m2kgZOG6o2kgNSBj4budIChEMCwgRDEpCiAgICAgICAgTUFYX0QgPSA0MAogICAgICAgIEQwID0gW01BWF9EXSAqIFNJWkUKICAgICAgICBkcSA9IGRlcXVlKEdPQUwwKQogICAgICAgIGZvciBnIGluIEdPQUwwOgogICAgICAgICAgICBEMFtnXSA9IDAKICAgICAgICB3aGlsZSBkcToKICAgICAgICAgICAgdSA9IGRxLnBvcGxlZnQoKQogICAgICAgICAgICBkdSA9IEQwW3VdICsgMQogICAgICAgICAgICBmb3Igb2ZmIGluIE9GRlM6CiAgICAgICAgICAgICAgICB2ID0gdSArIG9mZgogICAgICAgICAgICAgICAgaWYgdiBpbiB2YWxpZF9zZXQgYW5kIGR1IDwgRDBbdl06CiAgICAgICAgICAgICAgICAgICAgRDBbdl0gPSBkdQogICAgICAgICAgICAgICAgICAgIGRxLmFwcGVuZCh2KQoKICAgICAgICBEMSA9IFtNQVhfRF0gKiBTSVpFCiAgICAgICAgZHEgPSBkZXF1ZShHT0FMMSkKICAgICAgICBmb3IgZyBpbiBHT0FMMToKICAgICAgICAgICAgRDFbZ10gPSAwCiAgICAgICAgd2hpbGUgZHE6CiAgICAgICAgICAgIHUgPSBkcS5wb3BsZWZ0KCkKICAgICAgICAgICAgZHUgPSBEMVt1XSArIDEKICAgICAgICAgICAgZm9yIG9mZiBpbiBPRkZTOgogICAgICAgICAgICAgICAgdiA9IHUgKyBvZmYKICAgICAgICAgICAgICAgIGlmIHYgaW4gdmFsaWRfc2V0IGFuZCBkdSA8IEQxW3ZdOgogICAgICAgICAgICAgICAgICAgIEQxW3ZdID0gZHUKICAgICAgICAgICAgICAgICAgICBkcS5hcHBlbmQodikKCiAgICAgICAgIyBCRlMgdMOtbmgga2hv4bqjbmcgY8OhY2ggc8SDbiDEkXXhu5VpIG7DqSB0xrDhu51uZyBnaeG7r2EgbeG7jWkgY+G6t3Agw7QgaOG7o3AgbOG7hyAoRFQsIE1EVCkKICAgICAgICBEVCA9IFtbTUFYX0RdICogU0laRSBmb3IgXyBpbiByYW5nZShTSVpFKV0KICAgICAgICBNRFQgPSBbW01BWF9EICogMl0gKiBTSVpFIGZvciBfIGluIHJhbmdlKFNJWkUpXQogICAgICAgIGZvciBzcmMgaW4gY2VsbHM6CiAgICAgICAgICAgIHJvdyA9IERUW3NyY10KICAgICAgICAgICAgbXJvdyA9IE1EVFtzcmNdCiAgICAgICAgICAgIHJvd1tzcmNdID0gMAogICAgICAgICAgICBtcm93W3NyY10gPSAwCiAgICAgICAgICAgIGRxID0gZGVxdWUoW3NyY10pCiAgICAgICAgICAgIHdoaWxlIGRxOgogICAgICAgICAgICAgICAgdSA9IGRxLnBvcGxlZnQoKQogICAgICAgICAgICAgICAgZHUgPSByb3dbdV0gKyAxCiAgICAgICAgICAgICAgICBmb3Igb2ZmIGluIE9GRlM6CiAgICAgICAgICAgICAgICAgICAgdiA9IHUgKyBvZmYKICAgICAgICAgICAgICAgICAgICBpZiB2IGluIHZhbGlkX3NldCBhbmQgZHUgPCByb3dbdl06CiAgICAgICAgICAgICAgICAgICAgICAgIHJvd1t2XSA9IGR1CiAgICAgICAgICAgICAgICAgICAgICAgIG1yb3dbdl0gPSBkdSAqIDIKICAgICAgICAgICAgICAgICAgICAgICAgZHEuYXBwZW5kKHYpCgogICAgICAgIG1heF9kMCA9IG1heCgoRDBbYV0gZm9yIGEgaW4gY2VsbHMgaWYgRDBbYV0gPCBNQVhfRCksIGRlZmF1bHQ9MSkKICAgICAgICBtYXhfZDEgPSBtYXgoKEQxW2FdIGZvciBhIGluIGNlbGxzIGlmIEQxW2FdIDwgTUFYX0QpLCBkZWZhdWx0PTEpCiAgICAgICAgQURWMCA9IFswXSAqIFNJWkUKICAgICAgICBBRFYxID0gWzBdICogU0laRQogICAgICAgIENFTlRFUiA9IFswXSAqIFNJWkUKICAgICAgICBmb3IgYSBpbiBjZWxsczoKICAgICAgICAgICAgeCA9IGEgJSBTVFJJREUKICAgICAgICAgICAgeSA9IGEgLy8gU1RSSURFCiAgICAgICAgICAgIEFEVjBbYV0gPSBtYXgoMCwgbWF4X2QwIC0gRDBbYV0pCiAgICAgICAgICAgIEFEVjFbYV0gPSBtYXgoMCwgbWF4X2QxIC0gRDFbYV0pCiAgICAgICAgICAgIGN4ID0gYWJzKHggLSAxMC41KQogICAgICAgICAgICBjeSA9IGFicyh5IC0gNS4wKQogICAgICAgICAgICBDRU5URVJbYV0gPSBtYXgoMCwgaW50KDQgLSBtYXgoY3ggLyAyLjAsIGN5KSkpCgogICAgICAgIE1UQUIwID0gWygpIGZvciBfIGluIHJhbmdlKFNJWkUpXQogICAgICAgIE1UQUIxID0gWygpIGZvciBfIGluIHJhbmdlKFNJWkUpXQogICAgICAgIGZvciBhIGluIGNlbGxzOgogICAgICAgICAgICBtMCA9IFtdCiAgICAgICAgICAgIG0xID0gW10KICAgICAgICAgICAgZm9yIG9mZiBpbiBPRkZTOgogICAgICAgICAgICAgICAgcSA9IGEgKyBvZmYKICAgICAgICAgICAgICAgIGlmIHEgaW4gdmFsaWRfc2V0OgogICAgICAgICAgICAgICAgICAgIGhfaXggPSBhICogU0laRSArIHEKICAgICAgICAgICAgICAgICAgICBmdzBfYiA9IChEMFthXSAtIEQwW3FdKSAqIDIKICAgICAgICAgICAgICAgICAgICBmdzFfYiA9IChEMVthXSAtIEQxW3FdKSAqIDIKICAgICAgICAgICAgICAgICAgICBtMC5hcHBlbmQoKHEsIGZ3MF9iLCBoX2l4LCAxIGlmIHEgaW4gbmIwX3NldCBlbHNlIDApKQogICAgICAgICAgICAgICAgICAgIG0xLmFwcGVuZCgocSwgZncxX2IsIGhfaXgsIDEgaWYgcSBpbiBuYjFfc2V0IGVsc2UgMCkpCiAgICAgICAgICAgIG0wLnNvcnQoa2V5PWxhbWJkYSBpdGVtOiBpdGVtWzFdLCByZXZlcnNlPVRydWUpCiAgICAgICAgICAgIG0xLnNvcnQoa2V5PWxhbWJkYSBpdGVtOiBpdGVtWzFdLCByZXZlcnNlPVRydWUpCiAgICAgICAgICAgIE1UQUIwW2FdID0gdHVwbGUobTApCiAgICAgICAgICAgIE1UQUIxW2FdID0gdHVwbGUobTEpCiAgICAgICAgTVRBQiA9ICh0dXBsZShNVEFCMCksIHR1cGxlKE1UQUIxKSkKCiAgICAgICAgcnogPSByYW5kb20uUmFuZG9tKDIwMjYwNDAyKQogICAgICAgIFogPSB0dXBsZSh0dXBsZShyei5nZXRyYW5kYml0cyg1MikgZm9yIF8gaW4gcmFuZ2UoU0laRSkpIGZvciBfIGluIHJhbmdlKDIwKSkKICAgICAgICBaUyA9IHJ6LmdldHJhbmRiaXRzKDUyKQogICAgICAgIFBBU1NLID0gcnouZ2V0cmFuZGJpdHMoNTIpCiAgICAgICAgdGFicyA9IChXQUxMX1NFVCwgR09BTCwgTkIsIERFRl9TUSwgRFQsIE1EVCwgQURWMCwgQURWMSwgRDAsIEQxLCBDRU5URVIsIE1UQUIsIFosIFpTLCBQQVNTSykKICAgICAgICBtZW1vWyd0YWJzJ10gPSB0YWJzCgogICAgV0FMTF9TRVQsIEdPQUwsIE5CLCBERUZfU1EsIERULCBNRFQsIEFEVjAsIEFEVjEsIEQwLCBEMSwgQ0VOVEVSLCBNVEFCLCBaLCBaUywgUEFTU0sgPSB0YWJzCgogICAgdXNlZCA9IG1lbW8uZ2V0KCd1c2VkJywgMC4wKQogICAgbGVmdCA9IG1heCgxLCAobWF4VCAtIHR1cm4pIC8vIDIgKyAxKQogICAgaWYgdHVybiA8PSAxOgogICAgICAgIGJ1ZGdldCA9IDAuODIKICAgIGVsc2U6CiAgICAgICAgYnVkZ2V0ID0gbWluKDAuODEsIG1heCgwLjA0LCAoMTU1LjAgLSB1c2VkKSAvIG1pbihsZWZ0LCAxNTApKSkKICAgIGRlYWRsaW5lID0gc3RhcnRfdGltZSArIGJ1ZGdldAoKICAgICMgROG7sW5nIGLDoG4gY+G7nSAyMHg5OiBuZ2/DoGkgYmnDqm4gdsOgIMO0IHTGsOG7nW5nIMSRZW4gxJHhu4F1IGzDoCAtMQogICAgYm9hcmQgPSBbLTFdICogU0laRQogICAgZm9yIHl5IGluIHJhbmdlKDEsIEggKyAxKToKICAgICAgICBiYXNlX3kgPSB5eSAqIFNUUklERQogICAgICAgIGZvciB4eCBpbiByYW5nZSgxLCBXICsgMSk6CiAgICAgICAgICAgIHBvcyA9IGJhc2VfeSArIHh4CiAgICAgICAgICAgIGlmIHBvcyBub3QgaW4gV0FMTF9TRVQ6CiAgICAgICAgICAgICAgICBib2FyZFtwb3NdID0gMAoKICAgIHRwID0gWzBdICogMjAKICAgIHBzID0gWy0xXSAqIDIwCiAgICBUSSA9IHsnUic6IDAsICdQJzogMSwgJ1MnOiAyfQogICAgY250ID0gWzAsIDBdCiAgICBmb3IgcCBpbiBhbGx5X2xpc3Q6CiAgICAgICAgYyA9IHAucGlkCiAgICAgICAgdHBbY10gPSBUSVtwLlR5cGVdCiAgICAgICAgcG9zID0gcC55ICogU1RSSURFICsgcC54CiAgICAgICAgcHNbY10gPSBwb3MKICAgICAgICBib2FyZFtwb3NdID0gYwogICAgICAgIGNudFswXSArPSAxCiAgICBmb3IgcCBpbiBnYW1lU3RhdGUub3Bwb25lbnQ6CiAgICAgICAgYyA9IDEwICsgcC5waWQKICAgICAgICB0cFtjXSA9IFRJW3AuVHlwZV0KICAgICAgICBwb3MgPSBwLnkgKiBTVFJJREUgKyBwLngKICAgICAgICBwc1tjXSA9IHBvcwogICAgICAgIGJvYXJkW3Bvc10gPSBjCiAgICAgICAgY250WzFdICs9IDEKCiAgICB0dCA9IG1lbW8uZ2V0KCd0dCcpCiAgICBpZiB0dCBpcyBOb25lIG9yIGxlbih0dCkgPiAxMjAwMDAgb3IgdHVybiA8PSAxOgogICAgICAgIHR0ID0ge30KICAgICAgICBtZW1vWyd0dCddID0gdHQKCiAgICBISVNUX1NJWkUgPSBTSVpFICogU0laRQogICAgSElTVCA9IG1lbW8uZ2V0KCdoaXN0JykKICAgIGlmIEhJU1QgaXMgTm9uZSBvciBsZW4oSElTVCkgIT0gSElTVF9TSVpFIG9yIHR1cm4gPD0gMToKICAgICAgICBISVNUID0gWzBdICogSElTVF9TSVpFCiAgICAgICAgbWVtb1snaGlzdCddID0gSElTVAogICAgZWxzZToKICAgICAgICBmb3IgaSBpbiByYW5nZShISVNUX1NJWkUpOgogICAgICAgICAgICBpZiBISVNUW2ldOgogICAgICAgICAgICAgICAgSElTVFtpXSA+Pj0gMQoKICAgIEtJTExFUiA9IFtOb25lXSAqIDY0CiAgICBub2RlcyA9IFswXQogICAgYWJvcnQgPSBbRmFsc2VdCgogICAgdG90YWwgPSBjbnRbMF0gKyBjbnRbMV0KICAgIGlmIG1lbW8uZ2V0KCdwcmV2X3RvdGFsJykgIT0gdG90YWw6CiAgICAgICAgbWVtb1sncHJldl90b3RhbCddID0gdG90YWwKICAgICAgICBtZW1vWydjYXB0X3R1cm4nXSA9IHR1cm4KICAgICAgICBtZW1vWydjZmcnXSA9IHt9CiAgICBzdGFnID0gKHR1cm4gLSBtZW1vLmdldCgnY2FwdF90dXJuJywgdHVybikpIC8vIDIKICAgIGFoZWFkID0gY250WzBdID4gY250WzFdCiAgICBiZWhpbmQgPSBjbnRbMF0gPCBjbnRbMV0KCiAgICBLID0gNSArIG1pbig4LCB0dXJuIC8vIDI1KQogICAgaWYgbm90IGJlaGluZCBhbmQgc3RhZyA+IDE2OgogICAgICAgIEsgKz0gbWluKDcsIChzdGFnIC0gMTYpIC8vIDYpCiAgICBpZiBiZWhpbmQ6CiAgICAgICAgSFcgPSAzCiAgICBlbGlmIHN0YWcgPiAxNjoKICAgICAgICBIVyA9IDExCiAgICBlbHNlOgogICAgICAgIEhXID0gNgogICAgaWYgYWhlYWQgYW5kIHN0YWcgPiAyNjoKICAgICAgICBEUCA9ICgwLCAyMjAsIDEyMCwgNTUpCiAgICBlbHNlOgogICAgICAgIERQID0gKDAsIDMzMCwgMTc1LCA4MCkKCiAgICByb2xlcyA9IHt9CiAgICBlX3R5cGVzX2FsaXZlID0gWzAsIDAsIDBdCiAgICBlX25lYXJfaG9tZSA9IFtdCiAgICBlX25lYXJfYXdheSA9IFswLCAwLCAwXQogICAgZm9yIGMgaW4gcmFuZ2UoMTEsIDIwKToKICAgICAgICBxID0gcHNbY10KICAgICAgICBpZiBxID49IDA6CiAgICAgICAgICAgIHUgPSB0cFtjXQogICAgICAgICAgICBlX3R5cGVzX2FsaXZlW3VdICs9IDEKICAgICAgICAgICAgaWYgRDFbcV0gPD0gNDoKICAgICAgICAgICAgICAgIGVfbmVhcl9ob21lLmFwcGVuZCgoRDFbcV0sIHEsIHUpKQogICAgICAgICAgICBpZiBEMFtxXSA8PSAyOgogICAgICAgICAgICAgICAgZV9uZWFyX2F3YXlbdV0gKz0gMQogICAgZV9uZWFyX2hvbWUuc29ydCgpCgogICAgZGVmX2Fzc2lnbmVkID0gc2V0KCkKICAgIGZvciBkX2gsIHFfaCwgdV9oIGluIGVfbmVhcl9ob21lOgogICAgICAgIG5lZWRfdCA9IFBSRURbdV9oXQogICAgICAgIGJlc3RfYyA9IDAKICAgICAgICBiZXN0X2QgPSA5OQogICAgICAgIGZvciBjIGluIHJhbmdlKDEsIDEwKToKICAgICAgICAgICAgcCA9IHBzW2NdCiAgICAgICAgICAgIGlmIHAgPj0gMCBhbmQgdHBbY10gPT0gbmVlZF90IGFuZCBjIG5vdCBpbiBkZWZfYXNzaWduZWQ6CiAgICAgICAgICAgICAgICBkX2MgPSBEMVtwXQogICAgICAgICAgICAgICAgaWYgZF9jIDwgYmVzdF9kOgogICAgICAgICAgICAgICAgICAgIGJlc3RfZCA9IGRfYwogICAgICAgICAgICAgICAgICAgIGJlc3RfYyA9IGMKICAgICAgICBpZiBiZXN0X2M6CiAgICAgICAgICAgIHJvbGVzW2Jlc3RfY10gPSAnREVGRU5ERVInCiAgICAgICAgICAgIGRlZl9hc3NpZ25lZC5hZGQoYmVzdF9jKQoKICAgIGlmIG5vdCBkZWZfYXNzaWduZWQ6CiAgICAgICAgYmVzdF9jID0gMAogICAgICAgIGJlc3RfZCA9IDk5CiAgICAgICAgZm9yIGMgaW4gcmFuZ2UoMSwgMTApOgogICAgICAgICAgICBwID0gcHNbY10KICAgICAgICAgICAgaWYgcCA+PSAwIGFuZCBlX3R5cGVzX2FsaXZlW1BSRVlbdHBbY11dXSA+IDA6CiAgICAgICAgICAgICAgICBkX2MgPSBEMVtwXQogICAgICAgICAgICAgICAgaWYgZF9jIDwgYmVzdF9kOgogICAgICAgICAgICAgICAgICAgIGJlc3RfZCA9IGRfYwogICAgICAgICAgICAgICAgICAgIGJlc3RfYyA9IGMKICAgICAgICBpZiBiZXN0X2MgYW5kIGJlc3RfZCA8PSAzOgogICAgICAgICAgICByb2xlc1tiZXN0X2NdID0gJ0RFRkVOREVSJwogICAgICAgICAgICBkZWZfYXNzaWduZWQuYWRkKGJlc3RfYykKCiAgICBydW5uZXJfY2FuZHMgPSBbXQogICAgZm9yIGMgaW4gcmFuZ2UoMSwgMTApOgogICAgICAgIHAgPSBwc1tjXQogICAgICAgIGlmIHAgPj0gMCBhbmQgYyBub3QgaW4gZGVmX2Fzc2lnbmVkOgogICAgICAgICAgICB0ID0gdHBbY10KICAgICAgICAgICAgaW1tID0gMSBpZiBlX3R5cGVzX2FsaXZlW1BSRURbdF1dID09IDAgZWxzZSAwCiAgICAgICAgICAgIGJyayA9IDEgaWYgZV9uZWFyX2F3YXlbUFJFWVt0XV0gPiAwIGVsc2UgMAogICAgICAgICAgICBydW5uZXJfY2FuZHMuYXBwZW5kKChEMFtwXSAtIDIgKiBpbW0gLSBicmssIC1BRFYwW3BdLCBjKSkKICAgIHJ1bm5lcl9jYW5kcy5zb3J0KCkKICAgIGZvciBpZHhfciBpbiByYW5nZShtaW4oMiwgbGVuKHJ1bm5lcl9jYW5kcykpKToKICAgICAgICByb2xlc1tydW5uZXJfY2FuZHNbaWR4X3JdWzJdXSA9ICdSVU5ORVInCiAgICBmb3IgYyBpbiByYW5nZSgxLCAxMCk6CiAgICAgICAgaWYgcHNbY10gPj0gMCBhbmQgYyBub3QgaW4gcm9sZXM6CiAgICAgICAgICAgIHJvbGVzW2NdID0gJ0hVTlRFUicKICAgIG1lbW9bJ3JvbGVzJ10gPSByb2xlcwoKICAgIGRlZiB3aW5zX25vdyhzKToKICAgICAgICBsbyA9IExPW3NdCiAgICAgICAgaGkgPSBsbyArIDgKICAgICAgICBmb3IgZyBpbiBHT0FMW3NdOgogICAgICAgICAgICB2MCA9IGJvYXJkW2ddCiAgICAgICAgICAgIGlmIHYwID09IDA6CiAgICAgICAgICAgICAgICBmb3Igb2ZmIGluIE9GRlM6CiAgICAgICAgICAgICAgICAgICAgdiA9IGJvYXJkW2cgKyBvZmZdCiAgICAgICAgICAgICAgICAgICAgaWYgbG8gPD0gdiA8PSBoaToKICAgICAgICAgICAgICAgICAgICAgICAgcmV0dXJuIFRydWUKICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgIHQgPSB0cFt2MF0KICAgICAgICAgICAgICAgIGZvciBvZmYgaW4gT0ZGUzoKICAgICAgICAgICAgICAgICAgICB2ID0gYm9hcmRbZyArIG9mZl0KICAgICAgICAgICAgICAgICAgICBpZiBsbyA8PSB2IDw9IGhpIGFuZCBCVFt0cFt2XV1bdF06CiAgICAgICAgICAgICAgICAgICAgICAgIHJldHVybiBUcnVlCiAgICAgICAgcmV0dXJuIEZhbHNlCgogICAgZGVmIGdlbihzLCBtb2RlKToKICAgICAgICByZXMgPSBbXQogICAgICAgIGxvID0gTE9bc10KICAgICAgICBlbG8gPSBMT1sxIC0gc10KICAgICAgICBlaGkgPSBlbG8gKyA4CiAgICAgICAgbXRhYiA9IE1UQUJbc10KICAgICAgICBnc2V0ID0gR09BTFtzXQogICAgICAgIGVnc2V0ID0gR09BTFsxIC0gc10KICAgICAgICBmb3IgYyBpbiByYW5nZShsbywgbG8gKyA5KToKICAgICAgICAgICAgcCA9IHBzW2NdCiAgICAgICAgICAgIGlmIHAgPCAwOgogICAgICAgICAgICAgICAgY29udGludWUKICAgICAgICAgICAgdCA9IHRwW2NdCiAgICAgICAgICAgIGJ0ID0gQlRbdF0KICAgICAgICAgICAgZm9yIHEsIGZ3X2IsIGhfaXgsIGlzX25iIGluIG10YWJbcF06CiAgICAgICAgICAgICAgICB2ID0gYm9hcmRbcV0KICAgICAgICAgICAgICAgIGlmIHYgPT0gMDoKICAgICAgICAgICAgICAgICAgICBpZiBtb2RlID09IDA6CiAgICAgICAgICAgICAgICAgICAgICAgIGggPSBISVNUW2hfaXhdCiAgICAgICAgICAgICAgICAgICAgICAgIHJlcy5hcHBlbmQoKGZ3X2IgKyAoaCBpZiBoIDwgNzIgZWxzZSA3MiksIGMsIHAsIHEsIDApKQogICAgICAgICAgICAgICAgICAgIGVsaWYgbW9kZSA9PSAyIGFuZCBpc19uYjoKICAgICAgICAgICAgICAgICAgICAgICAgZm9yIG9mZiBpbiBPRkZTOgogICAgICAgICAgICAgICAgICAgICAgICAgICAgZ3EgPSBxICsgb2ZmCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZiBncSBpbiBnc2V0OgogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHZnID0gYm9hcmRbZ3FdCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYgdmcgPT0gMCBvciAoZWxvIDw9IHZnIDw9IGVoaSBhbmQgYnRbdHBbdmddXSk6CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJlcy5hcHBlbmQoKDgyMCArIGZ3X2IsIGMsIHAsIHEsIDApKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBicmVhawogICAgICAgICAgICAgICAgZWxpZiBlbG8gPD0gdiA8PSBlaGk6CiAgICAgICAgICAgICAgICAgICAgdXQgPSB0cFt2XQogICAgICAgICAgICAgICAgICAgIGlmIGJ0W3V0XToKICAgICAgICAgICAgICAgICAgICAgICAgcmVzLmFwcGVuZCgoMTA1MCArIGZ3X2IgKyAoOTAgaWYgcSBpbiBlZ3NldCBvciBEMVtxXSA8PSAyIGVsc2UgMCksIGMsIHAsIHEsIHYpKQogICAgICAgIHJldHVybiByZXMKCiAgICBkZWYgZXZhbHVhdGVfcmF3KHMpOgogICAgICAgIEFfcCA9IFtdCiAgICAgICAgQV90ID0gW10KICAgICAgICBCX3AgPSBbXQogICAgICAgIEJfdCA9IFtdCiAgICAgICAgY0EwID0gY0ExID0gY0EyID0gMAogICAgICAgIGNCMCA9IGNCMSA9IGNCMiA9IDAKICAgICAgICBmb3IgYyBpbiByYW5nZSgxLCAxMCk6CiAgICAgICAgICAgIHAgPSBwc1tjXQogICAgICAgICAgICBpZiBwID49IDA6CiAgICAgICAgICAgICAgICB0ID0gdHBbY10KICAgICAgICAgICAgICAgIEFfcC5hcHBlbmQocCkKICAgICAgICAgICAgICAgIEFfdC5hcHBlbmQodCkKICAgICAgICAgICAgICAgIGlmIHQgPT0gMDoKICAgICAgICAgICAgICAgICAgICBjQTAgKz0gMQogICAgICAgICAgICAgICAgZWxpZiB0ID09IDE6CiAgICAgICAgICAgICAgICAgICAgY0ExICs9IDEKICAgICAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICAgICAgY0EyICs9IDEKICAgICAgICBmb3IgYyBpbiByYW5nZSgxMSwgMjApOgogICAgICAgICAgICBwID0gcHNbY10KICAgICAgICAgICAgaWYgcCA+PSAwOgogICAgICAgICAgICAgICAgdCA9IHRwW2NdCiAgICAgICAgICAgICAgICBCX3AuYXBwZW5kKHApCiAgICAgICAgICAgICAgICBCX3QuYXBwZW5kKHQpCiAgICAgICAgICAgICAgICBpZiB0ID09IDA6CiAgICAgICAgICAgICAgICAgICAgY0IwICs9IDEKICAgICAgICAgICAgICAgIGVsaWYgdCA9PSAxOgogICAgICAgICAgICAgICAgICAgIGNCMSArPSAxCiAgICAgICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgICAgIGNCMiArPSAxCgogICAgICAgIG5hID0gbGVuKEFfcCkKICAgICAgICBuYiA9IGxlbihCX3ApCiAgICAgICAgaWYgbmEgPT0gMDoKICAgICAgICAgICAgcmV0dXJuIC1XSU4gKyAxMDAgaWYgcyA9PSAwIGVsc2UgV0lOIC0gMTAwCiAgICAgICAgaWYgbmIgPT0gMDoKICAgICAgICAgICAgcmV0dXJuIFdJTiAtIDEwMCBpZiBzID09IDAgZWxzZSAtV0lOICsgMTAwCgogICAgICAgIGNBID0gKGNBMCwgY0ExLCBjQTIpCiAgICAgICAgY0IgPSAoY0IwLCBjQjEsIGNCMikKCiAgICAgICAgdiA9IDEwNTAgKiAobmEgLSBuYikgKyAzMjAwICogKG5hIC0gbmIpIC8vIChuYSArIG5iKQoKICAgICAgICBmb3IgdCBpbiAoMCwgMSwgMik6CiAgICAgICAgICAgIHByZWQgPSBQUkVEW3RdCiAgICAgICAgICAgIHByZXkgPSBQUkVZW3RdCiAgICAgICAgICAgIGNhID0gY0FbdF0KICAgICAgICAgICAgY2IgPSBjQlt0XQogICAgICAgICAgICBpZiBjYToKICAgICAgICAgICAgICAgIGlmIGNCW3ByZWRdID09IDA6CiAgICAgICAgICAgICAgICAgICAgdiArPSBjYSAqICg1MDAgaWYgY0JbdF0gPT0gMCBlbHNlIDM2MCkKICAgICAgICAgICAgICAgIGVsaWYgY0JbcHJlZF0gPT0gMSBhbmQgY0FbcHJleV0gPiAwOgogICAgICAgICAgICAgICAgICAgIHYgKz0gY2EgKiBFTElNMQogICAgICAgICAgICAgICAgZWxpZiBFTElNMiBhbmQgY0JbcHJlZF0gPT0gMiBhbmQgY0FbcHJleV0gPj0gMjoKICAgICAgICAgICAgICAgICAgICB2ICs9IGNhICogRUxJTTIKICAgICAgICAgICAgICAgIHYgKz0gY2EgKiAoODAgKiBjQltwcmV5XSBpZiBjQltwcmV5XSBlbHNlIC01MCkKICAgICAgICAgICAgaWYgY2I6CiAgICAgICAgICAgICAgICBpZiBjQVtwcmVkXSA9PSAwOgogICAgICAgICAgICAgICAgICAgIHYgLT0gY2IgKiAoNTAwIGlmIGNBW3RdID09IDAgZWxzZSAzNjApCiAgICAgICAgICAgICAgICBlbGlmIGNBW3ByZWRdID09IDEgYW5kIGNCW3ByZXldID4gMDoKICAgICAgICAgICAgICAgICAgICB2IC09IGNiICogRUxJTTEKICAgICAgICAgICAgICAgIGVsaWYgRUxJTTIgYW5kIGNBW3ByZWRdID09IDIgYW5kIGNCW3ByZXldID49IDI6CiAgICAgICAgICAgICAgICAgICAgdiAtPSBjYiAqIEVMSU0yCiAgICAgICAgICAgICAgICB2IC09IGNiICogKDgwICogY0FbcHJleV0gaWYgY0FbcHJleV0gZWxzZSAtNTApCgogICAgICAgIGZhcl9kID0gNDAKICAgICAgICBoYSA9IFtmYXJfZF0gKiBuYQogICAgICAgIHBhID0gW2Zhcl9kXSAqIG5hCiAgICAgICAgbWEgPSBbZmFyX2QgKiAyXSAqIG5hCiAgICAgICAgaW50YSA9IFs5OV0gKiBuYQogICAgICAgIGhiID0gW2Zhcl9kXSAqIG5iCiAgICAgICAgcGIgPSBbZmFyX2RdICogbmIKICAgICAgICBtYiA9IFtmYXJfZCAqIDJdICogbmIKICAgICAgICBpbnRiID0gWzk5XSAqIG5iCgogICAgICAgIGZvciBpIGluIHJhbmdlKG5hKToKICAgICAgICAgICAgcCA9IEFfcFtpXQogICAgICAgICAgICB0ID0gQV90W2ldCiAgICAgICAgICAgIGQwcCA9IEQwW3BdCiAgICAgICAgICAgIHJvdyA9IERUW3BdCiAgICAgICAgICAgIG1yb3cgPSBNRFRbcF0KICAgICAgICAgICAgYnQgPSBCVFt0XQogICAgICAgICAgICBmb3IgaiBpbiByYW5nZShuYik6CiAgICAgICAgICAgICAgICBxID0gQl9wW2pdCiAgICAgICAgICAgICAgICB1ID0gQl90W2pdCiAgICAgICAgICAgICAgICBkMHEgPSBEMFtxXQogICAgICAgICAgICAgICAgZDFxID0gRDFbcV0KICAgICAgICAgICAgICAgIGlmIHUgPT0gdDoKICAgICAgICAgICAgICAgICAgICBpZiBkMHEgPD0gZDBwIGFuZCBkMHEgPCBpbnRhW2ldOgogICAgICAgICAgICAgICAgICAgICAgICBpbnRhW2ldID0gZDBxCiAgICAgICAgICAgICAgICAgICAgaWYgRDFbcF0gPD0gZDFxIGFuZCBEMVtwXSA8IGludGJbal06CiAgICAgICAgICAgICAgICAgICAgICAgIGludGJbal0gPSBEMVtwXQogICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlCiAgICAgICAgICAgICAgICBkID0gcm93W3FdCiAgICAgICAgICAgICAgICBtZCA9IG1yb3dbcV0KICAgICAgICAgICAgICAgIGlmIGJ0W3VdOgogICAgICAgICAgICAgICAgICAgIGlmIGQgPCBwYVtpXToKICAgICAgICAgICAgICAgICAgICAgICAgcGFbaV0gPSBkCiAgICAgICAgICAgICAgICAgICAgaWYgbWQgPCBtYVtpXToKICAgICAgICAgICAgICAgICAgICAgICAgbWFbaV0gPSBtZAogICAgICAgICAgICAgICAgICAgIGlmIGQgPCBoYltqXToKICAgICAgICAgICAgICAgICAgICAgICAgaGJbal0gPSBkCiAgICAgICAgICAgICAgICAgICAgaWYgRDFbcF0gPD0gZDFxICsgMSBhbmQgRDFbcF0gPCBpbnRiW2pdOgogICAgICAgICAgICAgICAgICAgICAgICBpbnRiW2pdID0gRDFbcF0KICAgICAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICAgICAgaWYgZCA8IGhhW2ldOgogICAgICAgICAgICAgICAgICAgICAgICBoYVtpXSA9IGQKICAgICAgICAgICAgICAgICAgICBpZiBkIDwgcGJbal06CiAgICAgICAgICAgICAgICAgICAgICAgIHBiW2pdID0gZAogICAgICAgICAgICAgICAgICAgIGlmIG1kIDwgbWJbal06CiAgICAgICAgICAgICAgICAgICAgICAgIG1iW2pdID0gbWQKICAgICAgICAgICAgICAgICAgICBpZiBkMHEgPD0gZDBwICsgMSBhbmQgZDBxIDwgaW50YVtpXToKICAgICAgICAgICAgICAgICAgICAgICAgaW50YVtpXSA9IGQwcQoKICAgICAgICBhZHYwID0gMAogICAgICAgIHRocjAgPSAwCiAgICAgICAgZGcwID0gMAogICAgICAgIGh1bnQwID0gMAogICAgICAgIGhhbmcwID0gMAogICAgICAgIGF3YXlfZ3VhcmRfYiA9IFswLCAwLCAwXQogICAgICAgIGZvciBqIGluIHJhbmdlKG5iKToKICAgICAgICAgICAgaWYgRDBbQl9wW2pdXSA8PSAyOgogICAgICAgICAgICAgICAgYXdheV9ndWFyZF9iW0JfdFtqXV0gPSAxCgogICAgICAgIG1heF91bnN0b3AgPSBsZW4oVU5TVE9QX1JUKSAtIDEKICAgICAgICBtYXhfcnQgPSBsZW4oUlQpIC0gMQoKICAgICAgICBmb3IgaSBpbiByYW5nZShuYSk6CiAgICAgICAgICAgIHAgPSBBX3BbaV0KICAgICAgICAgICAgdCA9IEFfdFtpXQogICAgICAgICAgICBhcCA9IEFEVjBbcF0KICAgICAgICAgICAgaWYgY0JbUFJFRFt0XV0gPT0gMDoKICAgICAgICAgICAgICAgIGFwICs9IGFwID4+IDEKICAgICAgICAgICAgaWYgYXdheV9ndWFyZF9iW1BSRVlbdF1dOgogICAgICAgICAgICAgICAgYXAgKz0gbWF4KDAsIDE0IC0gRDBbcF0pICogMwogICAgICAgICAgICBhZHYwICs9IGFwCgogICAgICAgICAgICBtcCA9IHBhW2ldCiAgICAgICAgICAgIGlmIG1wIDwgZmFyX2Q6CiAgICAgICAgICAgICAgICBodW50MCArPSBIVyAqIG1heCgwLCAxNiAtIG1wKSArIG1heCgwLCAzMiAtIG1hW2ldKQogICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgaHVudDAgKz0gQ0VOVEVSW3BdCgogICAgICAgICAgICBtaCA9IGhhW2ldCiAgICAgICAgICAgIGlmIG1oIDw9IDM6CiAgICAgICAgICAgICAgICBwdCA9IFBSRVlbdF0KICAgICAgICAgICAgICAgIHJvdyA9IERUW3BdCiAgICAgICAgICAgICAgICBwcm90ID0gRmFsc2UKICAgICAgICAgICAgICAgIGZvciBrIGluIHJhbmdlKG5hKToKICAgICAgICAgICAgICAgICAgICBpZiBBX3Rba10gPT0gcHQgYW5kIHJvd1tBX3Bba11dIDw9IDE6CiAgICAgICAgICAgICAgICAgICAgICAgIHByb3QgPSBUcnVlCiAgICAgICAgICAgICAgICAgICAgICAgIGJyZWFrCiAgICAgICAgICAgICAgICBpZiBub3QgcHJvdDoKICAgICAgICAgICAgICAgICAgICBpZiBtaCA8PSAxOgogICAgICAgICAgICAgICAgICAgICAgICBkZzAgKz0gRFBbMV0gKyAoMTYwIGlmIHMgPT0gMSBlbHNlIDApCiAgICAgICAgICAgICAgICAgICAgICAgIGhhbmcwICs9IDEKICAgICAgICAgICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgICAgICAgICBkZzAgKz0gRFBbbWhdCiAgICAgICAgICAgICAgICBlbGlmIG1oIDw9IDI6CiAgICAgICAgICAgICAgICAgICAgaHVudDAgKz0gMjUKCiAgICAgICAgICAgIGQgPSBEMFtwXQogICAgICAgICAgICBpZiBpbnRhW2ldID09IDk5OgogICAgICAgICAgICAgICAgaWYgZCA8PSBtYXhfdW5zdG9wOgogICAgICAgICAgICAgICAgICAgIHR2ID0gVU5TVE9QX1JUW2RdCiAgICAgICAgICAgICAgICAgICAgaWYgdHYgPiB0aHIwOgogICAgICAgICAgICAgICAgICAgICAgICB0aHIwID0gdHYKICAgICAgICAgICAgZWxpZiBkIDw9IG1heF9ydDoKICAgICAgICAgICAgICAgIHR2ID0gUlRbZF0KICAgICAgICAgICAgICAgIGlmIG1oIDw9IDIgb3IgaW50YVtpXSA8PSBkOgogICAgICAgICAgICAgICAgICAgIHR2IC8vPSAzCiAgICAgICAgICAgICAgICBpZiB0diA+IHRocjA6CiAgICAgICAgICAgICAgICAgICAgdGhyMCA9IHR2CgogICAgICAgIGlmIGhhbmcwID49IDI6CiAgICAgICAgICAgIGRnMCArPSAzODAgKiAoaGFuZzAgLSAxKQoKICAgICAgICBhZHYxID0gMAogICAgICAgIHRocjEgPSAwCiAgICAgICAgZGcxID0gMAogICAgICAgIGh1bnQxID0gMAogICAgICAgIGhhbmcxID0gMAogICAgICAgIGhvbWVfZ3VhcmRfYSA9IFswLCAwLCAwXQogICAgICAgIGZvciBpIGluIHJhbmdlKG5hKToKICAgICAgICAgICAgaWYgRDFbQV9wW2ldXSA8PSAyOgogICAgICAgICAgICAgICAgaG9tZV9ndWFyZF9hW0FfdFtpXV0gPSAxCgogICAgICAgIGZvciBqIGluIHJhbmdlKG5iKToKICAgICAgICAgICAgcSA9IEJfcFtqXQogICAgICAgICAgICB1ID0gQl90W2pdCiAgICAgICAgICAgIGFxID0gQURWMVtxXQogICAgICAgICAgICBpZiBjQVtQUkVEW3VdXSA9PSAwOgogICAgICAgICAgICAgICAgYXEgKz0gYXEgPj4gMQogICAgICAgICAgICBpZiBob21lX2d1YXJkX2FbUFJFWVt1XV06CiAgICAgICAgICAgICAgICBhcSArPSBtYXgoMCwgMTQgLSBEMVtxXSkgKiAzCiAgICAgICAgICAgIGFkdjEgKz0gYXEKCiAgICAgICAgICAgIG1wID0gcGJbal0KICAgICAgICAgICAgaWYgbXAgPCBmYXJfZDoKICAgICAgICAgICAgICAgIGh1bnQxICs9IEhXICogbWF4KDAsIDE2IC0gbXApICsgbWF4KDAsIDMyIC0gbWJbal0pCiAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICBodW50MSArPSBDRU5URVJbcV0KCiAgICAgICAgICAgIG1oID0gaGJbal0KICAgICAgICAgICAgaWYgbWggPD0gMzoKICAgICAgICAgICAgICAgIHB0ID0gUFJFWVt1XQogICAgICAgICAgICAgICAgcm93ID0gRFRbcV0KICAgICAgICAgICAgICAgIHByb3QgPSBGYWxzZQogICAgICAgICAgICAgICAgZm9yIGsgaW4gcmFuZ2UobmIpOgogICAgICAgICAgICAgICAgICAgIGlmIEJfdFtrXSA9PSBwdCBhbmQgcm93W0JfcFtrXV0gPD0gMToKICAgICAgICAgICAgICAgICAgICAgICAgcHJvdCA9IFRydWUKICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWsKICAgICAgICAgICAgICAgIGlmIG5vdCBwcm90OgogICAgICAgICAgICAgICAgICAgIGlmIG1oIDw9IDE6CiAgICAgICAgICAgICAgICAgICAgICAgIGRnMSArPSBEUFsxXSArICgxNjAgaWYgcyA9PSAwIGVsc2UgMCkKICAgICAgICAgICAgICAgICAgICAgICAgaGFuZzEgKz0gMQogICAgICAgICAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICAgICAgICAgIGRnMSArPSBEUFttaF0KICAgICAgICAgICAgICAgIGVsaWYgbWggPD0gMjoKICAgICAgICAgICAgICAgICAgICBodW50MSArPSAyNQoKICAgICAgICAgICAgZCA9IEQxW3FdCiAgICAgICAgICAgIGlmIGludGJbal0gPT0gOTk6CiAgICAgICAgICAgICAgICBpZiBkIDw9IG1heF91bnN0b3A6CiAgICAgICAgICAgICAgICAgICAgdHYgPSBVTlNUT1BfUlRbZF0KICAgICAgICAgICAgICAgICAgICBpZiB0diA+IHRocjE6CiAgICAgICAgICAgICAgICAgICAgICAgIHRocjEgPSB0dgogICAgICAgICAgICBlbGlmIGQgPD0gbWF4X3J0OgogICAgICAgICAgICAgICAgdHYgPSBSVFtkXQogICAgICAgICAgICAgICAgaWYgbWggPD0gMiBvciBpbnRiW2pdIDw9IGQ6CiAgICAgICAgICAgICAgICAgICAgdHYgLy89IDMKICAgICAgICAgICAgICAgIGlmIHR2ID4gdGhyMToKICAgICAgICAgICAgICAgICAgICB0aHIxID0gdHYKCiAgICAgICAgaWYgaGFuZzEgPj0gMjoKICAgICAgICAgICAgZGcxICs9IDM4MCAqIChoYW5nMSAtIDEpCgogICAgICAgIHYgKz0gSyAqIChhZHYwIC0gYWR2MSkgKyAodGhyMCAtIHRocjEpIC0gKGRnMCAtIGRnMSkgKyAoaHVudDAgLSBodW50MSkKCiAgICAgICAgaGFzX3VzZWZ1bF9kZWYgPSBGYWxzZQogICAgICAgIGZvciBpIGluIHJhbmdlKG5hKToKICAgICAgICAgICAgaWYgRDFbQV9wW2ldXSA8PSAyIGFuZCBjQltQUkVZW0FfdFtpXV1dID4gMDoKICAgICAgICAgICAgICAgIGhhc191c2VmdWxfZGVmID0gVHJ1ZQogICAgICAgICAgICAgICAgYnJlYWsKCiAgICAgICAgbmVhcl9jbnQgPSAwCiAgICAgICAgZm9yIGogaW4gcmFuZ2UobmIpOgogICAgICAgICAgICBkID0gRDFbQl9wW2pdXQogICAgICAgICAgICBpZiBkIDw9IDI6CiAgICAgICAgICAgICAgICB2IC09IDUyMCAqICgzIC0gZCkKICAgICAgICAgICAgICAgIG5lYXJfY250ICs9IDEKICAgICAgICAgICAgICAgIGlmIGludGJbal0gPT0gOTk6CiAgICAgICAgICAgICAgICAgICAgdiAtPSA0NTAgKiAoMyAtIGQpCiAgICAgICAgICAgIGVsaWYgZCA9PSAzOgogICAgICAgICAgICAgICAgdiAtPSAxMTAKICAgICAgICAgICAgICAgIGlmIGludGJbal0gPT0gOTk6CiAgICAgICAgICAgICAgICAgICAgdiAtPSAyMjAKICAgICAgICAgICAgZWxpZiBkID09IDQ6CiAgICAgICAgICAgICAgICB2IC09IDM1CgogICAgICAgIGlmIG5lYXJfY250ID49IDI6CiAgICAgICAgICAgIHYgLT0gNDIwICogKG5lYXJfY250IC0gMSkKICAgICAgICBpZiBuZWFyX2NudCA+PSAxIGFuZCBub3QgaGFzX3VzZWZ1bF9kZWY6CiAgICAgICAgICAgIHYgLT0gNDIwICogbmVhcl9jbnQKICAgICAgICBpZiBoYXNfdXNlZnVsX2RlZjoKICAgICAgICAgICAgdiArPSAxMzUgKyAxMDUgKiBuZWFyX2NudAoKICAgICAgICByZXR1cm4gdiBpZiBzID09IDAgZWxzZSAtdgoKICAgIGV2YyA9IHt9CgogICAgZGVmIGV2YWx1YXRlKHMsIGgpOgogICAgICAgIHIgPSBldmMuZ2V0KGgpCiAgICAgICAgaWYgciBpcyBOb25lOgogICAgICAgICAgICByID0gZXZhbHVhdGVfcmF3KHMpCiAgICAgICAgICAgIGV2Y1toXSA9IHIKICAgICAgICByZXR1cm4gcgoKICAgIGRlZiBxc2VhcmNoKHMsIGFscGhhLCBiZXRhLCBwbHksIHFkLCBoKToKICAgICAgICBub2Rlc1swXSArPSAxCiAgICAgICAgaWYgKG5vZGVzWzBdICYgNjMpID09IDAgYW5kICh0aW1lLnByb2Nlc3NfdGltZSgpID4gZGVhZGxpbmUgb3IgdGltZS5wcm9jZXNzX3RpbWUoKSAtIHN0YXJ0X3RpbWUgPiAwLjg1KToKICAgICAgICAgICAgYWJvcnRbMF0gPSBUcnVlCiAgICAgICAgaWYgYWJvcnRbMF06CiAgICAgICAgICAgIHJldHVybiAwCiAgICAgICAgaWYgd2luc19ub3cocyk6CiAgICAgICAgICAgIHJldHVybiBXSU4gLSBwbHkKICAgICAgICBvID0gMSAtIHMKICAgICAgICBpbl9jaGsgPSB3aW5zX25vdyhvKQogICAgICAgIGlmIGluX2NoazoKICAgICAgICAgICAgaWYgcWQgPj0gNDoKICAgICAgICAgICAgICAgIHJldHVybiAtV0lOICsgcGx5ICsgMQogICAgICAgICAgICBhbGxfbSA9IGdlbihzLCAwKQogICAgICAgICAgICBkZWZfc3EgPSBERUZfU1Fbb10KICAgICAgICAgICAgZXZhc2lvbnMgPSBbbSBmb3IgbSBpbiBhbGxfbSBpZiBtWzNdIGluIGRlZl9zcV0KICAgICAgICAgICAgaWYgbm90IGV2YXNpb25zOgogICAgICAgICAgICAgICAgcmV0dXJuIC1XSU4gKyBwbHkgKyAxCiAgICAgICAgICAgIGV2YXNpb25zLnNvcnQocmV2ZXJzZT1UcnVlKQogICAgICAgICAgICBiZXN0ID0gLVdJTiArIHBseSArIDEKICAgICAgICAgICAgZm9yIG0gaW4gZXZhc2lvbnM6CiAgICAgICAgICAgICAgICBjID0gbVsxXQogICAgICAgICAgICAgICAgcCA9IG1bMl0KICAgICAgICAgICAgICAgIHEgPSBtWzNdCiAgICAgICAgICAgICAgICBjYXAgPSBtWzRdCiAgICAgICAgICAgICAgICBib2FyZFtwXSA9IDAKICAgICAgICAgICAgICAgIGJvYXJkW3FdID0gYwogICAgICAgICAgICAgICAgcHNbY10gPSBxCiAgICAgICAgICAgICAgICBoMiA9IGggXiBaW2NdW3BdIF4gWltjXVtxXSBeIFpTCiAgICAgICAgICAgICAgICBpZiBjYXA6CiAgICAgICAgICAgICAgICAgICAgcHNbY2FwXSA9IC0xCiAgICAgICAgICAgICAgICAgICAgY250W29dIC09IDEKICAgICAgICAgICAgICAgICAgICBoMiBePSBaW2NhcF1bcV0KICAgICAgICAgICAgICAgIHN0aWxsX3cgPSB3aW5zX25vdyhvKQogICAgICAgICAgICAgICAgaWYgbm90IHN0aWxsX3c6CiAgICAgICAgICAgICAgICAgICAgaWYgY2FwIGFuZCBjbnRbb10gPT0gMDoKICAgICAgICAgICAgICAgICAgICAgICAgdmFsID0gV0lOIC0gcGx5CiAgICAgICAgICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgICAgICAgICAgdmFsID0gLXFzZWFyY2gobywgLWJldGEsIC1hbHBoYSwgcGx5ICsgMSwgcWQgKyAxLCBoMikKICAgICAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICAgICAgdmFsID0gLVdJTiArIHBseSArIDEKICAgICAgICAgICAgICAgIGlmIGNhcDoKICAgICAgICAgICAgICAgICAgICBjbnRbb10gKz0gMQogICAgICAgICAgICAgICAgICAgIHBzW2NhcF0gPSBxCiAgICAgICAgICAgICAgICBib2FyZFtxXSA9IGNhcAogICAgICAgICAgICAgICAgYm9hcmRbcF0gPSBjCiAgICAgICAgICAgICAgICBwc1tjXSA9IHAKICAgICAgICAgICAgICAgIGlmIGFib3J0WzBdOgogICAgICAgICAgICAgICAgICAgIHJldHVybiAwCiAgICAgICAgICAgICAgICBpZiB2YWwgPiBiZXN0OgogICAgICAgICAgICAgICAgICAgIGJlc3QgPSB2YWwKICAgICAgICAgICAgICAgICAgICBpZiB2YWwgPiBhbHBoYToKICAgICAgICAgICAgICAgICAgICAgICAgYWxwaGEgPSB2YWwKICAgICAgICAgICAgICAgICAgICAgICAgaWYgYWxwaGEgPj0gYmV0YToKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJyZWFrCiAgICAgICAgICAgIHJldHVybiBiZXN0CgogICAgICAgIHN0YW5kID0gZXZhbHVhdGUocywgaCkKICAgICAgICBpZiBzdGFuZCA+PSBiZXRhOgogICAgICAgICAgICByZXR1cm4gc3RhbmQKICAgICAgICBpZiBzdGFuZCA+IGFscGhhOgogICAgICAgICAgICBhbHBoYSA9IHN0YW5kCiAgICAgICAgaWYgcWQgPj0gNjoKICAgICAgICAgICAgcmV0dXJuIHN0YW5kCiAgICAgICAgbW92ZXMgPSBnZW4ocywgMiBpZiBxZCA9PSAwIGVsc2UgMSkKICAgICAgICBpZiBub3QgbW92ZXM6CiAgICAgICAgICAgIHJldHVybiBzdGFuZAogICAgICAgIG1vdmVzLnNvcnQocmV2ZXJzZT1UcnVlKQogICAgICAgIGZvciBtIGluIG1vdmVzOgogICAgICAgICAgICBjID0gbVsxXQogICAgICAgICAgICBwID0gbVsyXQogICAgICAgICAgICBxID0gbVszXQogICAgICAgICAgICBjYXAgPSBtWzRdCiAgICAgICAgICAgIGJvYXJkW3BdID0gMAogICAgICAgICAgICBib2FyZFtxXSA9IGMKICAgICAgICAgICAgcHNbY10gPSBxCiAgICAgICAgICAgIGgyID0gaCBeIFpbY11bcF0gXiBaW2NdW3FdIF4gWlMKICAgICAgICAgICAgaWYgY2FwOgogICAgICAgICAgICAgICAgcHNbY2FwXSA9IC0xCiAgICAgICAgICAgICAgICBjbnRbb10gLT0gMQogICAgICAgICAgICAgICAgaDIgXj0gWltjYXBdW3FdCiAgICAgICAgICAgIGlmIGNhcCBhbmQgY250W29dID09IDA6CiAgICAgICAgICAgICAgICB2YWwgPSBXSU4gLSBwbHkKICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgIHZhbCA9IC1xc2VhcmNoKG8sIC1iZXRhLCAtYWxwaGEsIHBseSArIDEsIHFkICsgMSwgaDIpCiAgICAgICAgICAgIGlmIGNhcDoKICAgICAgICAgICAgICAgIGNudFtvXSArPSAxCiAgICAgICAgICAgICAgICBwc1tjYXBdID0gcQogICAgICAgICAgICBib2FyZFtxXSA9IGNhcAogICAgICAgICAgICBib2FyZFtwXSA9IGMKICAgICAgICAgICAgcHNbY10gPSBwCiAgICAgICAgICAgIGlmIGFib3J0WzBdOgogICAgICAgICAgICAgICAgcmV0dXJuIDAKICAgICAgICAgICAgaWYgdmFsID4gc3RhbmQ6CiAgICAgICAgICAgICAgICBzdGFuZCA9IHZhbAogICAgICAgICAgICAgICAgaWYgdmFsID4gYWxwaGE6CiAgICAgICAgICAgICAgICAgICAgYWxwaGEgPSB2YWwKICAgICAgICAgICAgICAgICAgICBpZiBhbHBoYSA+PSBiZXRhOgogICAgICAgICAgICAgICAgICAgICAgICBicmVhawogICAgICAgIHJldHVybiBzdGFuZAoKICAgIGRlZiBzZWFyY2gocywgZGVwdGgsIGFscGhhLCBiZXRhLCBwbHksIGgsIHBwPTApOgogICAgICAgIG5vZGVzWzBdICs9IDEKICAgICAgICBpZiAobm9kZXNbMF0gJiA2MykgPT0gMCBhbmQgKHRpbWUucHJvY2Vzc190aW1lKCkgPiBkZWFkbGluZSBvciB0aW1lLnByb2Nlc3NfdGltZSgpIC0gc3RhcnRfdGltZSA+IDAuODUpOgogICAgICAgICAgICBhYm9ydFswXSA9IFRydWUKICAgICAgICBpZiBhYm9ydFswXToKICAgICAgICAgICAgcmV0dXJuIDAKICAgICAgICBpZiB3aW5zX25vdyhzKToKICAgICAgICAgICAgcmV0dXJuIFdJTiAtIHBseQogICAgICAgIG8gPSAxIC0gcwogICAgICAgIGluX2NoayA9IHdpbnNfbm93KG8pCiAgICAgICAgaWYgZGVwdGggPD0gMDoKICAgICAgICAgICAgaWYgaW5fY2hrIGFuZCBwbHkgPCBQTFlMSU06CiAgICAgICAgICAgICAgICBkZXB0aCA9IDEKICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgIHJldHVybiBxc2VhcmNoKHMsIGFscGhhLCBiZXRhLCBwbHksIDAsIGgpCiAgICAgICAgYTAgPSBhbHBoYQogICAgICAgIHR0bSA9IE5vbmUKICAgICAgICBoayA9IChoIF4gUEFTU0spIGlmIHBwIGVsc2UgaAogICAgICAgIGUgPSB0dC5nZXQoaGspCiAgICAgICAgaWYgZSBpcyBub3QgTm9uZToKICAgICAgICAgICAgZWQsIGVmLCBldiwgZW0gPSBlCiAgICAgICAgICAgIGlmIGV2ID4gV0lOIC0gMTAwMDoKICAgICAgICAgICAgICAgIGV2IC09IHBseQogICAgICAgICAgICBlbGlmIGV2IDwgLVdJTiArIDEwMDA6CiAgICAgICAgICAgICAgICBldiArPSBwbHkKICAgICAgICAgICAgdHRtID0gZW0KICAgICAgICAgICAgaWYgZWQgPj0gZGVwdGg6CiAgICAgICAgICAgICAgICBpZiBlZiA9PSAwOgogICAgICAgICAgICAgICAgICAgIHJldHVybiBldgogICAgICAgICAgICAgICAgaWYgZWYgPT0gMToKICAgICAgICAgICAgICAgICAgICBpZiBldiA+PSBiZXRhOgogICAgICAgICAgICAgICAgICAgICAgICByZXR1cm4gZXYKICAgICAgICAgICAgICAgIGVsaWYgZXYgPD0gYWxwaGE6CiAgICAgICAgICAgICAgICAgICAgcmV0dXJuIGV2CiAgICAgICAgbW92ZXMgPSBnZW4ocywgMCkKICAgICAgICBpZiBub3QgbW92ZXM6CiAgICAgICAgICAgIHJldHVybiAtV0lOICsgcGx5ICsgMSBpZiBpbl9jaGsgZWxzZSBldmFsdWF0ZShzLCBoKQogICAgICAgIGlmIGluX2NoazoKICAgICAgICAgICAgZGVmX3NxID0gREVGX1NRW29dCiAgICAgICAgICAgIG1vdmVzID0gW20gZm9yIG0gaW4gbW92ZXMgaWYgbVszXSBpbiBkZWZfc3FdCiAgICAgICAgICAgIGlmIG5vdCBtb3ZlczoKICAgICAgICAgICAgICAgIHJldHVybiAtV0lOICsgcGx5ICsgMQoKICAgICAgICBtb3Zlcy5zb3J0KHJldmVyc2U9VHJ1ZSkKICAgICAgICBrbSA9IEtJTExFUltwbHldIGlmIHBseSA8IDY0IGVsc2UgTm9uZQogICAgICAgIGlmIGttIGlzIG5vdCBOb25lIG9yIHR0bSBpcyBub3QgTm9uZToKICAgICAgICAgICAgZm9yIGkgaW4gcmFuZ2UobGVuKG1vdmVzKSk6CiAgICAgICAgICAgICAgICBtID0gbW92ZXNbaV0KICAgICAgICAgICAgICAgIGlmIHR0bSBpcyBub3QgTm9uZSBhbmQgbVsxXSA9PSB0dG1bMF0gYW5kIG1bMl0gPT0gdHRtWzFdIGFuZCBtWzNdID09IHR0bVsyXToKICAgICAgICAgICAgICAgICAgICBpZiBpOgogICAgICAgICAgICAgICAgICAgICAgICBtb3Zlcy5pbnNlcnQoMCwgbW92ZXMucG9wKGkpKQogICAgICAgICAgICAgICAgICAgIGJyZWFrCiAgICAgICAgICAgIGlmIGttIGlzIG5vdCBOb25lOgogICAgICAgICAgICAgICAgZm9yIGkgaW4gcmFuZ2UoMSwgbGVuKG1vdmVzKSk6CiAgICAgICAgICAgICAgICAgICAgbSA9IG1vdmVzW2ldCiAgICAgICAgICAgICAgICAgICAgaWYgbVsxXSA9PSBrbVswXSBhbmQgbVsyXSA9PSBrbVsxXSBhbmQgbVszXSA9PSBrbVsyXToKICAgICAgICAgICAgICAgICAgICAgICAgbW92ZXMuaW5zZXJ0KDEgaWYgdHRtIGlzIG5vdCBOb25lIGVsc2UgMCwgbW92ZXMucG9wKGkpKQogICAgICAgICAgICAgICAgICAgICAgICBicmVhawoKICAgICAgICBiZXN0ID0gLVdJTiArIHBseSArIDEgaWYgaW5fY2hrIGVsc2UgLUlORgogICAgICAgIGJtID0gTm9uZQogICAgICAgIGlkeCA9IDAKICAgICAgICBuYl9zZXQgPSBERUZfU1Fbc10KICAgICAgICBmb3IgbSBpbiBtb3ZlczoKICAgICAgICAgICAgYyA9IG1bMV0KICAgICAgICAgICAgcCA9IG1bMl0KICAgICAgICAgICAgcSA9IG1bM10KICAgICAgICAgICAgY2FwID0gbVs0XQogICAgICAgICAgICBib2FyZFtwXSA9IDAKICAgICAgICAgICAgYm9hcmRbcV0gPSBjCiAgICAgICAgICAgIHBzW2NdID0gcQogICAgICAgICAgICBoMiA9IGggXiBaW2NdW3BdIF4gWltjXVtxXSBeIFpTCiAgICAgICAgICAgIGlmIGNhcDoKICAgICAgICAgICAgICAgIHBzW2NhcF0gPSAtMQogICAgICAgICAgICAgICAgY250W29dIC09IDEKICAgICAgICAgICAgICAgIGgyIF49IFpbY2FwXVtxXQogICAgICAgICAgICBpZiBpbl9jaGsgYW5kIHdpbnNfbm93KG8pOgogICAgICAgICAgICAgICAgdmFsID0gLVdJTiArIHBseSArIDEKICAgICAgICAgICAgZWxpZiBjYXAgYW5kIGNudFtvXSA9PSAwOgogICAgICAgICAgICAgICAgdmFsID0gV0lOIC0gcGx5CiAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICBpZiBpZHggPT0gMDoKICAgICAgICAgICAgICAgICAgICB2YWwgPSAtc2VhcmNoKG8sIGRlcHRoIC0gMSwgLWJldGEsIC1hbHBoYSwgcGx5ICsgMSwgaDIpCiAgICAgICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgICAgIHJlZCA9IDEgaWYgKGlkeCA+PSA0IGFuZCBkZXB0aCA+PSAzIGFuZCBub3QgY2FwIGFuZCBub3QgaW5fY2hrIGFuZCBxIG5vdCBpbiBuYl9zZXQpIGVsc2UgMAogICAgICAgICAgICAgICAgICAgIGlmIGlkeCA+PSAxMiBhbmQgZGVwdGggPj0gNSBhbmQgcmVkOgogICAgICAgICAgICAgICAgICAgICAgICByZWQgPSAyCiAgICAgICAgICAgICAgICAgICAgdmFsID0gLXNlYXJjaChvLCBkZXB0aCAtIDEgLSByZWQsIC1hbHBoYSAtIDEsIC1hbHBoYSwgcGx5ICsgMSwgaDIpCiAgICAgICAgICAgICAgICAgICAgaWYgdmFsID4gYWxwaGEgYW5kIG5vdCBhYm9ydFswXToKICAgICAgICAgICAgICAgICAgICAgICAgdmFsID0gLXNlYXJjaChvLCBkZXB0aCAtIDEsIC1iZXRhLCAtYWxwaGEsIHBseSArIDEsIGgyKQogICAgICAgICAgICBpZiBjYXA6CiAgICAgICAgICAgICAgICBjbnRbb10gKz0gMQogICAgICAgICAgICAgICAgcHNbY2FwXSA9IHEKICAgICAgICAgICAgYm9hcmRbcV0gPSBjYXAKICAgICAgICAgICAgYm9hcmRbcF0gPSBjCiAgICAgICAgICAgIHBzW2NdID0gcAogICAgICAgICAgICBpZiBhYm9ydFswXToKICAgICAgICAgICAgICAgIHJldHVybiAwCiAgICAgICAgICAgIGlmIHZhbCA+IGJlc3Q6CiAgICAgICAgICAgICAgICBiZXN0ID0gdmFsCiAgICAgICAgICAgICAgICBibSA9IChjLCBwLCBxKQogICAgICAgICAgICAgICAgaWYgdmFsID4gYWxwaGE6CiAgICAgICAgICAgICAgICAgICAgYWxwaGEgPSB2YWwKICAgICAgICAgICAgICAgICAgICBpZiBhbHBoYSA+PSBiZXRhOgogICAgICAgICAgICAgICAgICAgICAgICBpZiBub3QgY2FwOgogICAgICAgICAgICAgICAgICAgICAgICAgICAgSElTVFtwICogU0laRSArIHFdICs9IGRlcHRoICogZGVwdGgKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmIHBseSA8IDY0OgogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIEtJTExFUltwbHldID0gYm0KICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWsKICAgICAgICAgICAgaWR4ICs9IDEKCiAgICAgICAgaWYgUEFTU19PTiBhbmQgbm90IHBwIGFuZCBub3QgaW5fY2hrIGFuZCBhbHBoYSA8IGJldGEgYW5kIHBseSA8IDQwOgogICAgICAgICAgICB2YWwgPSAtc2VhcmNoKG8sIGRlcHRoIC0gMSwgLWJldGEgLSBQQVNTX0lOLCAtYWxwaGEgLSBQQVNTX0lOLCBwbHkgKyAxLCBoIF4gWlMsIDEpIC0gUEFTU19JTgogICAgICAgICAgICBpZiBhYm9ydFswXToKICAgICAgICAgICAgICAgIHJldHVybiAwCiAgICAgICAgICAgIGlmIHZhbCA+IGJlc3Q6CiAgICAgICAgICAgICAgICBiZXN0ID0gdmFsCiAgICAgICAgICAgICAgICBibSA9IE5vbmUKICAgICAgICAgICAgICAgIGlmIHZhbCA+IGFscGhhOgogICAgICAgICAgICAgICAgICAgIGFscGhhID0gdmFsCgogICAgICAgIHN2ID0gYmVzdAogICAgICAgIGlmIHN2ID4gV0lOIC0gMTAwMDoKICAgICAgICAgICAgc3YgKz0gcGx5CiAgICAgICAgZWxpZiBzdiA8IC1XSU4gKyAxMDAwOgogICAgICAgICAgICBzdiAtPSBwbHkKICAgICAgICBpZiBiZXN0IDw9IGEwOgogICAgICAgICAgICBmbCA9IDIKICAgICAgICBlbGlmIGJlc3QgPj0gYmV0YToKICAgICAgICAgICAgZmwgPSAxCiAgICAgICAgZWxzZToKICAgICAgICAgICAgZmwgPSAwCiAgICAgICAgdHRbaGtdID0gKGRlcHRoLCBmbCwgc3YsIGJtKQogICAgICAgIHJldHVybiBiZXN0CgogICAgZGVmIGRlY2lkZSgpOgogICAgICAgIHJvb3QgPSBnZW4oMCwgMCkKICAgICAgICBpZiBub3Qgcm9vdDoKICAgICAgICAgICAgcmV0dXJuICgwLCAwKQoKICAgICAgICBnc2V0MCA9IEdPQUxbMF0KICAgICAgICBmb3IgbSBpbiByb290OgogICAgICAgICAgICBpZiBtWzNdIGluIGdzZXQwIG9yIChtWzRdIGFuZCBjbnRbMV0gPT0gMSk6CiAgICAgICAgICAgICAgICByZXR1cm4gKG1bMV0sIERJUk5bbVszXSAtIG1bMl1dKQoKICAgICAgICBpZiB3aW5zX25vdygxKToKICAgICAgICAgICAgc2FmZSA9IFtdCiAgICAgICAgICAgIGZvciBtIGluIHJvb3Q6CiAgICAgICAgICAgICAgICBjMCA9IG1bMV0KICAgICAgICAgICAgICAgIHAwID0gbVsyXQogICAgICAgICAgICAgICAgcTAgPSBtWzNdCiAgICAgICAgICAgICAgICBjYXAwID0gbVs0XQogICAgICAgICAgICAgICAgYm9hcmRbcDBdID0gMAogICAgICAgICAgICAgICAgYm9hcmRbcTBdID0gYzAKICAgICAgICAgICAgICAgIHBzW2MwXSA9IHEwCiAgICAgICAgICAgICAgICBpZiBjYXAwOgogICAgICAgICAgICAgICAgICAgIHBzW2NhcDBdID0gLTEKICAgICAgICAgICAgICAgICAgICBjbnRbMV0gLT0gMQogICAgICAgICAgICAgICAgaWYgbm90IHdpbnNfbm93KDEpOgogICAgICAgICAgICAgICAgICAgIHNhZmUuYXBwZW5kKG0pCiAgICAgICAgICAgICAgICBpZiBjYXAwOgogICAgICAgICAgICAgICAgICAgIGNudFsxXSArPSAxCiAgICAgICAgICAgICAgICAgICAgcHNbY2FwMF0gPSBxMAogICAgICAgICAgICAgICAgYm9hcmRbcTBdID0gY2FwMAogICAgICAgICAgICAgICAgYm9hcmRbcDBdID0gYzAKICAgICAgICAgICAgICAgIHBzW2MwXSA9IHAwCiAgICAgICAgICAgIGlmIHNhZmU6CiAgICAgICAgICAgICAgICByb290ID0gc2FmZQoKICAgICAgICBpZiBsZW4ocm9vdCkgPT0gMToKICAgICAgICAgICAgcmV0dXJuIChyb290WzBdWzFdLCBESVJOW3Jvb3RbMF1bM10gLSByb290WzBdWzJdXSkKCiAgICAgICAgaDAgPSAwCiAgICAgICAgZm9yIGMgaW4gcmFuZ2UoMSwgMjApOgogICAgICAgICAgICBpZiBwc1tjXSA+PSAwOgogICAgICAgICAgICAgICAgaDAgXj0gWltjXVtwc1tjXV0KCiAgICAgICAgc2VlbiA9IG1lbW8uc2V0ZGVmYXVsdCgnc2VlbicsIHt9KQogICAgICAgIGNmZyA9IG1lbW8uc2V0ZGVmYXVsdCgnY2ZnJywge30pCiAgICAgICAgcGVuX3VuaXQgPSAxMzAgKyAyICogbWluKHR1cm4sIDIwMCkKICAgICAgICBjZmdfdW5pdCA9ICg0NSArIDQgKiBzdGFnKSAqICgwLjI1IGlmIGJlaGluZCBlbHNlIDEuMCkKCiAgICAgICAgb3JkZXIgPSBbXQogICAgICAgIGZvciBtIGluIHJvb3Q6CiAgICAgICAgICAgIGMgPSBtWzFdCiAgICAgICAgICAgIHAgPSBtWzJdCiAgICAgICAgICAgIHEgPSBtWzNdCiAgICAgICAgICAgIGNhcCA9IG1bNF0KICAgICAgICAgICAgdCA9IHRwW2NdCiAgICAgICAgICAgIHByZWRfdCA9IFBSRURbdF0KICAgICAgICAgICAgcHJleV90ID0gUFJFWVt0XQogICAgICAgICAgICByb2xlID0gcm9sZXMuZ2V0KGMsICdIVU5URVInKQogICAgICAgICAgICB0YiA9IG1bMF0gKiAxMAogICAgICAgICAgICBpZiBjYXA6CiAgICAgICAgICAgICAgICB0YiArPSA1MDAwCgogICAgICAgICAgICBtaW5fcHJlZF9wID0gOTkKICAgICAgICAgICAgbWluX3ByZWRfcSA9IDk5CiAgICAgICAgICAgIG1pbl9wcmV5X3EgPSA5OQogICAgICAgICAgICByb3dfcCA9IERUW3BdCiAgICAgICAgICAgIHJvd19xID0gRFRbcV0KICAgICAgICAgICAgZm9yIGVjIGluIHJhbmdlKDExLCAyMCk6CiAgICAgICAgICAgICAgICBlcCA9IHBzW2VjXQogICAgICAgICAgICAgICAgaWYgZXAgPj0gMCBhbmQgZWMgIT0gY2FwOgogICAgICAgICAgICAgICAgICAgIGV0ID0gdHBbZWNdCiAgICAgICAgICAgICAgICAgICAgaWYgZXQgPT0gcHJlZF90OgogICAgICAgICAgICAgICAgICAgICAgICBpZiByb3dfcFtlcF0gPCBtaW5fcHJlZF9wOgogICAgICAgICAgICAgICAgICAgICAgICAgICAgbWluX3ByZWRfcCA9IHJvd19wW2VwXQogICAgICAgICAgICAgICAgICAgICAgICBpZiByb3dfcVtlcF0gPCBtaW5fcHJlZF9xOgogICAgICAgICAgICAgICAgICAgICAgICAgICAgbWluX3ByZWRfcSA9IHJvd19xW2VwXQogICAgICAgICAgICAgICAgICAgIGVsaWYgZXQgPT0gcHJleV90OgogICAgICAgICAgICAgICAgICAgICAgICBpZiByb3dfcVtlcF0gPCBtaW5fcHJleV9xOgogICAgICAgICAgICAgICAgICAgICAgICAgICAgbWluX3ByZXlfcSA9IHJvd19xW2VwXQogICAgICAgICAgICBpZiBtaW5fcHJlZF9wID09IDEgYW5kIG1pbl9wcmVkX3EgPiAxOgogICAgICAgICAgICAgICAgdGIgKz0gMzUwCiAgICAgICAgICAgIGlmIG1pbl9wcmVkX3EgPT0gMToKICAgICAgICAgICAgICAgIHRiIC09IDYwMAogICAgICAgICAgICBpZiByb2xlID09ICdSVU5ORVInOgogICAgICAgICAgICAgICAgdGIgKz0gKEQwW3BdIC0gRDBbcV0pICogNDUgKyAoQURWMFtxXSAtIEFEVjBbcF0pICogMjAKICAgICAgICAgICAgZWxpZiByb2xlID09ICdERUZFTkRFUic6CiAgICAgICAgICAgICAgICB0YiArPSAoRDFbcF0gLSBEMVtxXSkgKiAzNQogICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgdGIgKz0gbWF4KDAsIDE4IC0gbWluX3ByZXlfcSkgKiAyNQogICAgICAgICAgICBvcmRlci5hcHBlbmQoKHRiLCBtKSkKICAgICAgICBvcmRlci5zb3J0KHJldmVyc2U9VHJ1ZSkKICAgICAgICBvcmRlciA9IFt4WzFdIGZvciB4IGluIG9yZGVyXQoKICAgICAgICBwZW5zID0ge30KICAgICAgICBmb3IgbSBpbiBvcmRlcjoKICAgICAgICAgICAgYyA9IG1bMV0KICAgICAgICAgICAgcCA9IG1bMl0KICAgICAgICAgICAgcSA9IG1bM10KICAgICAgICAgICAgY2FwID0gbVs0XQogICAgICAgICAgICBib2FyZFtwXSA9IDAKICAgICAgICAgICAgYm9hcmRbcV0gPSBjCiAgICAgICAgICAgIHBzW2NdID0gcQogICAgICAgICAgICBpZiBjYXA6CiAgICAgICAgICAgICAgICBwc1tjYXBdID0gLTEKICAgICAgICAgICAga2V5ID0gdHVwbGUocHMpCiAgICAgICAgICAgIGNrID0gdHVwbGUocHNbMToxMF0pCiAgICAgICAgICAgIGlmIGNhcDoKICAgICAgICAgICAgICAgIHBzW2NhcF0gPSBxCiAgICAgICAgICAgIGJvYXJkW3FdID0gY2FwCiAgICAgICAgICAgIGJvYXJkW3BdID0gYwogICAgICAgICAgICBwc1tjXSA9IHAKICAgICAgICAgICAgcGVuc1soYywgcCwgcSldID0gbWluKDc1MCwgaW50KHBlbl91bml0ICogc2Vlbi5nZXQoa2V5LCAwKSArIGNmZ191bml0ICogY2ZnLmdldChjaywgMCkpKQoKICAgICAgICBjYW5fcGFzcyA9ICgKICAgICAgICAgICAgUEFTU19PTiBhbmQgdHVybiA+IDEgYW5kIG1lbW8uZ2V0KCdwYycsIDApIDwgMiBhbmQgKDE1NS4wIC0gdXNlZCkgPiAxNQogICAgICAgICAgICBhbmQgbm90IHdpbnNfbm93KDEpIGFuZCBub3Qgd2luc19ub3coMCkKICAgICAgICApCgogICAgICAgIGJlc3RfbW92ZSA9IG9yZGVyWzBdCiAgICAgICAgZm9yIGRlcHRoIGluIHJhbmdlKDEsIDQyKToKICAgICAgICAgICAgYmVzdF9hZGogPSAtSU5GCiAgICAgICAgICAgIGN1cl9iZXN0ID0gTm9uZQogICAgICAgICAgICBkb25lID0gMAogICAgICAgICAgICB2YWxzID0gW10KICAgICAgICAgICAgZm9yIG0gaW4gb3JkZXI6CiAgICAgICAgICAgICAgICBpZiB0aW1lLnByb2Nlc3NfdGltZSgpIC0gc3RhcnRfdGltZSA+IDAuODU6CiAgICAgICAgICAgICAgICAgICAgYWJvcnRbMF0gPSBUcnVlCiAgICAgICAgICAgICAgICAgICAgYnJlYWsKICAgICAgICAgICAgICAgIGMgPSBtWzFdCiAgICAgICAgICAgICAgICBwID0gbVsyXQogICAgICAgICAgICAgICAgcSA9IG1bM10KICAgICAgICAgICAgICAgIGNhcCA9IG1bNF0KICAgICAgICAgICAgICAgIHBlbiA9IHBlbnNbKGMsIHAsIHEpXQogICAgICAgICAgICAgICAgYXJhdyA9IGJlc3RfYWRqICsgcGVuIGlmIGJlc3RfYWRqID4gLUlORiBlbHNlIC1JTkYKICAgICAgICAgICAgICAgIGJvYXJkW3BdID0gMAogICAgICAgICAgICAgICAgYm9hcmRbcV0gPSBjCiAgICAgICAgICAgICAgICBwc1tjXSA9IHEKICAgICAgICAgICAgICAgIGgyID0gaDAgXiBaW2NdW3BdIF4gWltjXVtxXSBeIFpTCiAgICAgICAgICAgICAgICBpZiBjYXA6CiAgICAgICAgICAgICAgICAgICAgcHNbY2FwXSA9IC0xCiAgICAgICAgICAgICAgICAgICAgY250WzFdIC09IDEKICAgICAgICAgICAgICAgICAgICBoMiBePSBaW2NhcF1bcV0KICAgICAgICAgICAgICAgIHZhbCA9IC1zZWFyY2goMSwgZGVwdGggLSAxLCAtSU5GLCAtYXJhdyBpZiBhcmF3ID4gLUlORiBlbHNlIElORiwgMSwgaDIpCiAgICAgICAgICAgICAgICBpZiBjYXA6CiAgICAgICAgICAgICAgICAgICAgY250WzFdICs9IDEKICAgICAgICAgICAgICAgICAgICBwc1tjYXBdID0gcQogICAgICAgICAgICAgICAgYm9hcmRbcV0gPSBjYXAKICAgICAgICAgICAgICAgIGJvYXJkW3BdID0gYwogICAgICAgICAgICAgICAgcHNbY10gPSBwCiAgICAgICAgICAgICAgICBpZiBhYm9ydFswXToKICAgICAgICAgICAgICAgICAgICBicmVhawogICAgICAgICAgICAgICAgZG9uZSArPSAxCiAgICAgICAgICAgICAgICBhZGogPSB2YWwgLSBwZW4gaWYgdmFsIDwgV0lOIC0gMTAwMCBlbHNlIHZhbAogICAgICAgICAgICAgICAgdmFscy5hcHBlbmQoKGFkaiwgbSkpCiAgICAgICAgICAgICAgICBpZiBhZGogPiBiZXN0X2FkajoKICAgICAgICAgICAgICAgICAgICBiZXN0X2FkaiA9IGFkagogICAgICAgICAgICAgICAgICAgIGN1cl9iZXN0ID0gbQoKICAgICAgICAgICAgaWYgY2FuX3Bhc3MgYW5kIGN1cl9iZXN0IGlzIG5vdCBOb25lIGFuZCBub3QgYWJvcnRbMF06CiAgICAgICAgICAgICAgICBhcmF3ID0gYmVzdF9hZGogKyBQQVNTX1JPT1QgaWYgYmVzdF9hZGogPiAtSU5GIGVsc2UgLUlORgogICAgICAgICAgICAgICAgdmFsID0gLXNlYXJjaCgxLCBkZXB0aCAtIDEsIC1JTkYsIC1hcmF3IGlmIGFyYXcgPiAtSU5GIGVsc2UgSU5GLCAxLCBoMCBeIFpTLCAxKQogICAgICAgICAgICAgICAgaWYgbm90IGFib3J0WzBdOgogICAgICAgICAgICAgICAgICAgIGFkaiA9IHZhbCAtIFBBU1NfUk9PVCBpZiB2YWwgPCBXSU4gLSAxMDAwIGVsc2UgdmFsCiAgICAgICAgICAgICAgICAgICAgdmFscy5hcHBlbmQoKGFkaiwgUEFTU00pKQogICAgICAgICAgICAgICAgICAgIGlmIGFkaiA+IGJlc3RfYWRqOgogICAgICAgICAgICAgICAgICAgICAgICBiZXN0X2FkaiA9IGFkagogICAgICAgICAgICAgICAgICAgICAgICBjdXJfYmVzdCA9IFBBU1NNCgogICAgICAgICAgICBpZiBjdXJfYmVzdCBpcyBub3QgTm9uZSBhbmQgKG5vdCBhYm9ydFswXSBvciBkb25lID49IDEpOgogICAgICAgICAgICAgICAgYmVzdF9tb3ZlID0gY3VyX2Jlc3QKICAgICAgICAgICAgICAgIGlmIG5vdCBhYm9ydFswXToKICAgICAgICAgICAgICAgICAgICB2YWxzLnNvcnQoa2V5PWxhbWJkYSB6OiB6WzBdLCByZXZlcnNlPVRydWUpCiAgICAgICAgICAgICAgICAgICAgb3JkZXIgPSBbdF9pdGVtWzFdIGZvciB0X2l0ZW0gaW4gdmFscyBpZiB0X2l0ZW1bMV0gaXMgbm90IFBBU1NNXQogICAgICAgICAgICAgICAgZWxpZiBjdXJfYmVzdCBpcyBub3QgUEFTU006CiAgICAgICAgICAgICAgICAgICAgb3JkZXIucmVtb3ZlKGN1cl9iZXN0KQogICAgICAgICAgICAgICAgICAgIG9yZGVyLmluc2VydCgwLCBjdXJfYmVzdCkKICAgICAgICAgICAgaWYgYWJvcnRbMF06CiAgICAgICAgICAgICAgICBicmVhawogICAgICAgICAgICBpZiBiZXN0X2FkaiA+IFdJTiAtIDEwMDAgb3IgYmVzdF9hZGogPCAtV0lOICsgMTAwMDoKICAgICAgICAgICAgICAgIGJyZWFrCiAgICAgICAgICAgIGlmIHRpbWUucHJvY2Vzc190aW1lKCkgPiBkZWFkbGluZSBvciB0aW1lLnByb2Nlc3NfdGltZSgpIC0gc3RhcnRfdGltZSA+IDAuODU6CiAgICAgICAgICAgICAgICBicmVhawoKICAgICAgICBpZiBiZXN0X21vdmUgaXMgUEFTU006CiAgICAgICAgICAgIG1lbW9bJ3BjJ10gPSBtZW1vLmdldCgncGMnLCAwKSArIDEKICAgICAgICAgICAgbWVtb1sndXNlZCddID0gdXNlZCArICh0aW1lLnByb2Nlc3NfdGltZSgpIC0gc3RhcnRfdGltZSkKICAgICAgICAgICAgdGltZS5zbGVlcChQQVNTX1NMRUVQKQogICAgICAgICAgICByZXR1cm4gKDAsIDApCgogICAgICAgIG1lbW9bJ3BjJ10gPSAwCiAgICAgICAgYyA9IGJlc3RfbW92ZVsxXQogICAgICAgIHAgPSBiZXN0X21vdmVbMl0KICAgICAgICBxID0gYmVzdF9tb3ZlWzNdCiAgICAgICAgY2FwID0gYmVzdF9tb3ZlWzRdCiAgICAgICAgYm9hcmRbcF0gPSAwCiAgICAgICAgYm9hcmRbcV0gPSBjCiAgICAgICAgcHNbY10gPSBxCiAgICAgICAgaWYgY2FwOgogICAgICAgICAgICBwc1tjYXBdID0gLTEKICAgICAgICBrZXkgPSB0dXBsZShwcykKICAgICAgICBzZWVuW2tleV0gPSBzZWVuLmdldChrZXksIDApICsgMQogICAgICAgIGNrID0gdHVwbGUocHNbMToxMF0pCiAgICAgICAgY2ZnW2NrXSA9IGNmZy5nZXQoY2ssIDApICsgMQogICAgICAgIHJldHVybiAoYywgRElSTltxIC0gcF0pCgogICAgdHJ5OgogICAgICAgIHJlcyA9IGRlY2lkZSgpCiAgICBleGNlcHQgRXhjZXB0aW9uOgogICAgICAgIHJlcyA9ICgwLCAwKQogICAgICAgIGJlc3RrID0gLUlORgogICAgICAgIGZvciBwIGluIGdhbWVTdGF0ZS5hbGx5OgogICAgICAgICAgICBmb3IgZCBpbiByYW5nZSgxLCA5KToKICAgICAgICAgICAgICAgIGR4LCBkeSA9ICgoLTEsIDEpLCAoMCwgMSksICgxLCAxKSwgKDEsIDApLCAoMSwgLTEpLCAoMCwgLTEpLCAoLTEsIC0xKSwgKC0xLCAwKSlbZCAtIDFdCiAgICAgICAgICAgICAgICBueCA9IHAueCArIGR4CiAgICAgICAgICAgICAgICBueSA9IHAueSArIGR5CiAgICAgICAgICAgICAgICBpZiBueCA8IDEgb3IgbnggPiBXIG9yIG55IDwgMSBvciBueSA+IEggb3IgKG55ICogU1RSSURFICsgbngpIGluIFdBTExfU0VUOgogICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlCiAgICAgICAgICAgICAgICBvayA9IFRydWUKICAgICAgICAgICAgICAgIGZvciBhIGluIGdhbWVTdGF0ZS5hbGx5OgogICAgICAgICAgICAgICAgICAgIGlmIGEueCA9PSBueCBhbmQgYS55ID09IG55OgogICAgICAgICAgICAgICAgICAgICAgICBvayA9IEZhbHNlCiAgICAgICAgICAgICAgICBmb3IgZSBpbiBnYW1lU3RhdGUub3Bwb25lbnQ6CiAgICAgICAgICAgICAgICAgICAgaWYgZS54ID09IG54IGFuZCBlLnkgPT0gbnk6CiAgICAgICAgICAgICAgICAgICAgICAgIGlmIG5vdCAoKHAuVHlwZSA9PSAnUicgYW5kIGUuVHlwZSA9PSAnUycpIG9yIChwLlR5cGUgPT0gJ1MnIGFuZCBlLlR5cGUgPT0gJ1AnKSBvciAocC5UeXBlID09ICdQJyBhbmQgZS5UeXBlID09ICdSJykpOgogICAgICAgICAgICAgICAgICAgICAgICAgICAgb2sgPSBGYWxzZQogICAgICAgICAgICAgICAgaWYgb2sgYW5kIEFEVjBbbnkgKiBTVFJJREUgKyBueF0gPiBiZXN0azoKICAgICAgICAgICAgICAgICAgICBiZXN0ayA9IEFEVjBbbnkgKiBTVFJJREUgKyBueF0KICAgICAgICAgICAgICAgICAgICByZXMgPSAocC5waWQsIGQpCgogICAgbWVtb1sndXNlZCddID0gdXNlZCArICh0aW1lLnByb2Nlc3NfdGltZSgpIC0gc3RhcnRfdGltZSkKICAgIHJldHVybiByZXM=

Success #stdin #stdout 0.07s 14352KB

stdin

copy

Standard input is empty

stdout

copy

Standard output is empty

https://ideone.com/byaCcT

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