from collections import deque
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
 
    # Quy ước lưới 20x9 có vùng đệm 1 ô xung quanh -> STRIDE = 22, SIZE = 242
    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

ZnJvbSBjb2xsZWN0aW9ucyBpbXBvcnQgZGVxdWUKaW1wb3J0IG1hdGgKaW1wb3J0IHJhbmRvbQppbXBvcnQgdGltZQoKCmRlZiBwbGF5KGdhbWVTdGF0ZSwgbWVtbz17fSk6CiAgICBzdGFydF90aW1lID0gdGltZS5wcm9jZXNzX3RpbWUoKQogICAgdHVybiA9IGdhbWVTdGF0ZS5jdXJyZW50VHVybgogICAgbWF4VCA9IGdhbWVTdGF0ZS5tYXhUdXJuCgogICAgSU5GID0gMTAgKiogOQogICAgV0lOID0gMTAwMDAwCiAgICBQTFlMSU0gPSA0NAoKICAgICMgUXV5IMaw4bubYyBsxrDhu5tpIDIweDkgY8OzIHbDuW5nIMSR4buHbSAxIMO0IHh1bmcgcXVhbmggLT4gU1RSSURFID0gMjIsIFNJWkUgPSAyNDIKICAgIFcgPSAyMAogICAgSCA9IDkKICAgIFNUUklERSA9IDIyCiAgICBTSVpFID0gMjQyCgogICAgT0ZGUyA9ICgyMywgMjIsIDEsIDIxLCAtMjEsIC0xLCAtMjIsIC0yMykKICAgIERJUk4gPSB7MjE6IDEsIDIyOiAyLCAyMzogMywgMTogNCwgLTIxOiA1LCAtMjI6IDYsIC0yMzogNywgLTE6IDh9CgogICAgQlQgPSAoKEZhbHNlLCBGYWxzZSwgVHJ1ZSksIChUcnVlLCBGYWxzZSwgRmFsc2UpLCAoRmFsc2UsIFRydWUsIEZhbHNlKSkKICAgIFBSRUQgPSAoMSwgMiwgMCkKICAgIFBSRVkgPSAoMiwgMCwgMSkKICAgIExPID0gKDEsIDExKQoKICAgICMgTeG7nyBy4buZbmcgYuG6o25nIHRy4buNbmcgc+G7kSBjaOG6oXkgxJF1YSBsw6puIDI0IGLGsOG7m2MgY2hvIGNoaeG7gXUgZMOgaSBtYXAgMjB4OQogICAgUlQgPSAoCiAgICAgICAgMCwgOTIwLCA1MjAsIDI5MCwgMTcwLCAxMDAsIDY1LCA0NSwgMzIsIDI0LAogICAgICAgIDE4LCAxNCwgMTAsIDgsIDYsIDQsIDMsIDIsIDEsIDAsIDAsIDAsIDAsIDAsIDAKICAgICkKICAgIFVOU1RPUF9SVCA9ICgKICAgICAgICAwLCAxNjUwLCAxMDUwLCA2ODAsIDQ0MCwgMjkwLCAxOTUsIDEzNSwgOTUsIDY4LAogICAgICAgIDQ4LCAzNCwgMjQsIDE3LCAxMiwgOCwgNSwgMywgMSwgMCwgMCwgMCwgMCwgMCwgMAogICAgKQoKICAgIFBBU1NfT04gPSBUcnVlCiAgICBQQVNTX1NMRUVQID0gMy40CiAgICBQQVNTX1JPT1QgPSAxMAogICAgUEFTU19JTiA9IDgKICAgIEVMSU0xID0gNjUKICAgIEVMSU0yID0gMAogICAgUEFTU00gPSAoLTEsIDAsIC0xLCAtMSwgMCkKCiAgICAjIFjDoWMgxJHhu4tuaCBoxrDhu5tuZyB4deG6pXQgcGjDoXQgKHRyw6FpIGhheSBwaOG6o2kga2hpIHhvYXkgMTgwIMSR4buZKQogICAgYWxseV9saXN0ID0gbGlzdChnYW1lU3RhdGUuYWxseSkKICAgIGxlZnRfc2lkZSA9IChzdW0ocC54IGZvciBwIGluIGFsbHlfbGlzdCkgPD0gMTAgKiBtYXgoMSwgbGVuKGFsbHlfbGlzdCkpKQoKICAgIHJlc3RhcnRlZCA9ICgndGFicycgbm90IGluIG1lbW8pIGFuZCB0dXJuID4gMQogICAgaWYgcmVzdGFydGVkOgogICAgICAgIG1lbW9bJ3BjJ10gPSAzCgogICAgdGFicyA9IG1lbW8uZ2V0KCd0YWJzJykKICAgIGlmIHRhYnMgaXMgTm9uZSBvciBtZW1vLmdldCgnbGVmdF9zaWRlJykgIT0gbGVmdF9zaWRlOgogICAgICAgIG1lbW9bJ2xlZnRfc2lkZSddID0gbGVmdF9zaWRlCgogICAgICAgICMgxJDhurd0IGPhu6luZyAyIGto4buRaSB0xrDhu51uZyDEkWVuICg3eDMgw7QpIHbDoCBk4bqjaSA1IGPhu50gbeG7pWMgdGnDqnUgY+G7p2EgbWFwIDIweDkKICAgICAgICBpZiBsZWZ0X3NpZGU6CiAgICAgICAgICAgIFdBTExfU0VUID0gZnJvemVuc2V0KAogICAgICAgICAgICAgICAgeSAqIFNUUklERSArIHggZm9yIHggaW4gcmFuZ2UoMTMsIDIwKSBmb3IgeSBpbiAoMSwgMiwgMywgNywgOCwgOSkKICAgICAgICAgICAgKQogICAgICAgICAgICBHT0FMMCA9IGZyb3plbnNldCh5ICogU1RSSURFICsgMjAgZm9yIHkgaW4gcmFuZ2UoMywgOCkpCiAgICAgICAgICAgIEdPQUwxID0gZnJvemVuc2V0KHkgKiBTVFJJREUgKyAxMiBmb3IgeSBpbiByYW5nZSgzLCA4KSkKICAgICAgICBlbHNlOgogICAgICAgICAgICBXQUxMX1NFVCA9IGZyb3plbnNldCgKICAgICAgICAgICAgICAgIHkgKiBTVFJJREUgKyB4IGZvciB4IGluIHJhbmdlKDIsIDkpIGZvciB5IGluICgxLCAyLCAzLCA3LCA4LCA5KQogICAgICAgICAgICApCiAgICAgICAgICAgIEdPQUwwID0gZnJvemVuc2V0KHkgKiBTVFJJREUgKyAxIGZvciB5IGluIHJhbmdlKDMsIDgpKQogICAgICAgICAgICBHT0FMMSA9IGZyb3plbnNldCh5ICogU1RSSURFICsgOSBmb3IgeSBpbiByYW5nZSgzLCA4KSkKCiAgICAgICAgR09BTCA9IChHT0FMMCwgR09BTDEpCiAgICAgICAgY2VsbHMgPSBbCiAgICAgICAgICAgIHkgKiBTVFJJREUgKyB4CiAgICAgICAgICAgIGZvciB5IGluIHJhbmdlKDEsIEggKyAxKQogICAgICAgICAgICBmb3IgeCBpbiByYW5nZSgxLCBXICsgMSkKICAgICAgICAgICAgaWYgKHkgKiBTVFJJREUgKyB4KSBub3QgaW4gV0FMTF9TRVQKICAgICAgICBdCiAgICAgICAgdmFsaWRfc2V0ID0gc2V0KGNlbGxzKQoKICAgICAgICBuYjBfc2V0ID0ge2cgKyBvZmYgZm9yIGcgaW4gR09BTDAgZm9yIG9mZiBpbiBPRkZTIGlmIChnICsgb2ZmKSBpbiB2YWxpZF9zZXQgYW5kIChnICsgb2ZmKSBub3QgaW4gR09BTDB9CiAgICAgICAgbmIxX3NldCA9IHtnICsgb2ZmIGZvciBnIGluIEdPQUwxIGZvciBvZmYgaW4gT0ZGUyBpZiAoZyArIG9mZikgaW4gdmFsaWRfc2V0IGFuZCAoZyArIG9mZikgbm90IGluIEdPQUwxfQogICAgICAgIE5CID0gKHR1cGxlKG5iMF9zZXQpLCB0dXBsZShuYjFfc2V0KSkKICAgICAgICBERUZfU1EgPSAoR09BTDAgfCBuYjBfc2V0LCBHT0FMMSB8IG5iMV9zZXQpCgogICAgICAgICMgQkZTIHTDrW5oIGtob+G6o25nIGPDoWNoIG5n4bqvbiBuaOG6pXQgdsOybmcgcXVhIHTGsOG7nW5nIHThu5tpIGThuqNpIDUgY+G7nSAoRDAsIEQxKQogICAgICAgIE1BWF9EID0gNDAKICAgICAgICBEMCA9IFtNQVhfRF0gKiBTSVpFCiAgICAgICAgZHEgPSBkZXF1ZShHT0FMMCkKICAgICAgICBmb3IgZyBpbiBHT0FMMDoKICAgICAgICAgICAgRDBbZ10gPSAwCiAgICAgICAgd2hpbGUgZHE6CiAgICAgICAgICAgIHUgPSBkcS5wb3BsZWZ0KCkKICAgICAgICAgICAgZHUgPSBEMFt1XSArIDEKICAgICAgICAgICAgZm9yIG9mZiBpbiBPRkZTOgogICAgICAgICAgICAgICAgdiA9IHUgKyBvZmYKICAgICAgICAgICAgICAgIGlmIHYgaW4gdmFsaWRfc2V0IGFuZCBkdSA8IEQwW3ZdOgogICAgICAgICAgICAgICAgICAgIEQwW3ZdID0gZHUKICAgICAgICAgICAgICAgICAgICBkcS5hcHBlbmQodikKCiAgICAgICAgRDEgPSBbTUFYX0RdICogU0laRQogICAgICAgIGRxID0gZGVxdWUoR09BTDEpCiAgICAgICAgZm9yIGcgaW4gR09BTDE6CiAgICAgICAgICAgIEQxW2ddID0gMAogICAgICAgIHdoaWxlIGRxOgogICAgICAgICAgICB1ID0gZHEucG9wbGVmdCgpCiAgICAgICAgICAgIGR1ID0gRDFbdV0gKyAxCiAgICAgICAgICAgIGZvciBvZmYgaW4gT0ZGUzoKICAgICAgICAgICAgICAgIHYgPSB1ICsgb2ZmCiAgICAgICAgICAgICAgICBpZiB2IGluIHZhbGlkX3NldCBhbmQgZHUgPCBEMVt2XToKICAgICAgICAgICAgICAgICAgICBEMVt2XSA9IGR1CiAgICAgICAgICAgICAgICAgICAgZHEuYXBwZW5kKHYpCgogICAgICAgICMgQkZTIHTDrW5oIGtob+G6o25nIGPDoWNoIHPEg24gxJF14buVaSBuw6kgdMaw4budbmcgZ2nhu69hIG3hu41pIGPhurdwIMO0IGjhu6NwIGzhu4cgKERULCBNRFQpCiAgICAgICAgRFQgPSBbW01BWF9EXSAqIFNJWkUgZm9yIF8gaW4gcmFuZ2UoU0laRSldCiAgICAgICAgTURUID0gW1tNQVhfRCAqIDJdICogU0laRSBmb3IgXyBpbiByYW5nZShTSVpFKV0KICAgICAgICBmb3Igc3JjIGluIGNlbGxzOgogICAgICAgICAgICByb3cgPSBEVFtzcmNdCiAgICAgICAgICAgIG1yb3cgPSBNRFRbc3JjXQogICAgICAgICAgICByb3dbc3JjXSA9IDAKICAgICAgICAgICAgbXJvd1tzcmNdID0gMAogICAgICAgICAgICBkcSA9IGRlcXVlKFtzcmNdKQogICAgICAgICAgICB3aGlsZSBkcToKICAgICAgICAgICAgICAgIHUgPSBkcS5wb3BsZWZ0KCkKICAgICAgICAgICAgICAgIGR1ID0gcm93W3VdICsgMQogICAgICAgICAgICAgICAgZm9yIG9mZiBpbiBPRkZTOgogICAgICAgICAgICAgICAgICAgIHYgPSB1ICsgb2ZmCiAgICAgICAgICAgICAgICAgICAgaWYgdiBpbiB2YWxpZF9zZXQgYW5kIGR1IDwgcm93W3ZdOgogICAgICAgICAgICAgICAgICAgICAgICByb3dbdl0gPSBkdQogICAgICAgICAgICAgICAgICAgICAgICBtcm93W3ZdID0gZHUgKiAyCiAgICAgICAgICAgICAgICAgICAgICAgIGRxLmFwcGVuZCh2KQoKICAgICAgICBtYXhfZDAgPSBtYXgoKEQwW2FdIGZvciBhIGluIGNlbGxzIGlmIEQwW2FdIDwgTUFYX0QpLCBkZWZhdWx0PTEpCiAgICAgICAgbWF4X2QxID0gbWF4KChEMVthXSBmb3IgYSBpbiBjZWxscyBpZiBEMVthXSA8IE1BWF9EKSwgZGVmYXVsdD0xKQogICAgICAgIEFEVjAgPSBbMF0gKiBTSVpFCiAgICAgICAgQURWMSA9IFswXSAqIFNJWkUKICAgICAgICBDRU5URVIgPSBbMF0gKiBTSVpFCiAgICAgICAgZm9yIGEgaW4gY2VsbHM6CiAgICAgICAgICAgIHggPSBhICUgU1RSSURFCiAgICAgICAgICAgIHkgPSBhIC8vIFNUUklERQogICAgICAgICAgICBBRFYwW2FdID0gbWF4KDAsIG1heF9kMCAtIEQwW2FdKQogICAgICAgICAgICBBRFYxW2FdID0gbWF4KDAsIG1heF9kMSAtIEQxW2FdKQogICAgICAgICAgICBjeCA9IGFicyh4IC0gMTAuNSkKICAgICAgICAgICAgY3kgPSBhYnMoeSAtIDUuMCkKICAgICAgICAgICAgQ0VOVEVSW2FdID0gbWF4KDAsIGludCg0IC0gbWF4KGN4IC8gMi4wLCBjeSkpKQoKICAgICAgICBNVEFCMCA9IFsoKSBmb3IgXyBpbiByYW5nZShTSVpFKV0KICAgICAgICBNVEFCMSA9IFsoKSBmb3IgXyBpbiByYW5nZShTSVpFKV0KICAgICAgICBmb3IgYSBpbiBjZWxsczoKICAgICAgICAgICAgbTAgPSBbXQogICAgICAgICAgICBtMSA9IFtdCiAgICAgICAgICAgIGZvciBvZmYgaW4gT0ZGUzoKICAgICAgICAgICAgICAgIHEgPSBhICsgb2ZmCiAgICAgICAgICAgICAgICBpZiBxIGluIHZhbGlkX3NldDoKICAgICAgICAgICAgICAgICAgICBoX2l4ID0gYSAqIFNJWkUgKyBxCiAgICAgICAgICAgICAgICAgICAgZncwX2IgPSAoRDBbYV0gLSBEMFtxXSkgKiAyCiAgICAgICAgICAgICAgICAgICAgZncxX2IgPSAoRDFbYV0gLSBEMVtxXSkgKiAyCiAgICAgICAgICAgICAgICAgICAgbTAuYXBwZW5kKChxLCBmdzBfYiwgaF9peCwgMSBpZiBxIGluIG5iMF9zZXQgZWxzZSAwKSkKICAgICAgICAgICAgICAgICAgICBtMS5hcHBlbmQoKHEsIGZ3MV9iLCBoX2l4LCAxIGlmIHEgaW4gbmIxX3NldCBlbHNlIDApKQogICAgICAgICAgICBtMC5zb3J0KGtleT1sYW1iZGEgaXRlbTogaXRlbVsxXSwgcmV2ZXJzZT1UcnVlKQogICAgICAgICAgICBtMS5zb3J0KGtleT1sYW1iZGEgaXRlbTogaXRlbVsxXSwgcmV2ZXJzZT1UcnVlKQogICAgICAgICAgICBNVEFCMFthXSA9IHR1cGxlKG0wKQogICAgICAgICAgICBNVEFCMVthXSA9IHR1cGxlKG0xKQogICAgICAgIE1UQUIgPSAodHVwbGUoTVRBQjApLCB0dXBsZShNVEFCMSkpCgogICAgICAgIHJ6ID0gcmFuZG9tLlJhbmRvbSgyMDI2MDQwMikKICAgICAgICBaID0gdHVwbGUodHVwbGUocnouZ2V0cmFuZGJpdHMoNTIpIGZvciBfIGluIHJhbmdlKFNJWkUpKSBmb3IgXyBpbiByYW5nZSgyMCkpCiAgICAgICAgWlMgPSByei5nZXRyYW5kYml0cyg1MikKICAgICAgICBQQVNTSyA9IHJ6LmdldHJhbmRiaXRzKDUyKQogICAgICAgIHRhYnMgPSAoV0FMTF9TRVQsIEdPQUwsIE5CLCBERUZfU1EsIERULCBNRFQsIEFEVjAsIEFEVjEsIEQwLCBEMSwgQ0VOVEVSLCBNVEFCLCBaLCBaUywgUEFTU0spCiAgICAgICAgbWVtb1sndGFicyddID0gdGFicwoKICAgIFdBTExfU0VULCBHT0FMLCBOQiwgREVGX1NRLCBEVCwgTURULCBBRFYwLCBBRFYxLCBEMCwgRDEsIENFTlRFUiwgTVRBQiwgWiwgWlMsIFBBU1NLID0gdGFicwoKICAgIHVzZWQgPSBtZW1vLmdldCgndXNlZCcsIDAuMCkKICAgIGxlZnQgPSBtYXgoMSwgKG1heFQgLSB0dXJuKSAvLyAyICsgMSkKICAgIGlmIHR1cm4gPD0gMToKICAgICAgICBidWRnZXQgPSAwLjgyCiAgICBlbHNlOgogICAgICAgIGJ1ZGdldCA9IG1pbigwLjgxLCBtYXgoMC4wNCwgKDE1NS4wIC0gdXNlZCkgLyBtaW4obGVmdCwgMTUwKSkpCiAgICBkZWFkbGluZSA9IHN0YXJ0X3RpbWUgKyBidWRnZXQKCiAgICAjIEThu7FuZyBiw6BuIGPhu50gMjB4OTogbmdvw6BpIGJpw6puIHbDoCDDtCB0xrDhu51uZyDEkWVuIMSR4buBdSBsw6AgLTEKICAgIGJvYXJkID0gWy0xXSAqIFNJWkUKICAgIGZvciB5eSBpbiByYW5nZSgxLCBIICsgMSk6CiAgICAgICAgYmFzZV95ID0geXkgKiBTVFJJREUKICAgICAgICBmb3IgeHggaW4gcmFuZ2UoMSwgVyArIDEpOgogICAgICAgICAgICBwb3MgPSBiYXNlX3kgKyB4eAogICAgICAgICAgICBpZiBwb3Mgbm90IGluIFdBTExfU0VUOgogICAgICAgICAgICAgICAgYm9hcmRbcG9zXSA9IDAKCiAgICB0cCA9IFswXSAqIDIwCiAgICBwcyA9IFstMV0gKiAyMAogICAgVEkgPSB7J1InOiAwLCAnUCc6IDEsICdTJzogMn0KICAgIGNudCA9IFswLCAwXQogICAgZm9yIHAgaW4gYWxseV9saXN0OgogICAgICAgIGMgPSBwLnBpZAogICAgICAgIHRwW2NdID0gVElbcC5UeXBlXQogICAgICAgIHBvcyA9IHAueSAqIFNUUklERSArIHAueAogICAgICAgIHBzW2NdID0gcG9zCiAgICAgICAgYm9hcmRbcG9zXSA9IGMKICAgICAgICBjbnRbMF0gKz0gMQogICAgZm9yIHAgaW4gZ2FtZVN0YXRlLm9wcG9uZW50OgogICAgICAgIGMgPSAxMCArIHAucGlkCiAgICAgICAgdHBbY10gPSBUSVtwLlR5cGVdCiAgICAgICAgcG9zID0gcC55ICogU1RSSURFICsgcC54CiAgICAgICAgcHNbY10gPSBwb3MKICAgICAgICBib2FyZFtwb3NdID0gYwogICAgICAgIGNudFsxXSArPSAxCgogICAgdHQgPSBtZW1vLmdldCgndHQnKQogICAgaWYgdHQgaXMgTm9uZSBvciBsZW4odHQpID4gMTIwMDAwIG9yIHR1cm4gPD0gMToKICAgICAgICB0dCA9IHt9CiAgICAgICAgbWVtb1sndHQnXSA9IHR0CgogICAgSElTVF9TSVpFID0gU0laRSAqIFNJWkUKICAgIEhJU1QgPSBtZW1vLmdldCgnaGlzdCcpCiAgICBpZiBISVNUIGlzIE5vbmUgb3IgbGVuKEhJU1QpICE9IEhJU1RfU0laRSBvciB0dXJuIDw9IDE6CiAgICAgICAgSElTVCA9IFswXSAqIEhJU1RfU0laRQogICAgICAgIG1lbW9bJ2hpc3QnXSA9IEhJU1QKICAgIGVsc2U6CiAgICAgICAgZm9yIGkgaW4gcmFuZ2UoSElTVF9TSVpFKToKICAgICAgICAgICAgaWYgSElTVFtpXToKICAgICAgICAgICAgICAgIEhJU1RbaV0gPj49IDEKCiAgICBLSUxMRVIgPSBbTm9uZV0gKiA2NAogICAgbm9kZXMgPSBbMF0KICAgIGFib3J0ID0gW0ZhbHNlXQoKICAgIHRvdGFsID0gY250WzBdICsgY250WzFdCiAgICBpZiBtZW1vLmdldCgncHJldl90b3RhbCcpICE9IHRvdGFsOgogICAgICAgIG1lbW9bJ3ByZXZfdG90YWwnXSA9IHRvdGFsCiAgICAgICAgbWVtb1snY2FwdF90dXJuJ10gPSB0dXJuCiAgICAgICAgbWVtb1snY2ZnJ10gPSB7fQogICAgc3RhZyA9ICh0dXJuIC0gbWVtby5nZXQoJ2NhcHRfdHVybicsIHR1cm4pKSAvLyAyCiAgICBhaGVhZCA9IGNudFswXSA+IGNudFsxXQogICAgYmVoaW5kID0gY250WzBdIDwgY250WzFdCgogICAgSyA9IDUgKyBtaW4oOCwgdHVybiAvLyAyNSkKICAgIGlmIG5vdCBiZWhpbmQgYW5kIHN0YWcgPiAxNjoKICAgICAgICBLICs9IG1pbig3LCAoc3RhZyAtIDE2KSAvLyA2KQogICAgaWYgYmVoaW5kOgogICAgICAgIEhXID0gMwogICAgZWxpZiBzdGFnID4gMTY6CiAgICAgICAgSFcgPSAxMQogICAgZWxzZToKICAgICAgICBIVyA9IDYKICAgIGlmIGFoZWFkIGFuZCBzdGFnID4gMjY6CiAgICAgICAgRFAgPSAoMCwgMjIwLCAxMjAsIDU1KQogICAgZWxzZToKICAgICAgICBEUCA9ICgwLCAzMzAsIDE3NSwgODApCgogICAgcm9sZXMgPSB7fQogICAgZV90eXBlc19hbGl2ZSA9IFswLCAwLCAwXQogICAgZV9uZWFyX2hvbWUgPSBbXQogICAgZV9uZWFyX2F3YXkgPSBbMCwgMCwgMF0KICAgIGZvciBjIGluIHJhbmdlKDExLCAyMCk6CiAgICAgICAgcSA9IHBzW2NdCiAgICAgICAgaWYgcSA+PSAwOgogICAgICAgICAgICB1ID0gdHBbY10KICAgICAgICAgICAgZV90eXBlc19hbGl2ZVt1XSArPSAxCiAgICAgICAgICAgIGlmIEQxW3FdIDw9IDQ6CiAgICAgICAgICAgICAgICBlX25lYXJfaG9tZS5hcHBlbmQoKEQxW3FdLCBxLCB1KSkKICAgICAgICAgICAgaWYgRDBbcV0gPD0gMjoKICAgICAgICAgICAgICAgIGVfbmVhcl9hd2F5W3VdICs9IDEKICAgIGVfbmVhcl9ob21lLnNvcnQoKQoKICAgIGRlZl9hc3NpZ25lZCA9IHNldCgpCiAgICBmb3IgZF9oLCBxX2gsIHVfaCBpbiBlX25lYXJfaG9tZToKICAgICAgICBuZWVkX3QgPSBQUkVEW3VfaF0KICAgICAgICBiZXN0X2MgPSAwCiAgICAgICAgYmVzdF9kID0gOTkKICAgICAgICBmb3IgYyBpbiByYW5nZSgxLCAxMCk6CiAgICAgICAgICAgIHAgPSBwc1tjXQogICAgICAgICAgICBpZiBwID49IDAgYW5kIHRwW2NdID09IG5lZWRfdCBhbmQgYyBub3QgaW4gZGVmX2Fzc2lnbmVkOgogICAgICAgICAgICAgICAgZF9jID0gRDFbcF0KICAgICAgICAgICAgICAgIGlmIGRfYyA8IGJlc3RfZDoKICAgICAgICAgICAgICAgICAgICBiZXN0X2QgPSBkX2MKICAgICAgICAgICAgICAgICAgICBiZXN0X2MgPSBjCiAgICAgICAgaWYgYmVzdF9jOgogICAgICAgICAgICByb2xlc1tiZXN0X2NdID0gJ0RFRkVOREVSJwogICAgICAgICAgICBkZWZfYXNzaWduZWQuYWRkKGJlc3RfYykKCiAgICBpZiBub3QgZGVmX2Fzc2lnbmVkOgogICAgICAgIGJlc3RfYyA9IDAKICAgICAgICBiZXN0X2QgPSA5OQogICAgICAgIGZvciBjIGluIHJhbmdlKDEsIDEwKToKICAgICAgICAgICAgcCA9IHBzW2NdCiAgICAgICAgICAgIGlmIHAgPj0gMCBhbmQgZV90eXBlc19hbGl2ZVtQUkVZW3RwW2NdXV0gPiAwOgogICAgICAgICAgICAgICAgZF9jID0gRDFbcF0KICAgICAgICAgICAgICAgIGlmIGRfYyA8IGJlc3RfZDoKICAgICAgICAgICAgICAgICAgICBiZXN0X2QgPSBkX2MKICAgICAgICAgICAgICAgICAgICBiZXN0X2MgPSBjCiAgICAgICAgaWYgYmVzdF9jIGFuZCBiZXN0X2QgPD0gMzoKICAgICAgICAgICAgcm9sZXNbYmVzdF9jXSA9ICdERUZFTkRFUicKICAgICAgICAgICAgZGVmX2Fzc2lnbmVkLmFkZChiZXN0X2MpCgogICAgcnVubmVyX2NhbmRzID0gW10KICAgIGZvciBjIGluIHJhbmdlKDEsIDEwKToKICAgICAgICBwID0gcHNbY10KICAgICAgICBpZiBwID49IDAgYW5kIGMgbm90IGluIGRlZl9hc3NpZ25lZDoKICAgICAgICAgICAgdCA9IHRwW2NdCiAgICAgICAgICAgIGltbSA9IDEgaWYgZV90eXBlc19hbGl2ZVtQUkVEW3RdXSA9PSAwIGVsc2UgMAogICAgICAgICAgICBicmsgPSAxIGlmIGVfbmVhcl9hd2F5W1BSRVlbdF1dID4gMCBlbHNlIDAKICAgICAgICAgICAgcnVubmVyX2NhbmRzLmFwcGVuZCgoRDBbcF0gLSAyICogaW1tIC0gYnJrLCAtQURWMFtwXSwgYykpCiAgICBydW5uZXJfY2FuZHMuc29ydCgpCiAgICBmb3IgaWR4X3IgaW4gcmFuZ2UobWluKDIsIGxlbihydW5uZXJfY2FuZHMpKSk6CiAgICAgICAgcm9sZXNbcnVubmVyX2NhbmRzW2lkeF9yXVsyXV0gPSAnUlVOTkVSJwogICAgZm9yIGMgaW4gcmFuZ2UoMSwgMTApOgogICAgICAgIGlmIHBzW2NdID49IDAgYW5kIGMgbm90IGluIHJvbGVzOgogICAgICAgICAgICByb2xlc1tjXSA9ICdIVU5URVInCiAgICBtZW1vWydyb2xlcyddID0gcm9sZXMKCiAgICBkZWYgd2luc19ub3cocyk6CiAgICAgICAgbG8gPSBMT1tzXQogICAgICAgIGhpID0gbG8gKyA4CiAgICAgICAgZm9yIGcgaW4gR09BTFtzXToKICAgICAgICAgICAgdjAgPSBib2FyZFtnXQogICAgICAgICAgICBpZiB2MCA9PSAwOgogICAgICAgICAgICAgICAgZm9yIG9mZiBpbiBPRkZTOgogICAgICAgICAgICAgICAgICAgIHYgPSBib2FyZFtnICsgb2ZmXQogICAgICAgICAgICAgICAgICAgIGlmIGxvIDw9IHYgPD0gaGk6CiAgICAgICAgICAgICAgICAgICAgICAgIHJldHVybiBUcnVlCiAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICB0ID0gdHBbdjBdCiAgICAgICAgICAgICAgICBmb3Igb2ZmIGluIE9GRlM6CiAgICAgICAgICAgICAgICAgICAgdiA9IGJvYXJkW2cgKyBvZmZdCiAgICAgICAgICAgICAgICAgICAgaWYgbG8gPD0gdiA8PSBoaSBhbmQgQlRbdHBbdl1dW3RdOgogICAgICAgICAgICAgICAgICAgICAgICByZXR1cm4gVHJ1ZQogICAgICAgIHJldHVybiBGYWxzZQoKICAgIGRlZiBnZW4ocywgbW9kZSk6CiAgICAgICAgcmVzID0gW10KICAgICAgICBsbyA9IExPW3NdCiAgICAgICAgZWxvID0gTE9bMSAtIHNdCiAgICAgICAgZWhpID0gZWxvICsgOAogICAgICAgIG10YWIgPSBNVEFCW3NdCiAgICAgICAgZ3NldCA9IEdPQUxbc10KICAgICAgICBlZ3NldCA9IEdPQUxbMSAtIHNdCiAgICAgICAgZm9yIGMgaW4gcmFuZ2UobG8sIGxvICsgOSk6CiAgICAgICAgICAgIHAgPSBwc1tjXQogICAgICAgICAgICBpZiBwIDwgMDoKICAgICAgICAgICAgICAgIGNvbnRpbnVlCiAgICAgICAgICAgIHQgPSB0cFtjXQogICAgICAgICAgICBidCA9IEJUW3RdCiAgICAgICAgICAgIGZvciBxLCBmd19iLCBoX2l4LCBpc19uYiBpbiBtdGFiW3BdOgogICAgICAgICAgICAgICAgdiA9IGJvYXJkW3FdCiAgICAgICAgICAgICAgICBpZiB2ID09IDA6CiAgICAgICAgICAgICAgICAgICAgaWYgbW9kZSA9PSAwOgogICAgICAgICAgICAgICAgICAgICAgICBoID0gSElTVFtoX2l4XQogICAgICAgICAgICAgICAgICAgICAgICByZXMuYXBwZW5kKChmd19iICsgKGggaWYgaCA8IDcyIGVsc2UgNzIpLCBjLCBwLCBxLCAwKSkKICAgICAgICAgICAgICAgICAgICBlbGlmIG1vZGUgPT0gMiBhbmQgaXNfbmI6CiAgICAgICAgICAgICAgICAgICAgICAgIGZvciBvZmYgaW4gT0ZGUzoKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGdxID0gcSArIG9mZgogICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYgZ3EgaW4gZ3NldDoKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB2ZyA9IGJvYXJkW2dxXQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmIHZnID09IDAgb3IgKGVsbyA8PSB2ZyA8PSBlaGkgYW5kIGJ0W3RwW3ZnXV0pOgogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICByZXMuYXBwZW5kKCg4MjAgKyBmd19iLCBjLCBwLCBxLCAwKSkKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWsKICAgICAgICAgICAgICAgIGVsaWYgZWxvIDw9IHYgPD0gZWhpOgogICAgICAgICAgICAgICAgICAgIHV0ID0gdHBbdl0KICAgICAgICAgICAgICAgICAgICBpZiBidFt1dF06CiAgICAgICAgICAgICAgICAgICAgICAgIHJlcy5hcHBlbmQoKDEwNTAgKyBmd19iICsgKDkwIGlmIHEgaW4gZWdzZXQgb3IgRDFbcV0gPD0gMiBlbHNlIDApLCBjLCBwLCBxLCB2KSkKICAgICAgICByZXR1cm4gcmVzCgogICAgZGVmIGV2YWx1YXRlX3JhdyhzKToKICAgICAgICBBX3AgPSBbXQogICAgICAgIEFfdCA9IFtdCiAgICAgICAgQl9wID0gW10KICAgICAgICBCX3QgPSBbXQogICAgICAgIGNBMCA9IGNBMSA9IGNBMiA9IDAKICAgICAgICBjQjAgPSBjQjEgPSBjQjIgPSAwCiAgICAgICAgZm9yIGMgaW4gcmFuZ2UoMSwgMTApOgogICAgICAgICAgICBwID0gcHNbY10KICAgICAgICAgICAgaWYgcCA+PSAwOgogICAgICAgICAgICAgICAgdCA9IHRwW2NdCiAgICAgICAgICAgICAgICBBX3AuYXBwZW5kKHApCiAgICAgICAgICAgICAgICBBX3QuYXBwZW5kKHQpCiAgICAgICAgICAgICAgICBpZiB0ID09IDA6CiAgICAgICAgICAgICAgICAgICAgY0EwICs9IDEKICAgICAgICAgICAgICAgIGVsaWYgdCA9PSAxOgogICAgICAgICAgICAgICAgICAgIGNBMSArPSAxCiAgICAgICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgICAgIGNBMiArPSAxCiAgICAgICAgZm9yIGMgaW4gcmFuZ2UoMTEsIDIwKToKICAgICAgICAgICAgcCA9IHBzW2NdCiAgICAgICAgICAgIGlmIHAgPj0gMDoKICAgICAgICAgICAgICAgIHQgPSB0cFtjXQogICAgICAgICAgICAgICAgQl9wLmFwcGVuZChwKQogICAgICAgICAgICAgICAgQl90LmFwcGVuZCh0KQogICAgICAgICAgICAgICAgaWYgdCA9PSAwOgogICAgICAgICAgICAgICAgICAgIGNCMCArPSAxCiAgICAgICAgICAgICAgICBlbGlmIHQgPT0gMToKICAgICAgICAgICAgICAgICAgICBjQjEgKz0gMQogICAgICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgICAgICBjQjIgKz0gMQoKICAgICAgICBuYSA9IGxlbihBX3ApCiAgICAgICAgbmIgPSBsZW4oQl9wKQogICAgICAgIGlmIG5hID09IDA6CiAgICAgICAgICAgIHJldHVybiAtV0lOICsgMTAwIGlmIHMgPT0gMCBlbHNlIFdJTiAtIDEwMAogICAgICAgIGlmIG5iID09IDA6CiAgICAgICAgICAgIHJldHVybiBXSU4gLSAxMDAgaWYgcyA9PSAwIGVsc2UgLVdJTiArIDEwMAoKICAgICAgICBjQSA9IChjQTAsIGNBMSwgY0EyKQogICAgICAgIGNCID0gKGNCMCwgY0IxLCBjQjIpCgogICAgICAgIHYgPSAxMDUwICogKG5hIC0gbmIpICsgMzIwMCAqIChuYSAtIG5iKSAvLyAobmEgKyBuYikKCiAgICAgICAgZm9yIHQgaW4gKDAsIDEsIDIpOgogICAgICAgICAgICBwcmVkID0gUFJFRFt0XQogICAgICAgICAgICBwcmV5ID0gUFJFWVt0XQogICAgICAgICAgICBjYSA9IGNBW3RdCiAgICAgICAgICAgIGNiID0gY0JbdF0KICAgICAgICAgICAgaWYgY2E6CiAgICAgICAgICAgICAgICBpZiBjQltwcmVkXSA9PSAwOgogICAgICAgICAgICAgICAgICAgIHYgKz0gY2EgKiAoNTAwIGlmIGNCW3RdID09IDAgZWxzZSAzNjApCiAgICAgICAgICAgICAgICBlbGlmIGNCW3ByZWRdID09IDEgYW5kIGNBW3ByZXldID4gMDoKICAgICAgICAgICAgICAgICAgICB2ICs9IGNhICogRUxJTTEKICAgICAgICAgICAgICAgIGVsaWYgRUxJTTIgYW5kIGNCW3ByZWRdID09IDIgYW5kIGNBW3ByZXldID49IDI6CiAgICAgICAgICAgICAgICAgICAgdiArPSBjYSAqIEVMSU0yCiAgICAgICAgICAgICAgICB2ICs9IGNhICogKDgwICogY0JbcHJleV0gaWYgY0JbcHJleV0gZWxzZSAtNTApCiAgICAgICAgICAgIGlmIGNiOgogICAgICAgICAgICAgICAgaWYgY0FbcHJlZF0gPT0gMDoKICAgICAgICAgICAgICAgICAgICB2IC09IGNiICogKDUwMCBpZiBjQVt0XSA9PSAwIGVsc2UgMzYwKQogICAgICAgICAgICAgICAgZWxpZiBjQVtwcmVkXSA9PSAxIGFuZCBjQltwcmV5XSA+IDA6CiAgICAgICAgICAgICAgICAgICAgdiAtPSBjYiAqIEVMSU0xCiAgICAgICAgICAgICAgICBlbGlmIEVMSU0yIGFuZCBjQVtwcmVkXSA9PSAyIGFuZCBjQltwcmV5XSA+PSAyOgogICAgICAgICAgICAgICAgICAgIHYgLT0gY2IgKiBFTElNMgogICAgICAgICAgICAgICAgdiAtPSBjYiAqICg4MCAqIGNBW3ByZXldIGlmIGNBW3ByZXldIGVsc2UgLTUwKQoKICAgICAgICBmYXJfZCA9IDQwCiAgICAgICAgaGEgPSBbZmFyX2RdICogbmEKICAgICAgICBwYSA9IFtmYXJfZF0gKiBuYQogICAgICAgIG1hID0gW2Zhcl9kICogMl0gKiBuYQogICAgICAgIGludGEgPSBbOTldICogbmEKICAgICAgICBoYiA9IFtmYXJfZF0gKiBuYgogICAgICAgIHBiID0gW2Zhcl9kXSAqIG5iCiAgICAgICAgbWIgPSBbZmFyX2QgKiAyXSAqIG5iCiAgICAgICAgaW50YiA9IFs5OV0gKiBuYgoKICAgICAgICBmb3IgaSBpbiByYW5nZShuYSk6CiAgICAgICAgICAgIHAgPSBBX3BbaV0KICAgICAgICAgICAgdCA9IEFfdFtpXQogICAgICAgICAgICBkMHAgPSBEMFtwXQogICAgICAgICAgICByb3cgPSBEVFtwXQogICAgICAgICAgICBtcm93ID0gTURUW3BdCiAgICAgICAgICAgIGJ0ID0gQlRbdF0KICAgICAgICAgICAgZm9yIGogaW4gcmFuZ2UobmIpOgogICAgICAgICAgICAgICAgcSA9IEJfcFtqXQogICAgICAgICAgICAgICAgdSA9IEJfdFtqXQogICAgICAgICAgICAgICAgZDBxID0gRDBbcV0KICAgICAgICAgICAgICAgIGQxcSA9IEQxW3FdCiAgICAgICAgICAgICAgICBpZiB1ID09IHQ6CiAgICAgICAgICAgICAgICAgICAgaWYgZDBxIDw9IGQwcCBhbmQgZDBxIDwgaW50YVtpXToKICAgICAgICAgICAgICAgICAgICAgICAgaW50YVtpXSA9IGQwcQogICAgICAgICAgICAgICAgICAgIGlmIEQxW3BdIDw9IGQxcSBhbmQgRDFbcF0gPCBpbnRiW2pdOgogICAgICAgICAgICAgICAgICAgICAgICBpbnRiW2pdID0gRDFbcF0KICAgICAgICAgICAgICAgICAgICBjb250aW51ZQogICAgICAgICAgICAgICAgZCA9IHJvd1txXQogICAgICAgICAgICAgICAgbWQgPSBtcm93W3FdCiAgICAgICAgICAgICAgICBpZiBidFt1XToKICAgICAgICAgICAgICAgICAgICBpZiBkIDwgcGFbaV06CiAgICAgICAgICAgICAgICAgICAgICAgIHBhW2ldID0gZAogICAgICAgICAgICAgICAgICAgIGlmIG1kIDwgbWFbaV06CiAgICAgICAgICAgICAgICAgICAgICAgIG1hW2ldID0gbWQKICAgICAgICAgICAgICAgICAgICBpZiBkIDwgaGJbal06CiAgICAgICAgICAgICAgICAgICAgICAgIGhiW2pdID0gZAogICAgICAgICAgICAgICAgICAgIGlmIEQxW3BdIDw9IGQxcSArIDEgYW5kIEQxW3BdIDwgaW50YltqXToKICAgICAgICAgICAgICAgICAgICAgICAgaW50YltqXSA9IEQxW3BdCiAgICAgICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgICAgIGlmIGQgPCBoYVtpXToKICAgICAgICAgICAgICAgICAgICAgICAgaGFbaV0gPSBkCiAgICAgICAgICAgICAgICAgICAgaWYgZCA8IHBiW2pdOgogICAgICAgICAgICAgICAgICAgICAgICBwYltqXSA9IGQKICAgICAgICAgICAgICAgICAgICBpZiBtZCA8IG1iW2pdOgogICAgICAgICAgICAgICAgICAgICAgICBtYltqXSA9IG1kCiAgICAgICAgICAgICAgICAgICAgaWYgZDBxIDw9IGQwcCArIDEgYW5kIGQwcSA8IGludGFbaV06CiAgICAgICAgICAgICAgICAgICAgICAgIGludGFbaV0gPSBkMHEKCiAgICAgICAgYWR2MCA9IDAKICAgICAgICB0aHIwID0gMAogICAgICAgIGRnMCA9IDAKICAgICAgICBodW50MCA9IDAKICAgICAgICBoYW5nMCA9IDAKICAgICAgICBhd2F5X2d1YXJkX2IgPSBbMCwgMCwgMF0KICAgICAgICBmb3IgaiBpbiByYW5nZShuYik6CiAgICAgICAgICAgIGlmIEQwW0JfcFtqXV0gPD0gMjoKICAgICAgICAgICAgICAgIGF3YXlfZ3VhcmRfYltCX3Rbal1dID0gMQoKICAgICAgICBtYXhfdW5zdG9wID0gbGVuKFVOU1RPUF9SVCkgLSAxCiAgICAgICAgbWF4X3J0ID0gbGVuKFJUKSAtIDEKCiAgICAgICAgZm9yIGkgaW4gcmFuZ2UobmEpOgogICAgICAgICAgICBwID0gQV9wW2ldCiAgICAgICAgICAgIHQgPSBBX3RbaV0KICAgICAgICAgICAgYXAgPSBBRFYwW3BdCiAgICAgICAgICAgIGlmIGNCW1BSRURbdF1dID09IDA6CiAgICAgICAgICAgICAgICBhcCArPSBhcCA+PiAxCiAgICAgICAgICAgIGlmIGF3YXlfZ3VhcmRfYltQUkVZW3RdXToKICAgICAgICAgICAgICAgIGFwICs9IG1heCgwLCAxNCAtIEQwW3BdKSAqIDMKICAgICAgICAgICAgYWR2MCArPSBhcAoKICAgICAgICAgICAgbXAgPSBwYVtpXQogICAgICAgICAgICBpZiBtcCA8IGZhcl9kOgogICAgICAgICAgICAgICAgaHVudDAgKz0gSFcgKiBtYXgoMCwgMTYgLSBtcCkgKyBtYXgoMCwgMzIgLSBtYVtpXSkKICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgIGh1bnQwICs9IENFTlRFUltwXQoKICAgICAgICAgICAgbWggPSBoYVtpXQogICAgICAgICAgICBpZiBtaCA8PSAzOgogICAgICAgICAgICAgICAgcHQgPSBQUkVZW3RdCiAgICAgICAgICAgICAgICByb3cgPSBEVFtwXQogICAgICAgICAgICAgICAgcHJvdCA9IEZhbHNlCiAgICAgICAgICAgICAgICBmb3IgayBpbiByYW5nZShuYSk6CiAgICAgICAgICAgICAgICAgICAgaWYgQV90W2tdID09IHB0IGFuZCByb3dbQV9wW2tdXSA8PSAxOgogICAgICAgICAgICAgICAgICAgICAgICBwcm90ID0gVHJ1ZQogICAgICAgICAgICAgICAgICAgICAgICBicmVhawogICAgICAgICAgICAgICAgaWYgbm90IHByb3Q6CiAgICAgICAgICAgICAgICAgICAgaWYgbWggPD0gMToKICAgICAgICAgICAgICAgICAgICAgICAgZGcwICs9IERQWzFdICsgKDE2MCBpZiBzID09IDEgZWxzZSAwKQogICAgICAgICAgICAgICAgICAgICAgICBoYW5nMCArPSAxCiAgICAgICAgICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgICAgICAgICAgZGcwICs9IERQW21oXQogICAgICAgICAgICAgICAgZWxpZiBtaCA8PSAyOgogICAgICAgICAgICAgICAgICAgIGh1bnQwICs9IDI1CgogICAgICAgICAgICBkID0gRDBbcF0KICAgICAgICAgICAgaWYgaW50YVtpXSA9PSA5OToKICAgICAgICAgICAgICAgIGlmIGQgPD0gbWF4X3Vuc3RvcDoKICAgICAgICAgICAgICAgICAgICB0diA9IFVOU1RPUF9SVFtkXQogICAgICAgICAgICAgICAgICAgIGlmIHR2ID4gdGhyMDoKICAgICAgICAgICAgICAgICAgICAgICAgdGhyMCA9IHR2CiAgICAgICAgICAgIGVsaWYgZCA8PSBtYXhfcnQ6CiAgICAgICAgICAgICAgICB0diA9IFJUW2RdCiAgICAgICAgICAgICAgICBpZiBtaCA8PSAyIG9yIGludGFbaV0gPD0gZDoKICAgICAgICAgICAgICAgICAgICB0diAvLz0gMwogICAgICAgICAgICAgICAgaWYgdHYgPiB0aHIwOgogICAgICAgICAgICAgICAgICAgIHRocjAgPSB0dgoKICAgICAgICBpZiBoYW5nMCA+PSAyOgogICAgICAgICAgICBkZzAgKz0gMzgwICogKGhhbmcwIC0gMSkKCiAgICAgICAgYWR2MSA9IDAKICAgICAgICB0aHIxID0gMAogICAgICAgIGRnMSA9IDAKICAgICAgICBodW50MSA9IDAKICAgICAgICBoYW5nMSA9IDAKICAgICAgICBob21lX2d1YXJkX2EgPSBbMCwgMCwgMF0KICAgICAgICBmb3IgaSBpbiByYW5nZShuYSk6CiAgICAgICAgICAgIGlmIEQxW0FfcFtpXV0gPD0gMjoKICAgICAgICAgICAgICAgIGhvbWVfZ3VhcmRfYVtBX3RbaV1dID0gMQoKICAgICAgICBmb3IgaiBpbiByYW5nZShuYik6CiAgICAgICAgICAgIHEgPSBCX3Bbal0KICAgICAgICAgICAgdSA9IEJfdFtqXQogICAgICAgICAgICBhcSA9IEFEVjFbcV0KICAgICAgICAgICAgaWYgY0FbUFJFRFt1XV0gPT0gMDoKICAgICAgICAgICAgICAgIGFxICs9IGFxID4+IDEKICAgICAgICAgICAgaWYgaG9tZV9ndWFyZF9hW1BSRVlbdV1dOgogICAgICAgICAgICAgICAgYXEgKz0gbWF4KDAsIDE0IC0gRDFbcV0pICogMwogICAgICAgICAgICBhZHYxICs9IGFxCgogICAgICAgICAgICBtcCA9IHBiW2pdCiAgICAgICAgICAgIGlmIG1wIDwgZmFyX2Q6CiAgICAgICAgICAgICAgICBodW50MSArPSBIVyAqIG1heCgwLCAxNiAtIG1wKSArIG1heCgwLCAzMiAtIG1iW2pdKQogICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgaHVudDEgKz0gQ0VOVEVSW3FdCgogICAgICAgICAgICBtaCA9IGhiW2pdCiAgICAgICAgICAgIGlmIG1oIDw9IDM6CiAgICAgICAgICAgICAgICBwdCA9IFBSRVlbdV0KICAgICAgICAgICAgICAgIHJvdyA9IERUW3FdCiAgICAgICAgICAgICAgICBwcm90ID0gRmFsc2UKICAgICAgICAgICAgICAgIGZvciBrIGluIHJhbmdlKG5iKToKICAgICAgICAgICAgICAgICAgICBpZiBCX3Rba10gPT0gcHQgYW5kIHJvd1tCX3Bba11dIDw9IDE6CiAgICAgICAgICAgICAgICAgICAgICAgIHByb3QgPSBUcnVlCiAgICAgICAgICAgICAgICAgICAgICAgIGJyZWFrCiAgICAgICAgICAgICAgICBpZiBub3QgcHJvdDoKICAgICAgICAgICAgICAgICAgICBpZiBtaCA8PSAxOgogICAgICAgICAgICAgICAgICAgICAgICBkZzEgKz0gRFBbMV0gKyAoMTYwIGlmIHMgPT0gMCBlbHNlIDApCiAgICAgICAgICAgICAgICAgICAgICAgIGhhbmcxICs9IDEKICAgICAgICAgICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgICAgICAgICBkZzEgKz0gRFBbbWhdCiAgICAgICAgICAgICAgICBlbGlmIG1oIDw9IDI6CiAgICAgICAgICAgICAgICAgICAgaHVudDEgKz0gMjUKCiAgICAgICAgICAgIGQgPSBEMVtxXQogICAgICAgICAgICBpZiBpbnRiW2pdID09IDk5OgogICAgICAgICAgICAgICAgaWYgZCA8PSBtYXhfdW5zdG9wOgogICAgICAgICAgICAgICAgICAgIHR2ID0gVU5TVE9QX1JUW2RdCiAgICAgICAgICAgICAgICAgICAgaWYgdHYgPiB0aHIxOgogICAgICAgICAgICAgICAgICAgICAgICB0aHIxID0gdHYKICAgICAgICAgICAgZWxpZiBkIDw9IG1heF9ydDoKICAgICAgICAgICAgICAgIHR2ID0gUlRbZF0KICAgICAgICAgICAgICAgIGlmIG1oIDw9IDIgb3IgaW50YltqXSA8PSBkOgogICAgICAgICAgICAgICAgICAgIHR2IC8vPSAzCiAgICAgICAgICAgICAgICBpZiB0diA+IHRocjE6CiAgICAgICAgICAgICAgICAgICAgdGhyMSA9IHR2CgogICAgICAgIGlmIGhhbmcxID49IDI6CiAgICAgICAgICAgIGRnMSArPSAzODAgKiAoaGFuZzEgLSAxKQoKICAgICAgICB2ICs9IEsgKiAoYWR2MCAtIGFkdjEpICsgKHRocjAgLSB0aHIxKSAtIChkZzAgLSBkZzEpICsgKGh1bnQwIC0gaHVudDEpCgogICAgICAgIGhhc191c2VmdWxfZGVmID0gRmFsc2UKICAgICAgICBmb3IgaSBpbiByYW5nZShuYSk6CiAgICAgICAgICAgIGlmIEQxW0FfcFtpXV0gPD0gMiBhbmQgY0JbUFJFWVtBX3RbaV1dXSA+IDA6CiAgICAgICAgICAgICAgICBoYXNfdXNlZnVsX2RlZiA9IFRydWUKICAgICAgICAgICAgICAgIGJyZWFrCgogICAgICAgIG5lYXJfY250ID0gMAogICAgICAgIGZvciBqIGluIHJhbmdlKG5iKToKICAgICAgICAgICAgZCA9IEQxW0JfcFtqXV0KICAgICAgICAgICAgaWYgZCA8PSAyOgogICAgICAgICAgICAgICAgdiAtPSA1MjAgKiAoMyAtIGQpCiAgICAgICAgICAgICAgICBuZWFyX2NudCArPSAxCiAgICAgICAgICAgICAgICBpZiBpbnRiW2pdID09IDk5OgogICAgICAgICAgICAgICAgICAgIHYgLT0gNDUwICogKDMgLSBkKQogICAgICAgICAgICBlbGlmIGQgPT0gMzoKICAgICAgICAgICAgICAgIHYgLT0gMTEwCiAgICAgICAgICAgICAgICBpZiBpbnRiW2pdID09IDk5OgogICAgICAgICAgICAgICAgICAgIHYgLT0gMjIwCiAgICAgICAgICAgIGVsaWYgZCA9PSA0OgogICAgICAgICAgICAgICAgdiAtPSAzNQoKICAgICAgICBpZiBuZWFyX2NudCA+PSAyOgogICAgICAgICAgICB2IC09IDQyMCAqIChuZWFyX2NudCAtIDEpCiAgICAgICAgaWYgbmVhcl9jbnQgPj0gMSBhbmQgbm90IGhhc191c2VmdWxfZGVmOgogICAgICAgICAgICB2IC09IDQyMCAqIG5lYXJfY250CiAgICAgICAgaWYgaGFzX3VzZWZ1bF9kZWY6CiAgICAgICAgICAgIHYgKz0gMTM1ICsgMTA1ICogbmVhcl9jbnQKCiAgICAgICAgcmV0dXJuIHYgaWYgcyA9PSAwIGVsc2UgLXYKCiAgICBldmMgPSB7fQoKICAgIGRlZiBldmFsdWF0ZShzLCBoKToKICAgICAgICByID0gZXZjLmdldChoKQogICAgICAgIGlmIHIgaXMgTm9uZToKICAgICAgICAgICAgciA9IGV2YWx1YXRlX3JhdyhzKQogICAgICAgICAgICBldmNbaF0gPSByCiAgICAgICAgcmV0dXJuIHIKCiAgICBkZWYgcXNlYXJjaChzLCBhbHBoYSwgYmV0YSwgcGx5LCBxZCwgaCk6CiAgICAgICAgbm9kZXNbMF0gKz0gMQogICAgICAgIGlmIChub2Rlc1swXSAmIDYzKSA9PSAwIGFuZCAodGltZS5wcm9jZXNzX3RpbWUoKSA+IGRlYWRsaW5lIG9yIHRpbWUucHJvY2Vzc190aW1lKCkgLSBzdGFydF90aW1lID4gMC44NSk6CiAgICAgICAgICAgIGFib3J0WzBdID0gVHJ1ZQogICAgICAgIGlmIGFib3J0WzBdOgogICAgICAgICAgICByZXR1cm4gMAogICAgICAgIGlmIHdpbnNfbm93KHMpOgogICAgICAgICAgICByZXR1cm4gV0lOIC0gcGx5CiAgICAgICAgbyA9IDEgLSBzCiAgICAgICAgaW5fY2hrID0gd2luc19ub3cobykKICAgICAgICBpZiBpbl9jaGs6CiAgICAgICAgICAgIGlmIHFkID49IDQ6CiAgICAgICAgICAgICAgICByZXR1cm4gLVdJTiArIHBseSArIDEKICAgICAgICAgICAgYWxsX20gPSBnZW4ocywgMCkKICAgICAgICAgICAgZGVmX3NxID0gREVGX1NRW29dCiAgICAgICAgICAgIGV2YXNpb25zID0gW20gZm9yIG0gaW4gYWxsX20gaWYgbVszXSBpbiBkZWZfc3FdCiAgICAgICAgICAgIGlmIG5vdCBldmFzaW9uczoKICAgICAgICAgICAgICAgIHJldHVybiAtV0lOICsgcGx5ICsgMQogICAgICAgICAgICBldmFzaW9ucy5zb3J0KHJldmVyc2U9VHJ1ZSkKICAgICAgICAgICAgYmVzdCA9IC1XSU4gKyBwbHkgKyAxCiAgICAgICAgICAgIGZvciBtIGluIGV2YXNpb25zOgogICAgICAgICAgICAgICAgYyA9IG1bMV0KICAgICAgICAgICAgICAgIHAgPSBtWzJdCiAgICAgICAgICAgICAgICBxID0gbVszXQogICAgICAgICAgICAgICAgY2FwID0gbVs0XQogICAgICAgICAgICAgICAgYm9hcmRbcF0gPSAwCiAgICAgICAgICAgICAgICBib2FyZFtxXSA9IGMKICAgICAgICAgICAgICAgIHBzW2NdID0gcQogICAgICAgICAgICAgICAgaDIgPSBoIF4gWltjXVtwXSBeIFpbY11bcV0gXiBaUwogICAgICAgICAgICAgICAgaWYgY2FwOgogICAgICAgICAgICAgICAgICAgIHBzW2NhcF0gPSAtMQogICAgICAgICAgICAgICAgICAgIGNudFtvXSAtPSAxCiAgICAgICAgICAgICAgICAgICAgaDIgXj0gWltjYXBdW3FdCiAgICAgICAgICAgICAgICBzdGlsbF93ID0gd2luc19ub3cobykKICAgICAgICAgICAgICAgIGlmIG5vdCBzdGlsbF93OgogICAgICAgICAgICAgICAgICAgIGlmIGNhcCBhbmQgY250W29dID09IDA6CiAgICAgICAgICAgICAgICAgICAgICAgIHZhbCA9IFdJTiAtIHBseQogICAgICAgICAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICAgICAgICAgIHZhbCA9IC1xc2VhcmNoKG8sIC1iZXRhLCAtYWxwaGEsIHBseSArIDEsIHFkICsgMSwgaDIpCiAgICAgICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgICAgIHZhbCA9IC1XSU4gKyBwbHkgKyAxCiAgICAgICAgICAgICAgICBpZiBjYXA6CiAgICAgICAgICAgICAgICAgICAgY250W29dICs9IDEKICAgICAgICAgICAgICAgICAgICBwc1tjYXBdID0gcQogICAgICAgICAgICAgICAgYm9hcmRbcV0gPSBjYXAKICAgICAgICAgICAgICAgIGJvYXJkW3BdID0gYwogICAgICAgICAgICAgICAgcHNbY10gPSBwCiAgICAgICAgICAgICAgICBpZiBhYm9ydFswXToKICAgICAgICAgICAgICAgICAgICByZXR1cm4gMAogICAgICAgICAgICAgICAgaWYgdmFsID4gYmVzdDoKICAgICAgICAgICAgICAgICAgICBiZXN0ID0gdmFsCiAgICAgICAgICAgICAgICAgICAgaWYgdmFsID4gYWxwaGE6CiAgICAgICAgICAgICAgICAgICAgICAgIGFscGhhID0gdmFsCiAgICAgICAgICAgICAgICAgICAgICAgIGlmIGFscGhhID49IGJldGE6CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBicmVhawogICAgICAgICAgICByZXR1cm4gYmVzdAoKICAgICAgICBzdGFuZCA9IGV2YWx1YXRlKHMsIGgpCiAgICAgICAgaWYgc3RhbmQgPj0gYmV0YToKICAgICAgICAgICAgcmV0dXJuIHN0YW5kCiAgICAgICAgaWYgc3RhbmQgPiBhbHBoYToKICAgICAgICAgICAgYWxwaGEgPSBzdGFuZAogICAgICAgIGlmIHFkID49IDY6CiAgICAgICAgICAgIHJldHVybiBzdGFuZAogICAgICAgIG1vdmVzID0gZ2VuKHMsIDIgaWYgcWQgPT0gMCBlbHNlIDEpCiAgICAgICAgaWYgbm90IG1vdmVzOgogICAgICAgICAgICByZXR1cm4gc3RhbmQKICAgICAgICBtb3Zlcy5zb3J0KHJldmVyc2U9VHJ1ZSkKICAgICAgICBmb3IgbSBpbiBtb3ZlczoKICAgICAgICAgICAgYyA9IG1bMV0KICAgICAgICAgICAgcCA9IG1bMl0KICAgICAgICAgICAgcSA9IG1bM10KICAgICAgICAgICAgY2FwID0gbVs0XQogICAgICAgICAgICBib2FyZFtwXSA9IDAKICAgICAgICAgICAgYm9hcmRbcV0gPSBjCiAgICAgICAgICAgIHBzW2NdID0gcQogICAgICAgICAgICBoMiA9IGggXiBaW2NdW3BdIF4gWltjXVtxXSBeIFpTCiAgICAgICAgICAgIGlmIGNhcDoKICAgICAgICAgICAgICAgIHBzW2NhcF0gPSAtMQogICAgICAgICAgICAgICAgY250W29dIC09IDEKICAgICAgICAgICAgICAgIGgyIF49IFpbY2FwXVtxXQogICAgICAgICAgICBpZiBjYXAgYW5kIGNudFtvXSA9PSAwOgogICAgICAgICAgICAgICAgdmFsID0gV0lOIC0gcGx5CiAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICB2YWwgPSAtcXNlYXJjaChvLCAtYmV0YSwgLWFscGhhLCBwbHkgKyAxLCBxZCArIDEsIGgyKQogICAgICAgICAgICBpZiBjYXA6CiAgICAgICAgICAgICAgICBjbnRbb10gKz0gMQogICAgICAgICAgICAgICAgcHNbY2FwXSA9IHEKICAgICAgICAgICAgYm9hcmRbcV0gPSBjYXAKICAgICAgICAgICAgYm9hcmRbcF0gPSBjCiAgICAgICAgICAgIHBzW2NdID0gcAogICAgICAgICAgICBpZiBhYm9ydFswXToKICAgICAgICAgICAgICAgIHJldHVybiAwCiAgICAgICAgICAgIGlmIHZhbCA+IHN0YW5kOgogICAgICAgICAgICAgICAgc3RhbmQgPSB2YWwKICAgICAgICAgICAgICAgIGlmIHZhbCA+IGFscGhhOgogICAgICAgICAgICAgICAgICAgIGFscGhhID0gdmFsCiAgICAgICAgICAgICAgICAgICAgaWYgYWxwaGEgPj0gYmV0YToKICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWsKICAgICAgICByZXR1cm4gc3RhbmQKCiAgICBkZWYgc2VhcmNoKHMsIGRlcHRoLCBhbHBoYSwgYmV0YSwgcGx5LCBoLCBwcD0wKToKICAgICAgICBub2Rlc1swXSArPSAxCiAgICAgICAgaWYgKG5vZGVzWzBdICYgNjMpID09IDAgYW5kICh0aW1lLnByb2Nlc3NfdGltZSgpID4gZGVhZGxpbmUgb3IgdGltZS5wcm9jZXNzX3RpbWUoKSAtIHN0YXJ0X3RpbWUgPiAwLjg1KToKICAgICAgICAgICAgYWJvcnRbMF0gPSBUcnVlCiAgICAgICAgaWYgYWJvcnRbMF06CiAgICAgICAgICAgIHJldHVybiAwCiAgICAgICAgaWYgd2luc19ub3cocyk6CiAgICAgICAgICAgIHJldHVybiBXSU4gLSBwbHkKICAgICAgICBvID0gMSAtIHMKICAgICAgICBpbl9jaGsgPSB3aW5zX25vdyhvKQogICAgICAgIGlmIGRlcHRoIDw9IDA6CiAgICAgICAgICAgIGlmIGluX2NoayBhbmQgcGx5IDwgUExZTElNOgogICAgICAgICAgICAgICAgZGVwdGggPSAxCiAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICByZXR1cm4gcXNlYXJjaChzLCBhbHBoYSwgYmV0YSwgcGx5LCAwLCBoKQogICAgICAgIGEwID0gYWxwaGEKICAgICAgICB0dG0gPSBOb25lCiAgICAgICAgaGsgPSAoaCBeIFBBU1NLKSBpZiBwcCBlbHNlIGgKICAgICAgICBlID0gdHQuZ2V0KGhrKQogICAgICAgIGlmIGUgaXMgbm90IE5vbmU6CiAgICAgICAgICAgIGVkLCBlZiwgZXYsIGVtID0gZQogICAgICAgICAgICBpZiBldiA+IFdJTiAtIDEwMDA6CiAgICAgICAgICAgICAgICBldiAtPSBwbHkKICAgICAgICAgICAgZWxpZiBldiA8IC1XSU4gKyAxMDAwOgogICAgICAgICAgICAgICAgZXYgKz0gcGx5CiAgICAgICAgICAgIHR0bSA9IGVtCiAgICAgICAgICAgIGlmIGVkID49IGRlcHRoOgogICAgICAgICAgICAgICAgaWYgZWYgPT0gMDoKICAgICAgICAgICAgICAgICAgICByZXR1cm4gZXYKICAgICAgICAgICAgICAgIGlmIGVmID09IDE6CiAgICAgICAgICAgICAgICAgICAgaWYgZXYgPj0gYmV0YToKICAgICAgICAgICAgICAgICAgICAgICAgcmV0dXJuIGV2CiAgICAgICAgICAgICAgICBlbGlmIGV2IDw9IGFscGhhOgogICAgICAgICAgICAgICAgICAgIHJldHVybiBldgogICAgICAgIG1vdmVzID0gZ2VuKHMsIDApCiAgICAgICAgaWYgbm90IG1vdmVzOgogICAgICAgICAgICByZXR1cm4gLVdJTiArIHBseSArIDEgaWYgaW5fY2hrIGVsc2UgZXZhbHVhdGUocywgaCkKICAgICAgICBpZiBpbl9jaGs6CiAgICAgICAgICAgIGRlZl9zcSA9IERFRl9TUVtvXQogICAgICAgICAgICBtb3ZlcyA9IFttIGZvciBtIGluIG1vdmVzIGlmIG1bM10gaW4gZGVmX3NxXQogICAgICAgICAgICBpZiBub3QgbW92ZXM6CiAgICAgICAgICAgICAgICByZXR1cm4gLVdJTiArIHBseSArIDEKCiAgICAgICAgbW92ZXMuc29ydChyZXZlcnNlPVRydWUpCiAgICAgICAga20gPSBLSUxMRVJbcGx5XSBpZiBwbHkgPCA2NCBlbHNlIE5vbmUKICAgICAgICBpZiBrbSBpcyBub3QgTm9uZSBvciB0dG0gaXMgbm90IE5vbmU6CiAgICAgICAgICAgIGZvciBpIGluIHJhbmdlKGxlbihtb3ZlcykpOgogICAgICAgICAgICAgICAgbSA9IG1vdmVzW2ldCiAgICAgICAgICAgICAgICBpZiB0dG0gaXMgbm90IE5vbmUgYW5kIG1bMV0gPT0gdHRtWzBdIGFuZCBtWzJdID09IHR0bVsxXSBhbmQgbVszXSA9PSB0dG1bMl06CiAgICAgICAgICAgICAgICAgICAgaWYgaToKICAgICAgICAgICAgICAgICAgICAgICAgbW92ZXMuaW5zZXJ0KDAsIG1vdmVzLnBvcChpKSkKICAgICAgICAgICAgICAgICAgICBicmVhawogICAgICAgICAgICBpZiBrbSBpcyBub3QgTm9uZToKICAgICAgICAgICAgICAgIGZvciBpIGluIHJhbmdlKDEsIGxlbihtb3ZlcykpOgogICAgICAgICAgICAgICAgICAgIG0gPSBtb3Zlc1tpXQogICAgICAgICAgICAgICAgICAgIGlmIG1bMV0gPT0ga21bMF0gYW5kIG1bMl0gPT0ga21bMV0gYW5kIG1bM10gPT0ga21bMl06CiAgICAgICAgICAgICAgICAgICAgICAgIG1vdmVzLmluc2VydCgxIGlmIHR0bSBpcyBub3QgTm9uZSBlbHNlIDAsIG1vdmVzLnBvcChpKSkKICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWsKCiAgICAgICAgYmVzdCA9IC1XSU4gKyBwbHkgKyAxIGlmIGluX2NoayBlbHNlIC1JTkYKICAgICAgICBibSA9IE5vbmUKICAgICAgICBpZHggPSAwCiAgICAgICAgbmJfc2V0ID0gREVGX1NRW3NdCiAgICAgICAgZm9yIG0gaW4gbW92ZXM6CiAgICAgICAgICAgIGMgPSBtWzFdCiAgICAgICAgICAgIHAgPSBtWzJdCiAgICAgICAgICAgIHEgPSBtWzNdCiAgICAgICAgICAgIGNhcCA9IG1bNF0KICAgICAgICAgICAgYm9hcmRbcF0gPSAwCiAgICAgICAgICAgIGJvYXJkW3FdID0gYwogICAgICAgICAgICBwc1tjXSA9IHEKICAgICAgICAgICAgaDIgPSBoIF4gWltjXVtwXSBeIFpbY11bcV0gXiBaUwogICAgICAgICAgICBpZiBjYXA6CiAgICAgICAgICAgICAgICBwc1tjYXBdID0gLTEKICAgICAgICAgICAgICAgIGNudFtvXSAtPSAxCiAgICAgICAgICAgICAgICBoMiBePSBaW2NhcF1bcV0KICAgICAgICAgICAgaWYgaW5fY2hrIGFuZCB3aW5zX25vdyhvKToKICAgICAgICAgICAgICAgIHZhbCA9IC1XSU4gKyBwbHkgKyAxCiAgICAgICAgICAgIGVsaWYgY2FwIGFuZCBjbnRbb10gPT0gMDoKICAgICAgICAgICAgICAgIHZhbCA9IFdJTiAtIHBseQogICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgaWYgaWR4ID09IDA6CiAgICAgICAgICAgICAgICAgICAgdmFsID0gLXNlYXJjaChvLCBkZXB0aCAtIDEsIC1iZXRhLCAtYWxwaGEsIHBseSArIDEsIGgyKQogICAgICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgICAgICByZWQgPSAxIGlmIChpZHggPj0gNCBhbmQgZGVwdGggPj0gMyBhbmQgbm90IGNhcCBhbmQgbm90IGluX2NoayBhbmQgcSBub3QgaW4gbmJfc2V0KSBlbHNlIDAKICAgICAgICAgICAgICAgICAgICBpZiBpZHggPj0gMTIgYW5kIGRlcHRoID49IDUgYW5kIHJlZDoKICAgICAgICAgICAgICAgICAgICAgICAgcmVkID0gMgogICAgICAgICAgICAgICAgICAgIHZhbCA9IC1zZWFyY2gobywgZGVwdGggLSAxIC0gcmVkLCAtYWxwaGEgLSAxLCAtYWxwaGEsIHBseSArIDEsIGgyKQogICAgICAgICAgICAgICAgICAgIGlmIHZhbCA+IGFscGhhIGFuZCBub3QgYWJvcnRbMF06CiAgICAgICAgICAgICAgICAgICAgICAgIHZhbCA9IC1zZWFyY2gobywgZGVwdGggLSAxLCAtYmV0YSwgLWFscGhhLCBwbHkgKyAxLCBoMikKICAgICAgICAgICAgaWYgY2FwOgogICAgICAgICAgICAgICAgY250W29dICs9IDEKICAgICAgICAgICAgICAgIHBzW2NhcF0gPSBxCiAgICAgICAgICAgIGJvYXJkW3FdID0gY2FwCiAgICAgICAgICAgIGJvYXJkW3BdID0gYwogICAgICAgICAgICBwc1tjXSA9IHAKICAgICAgICAgICAgaWYgYWJvcnRbMF06CiAgICAgICAgICAgICAgICByZXR1cm4gMAogICAgICAgICAgICBpZiB2YWwgPiBiZXN0OgogICAgICAgICAgICAgICAgYmVzdCA9IHZhbAogICAgICAgICAgICAgICAgYm0gPSAoYywgcCwgcSkKICAgICAgICAgICAgICAgIGlmIHZhbCA+IGFscGhhOgogICAgICAgICAgICAgICAgICAgIGFscGhhID0gdmFsCiAgICAgICAgICAgICAgICAgICAgaWYgYWxwaGEgPj0gYmV0YToKICAgICAgICAgICAgICAgICAgICAgICAgaWYgbm90IGNhcDoKICAgICAgICAgICAgICAgICAgICAgICAgICAgIEhJU1RbcCAqIFNJWkUgKyBxXSArPSBkZXB0aCAqIGRlcHRoCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZiBwbHkgPCA2NDoKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBLSUxMRVJbcGx5XSA9IGJtCiAgICAgICAgICAgICAgICAgICAgICAgIGJyZWFrCiAgICAgICAgICAgIGlkeCArPSAxCgogICAgICAgIGlmIFBBU1NfT04gYW5kIG5vdCBwcCBhbmQgbm90IGluX2NoayBhbmQgYWxwaGEgPCBiZXRhIGFuZCBwbHkgPCA0MDoKICAgICAgICAgICAgdmFsID0gLXNlYXJjaChvLCBkZXB0aCAtIDEsIC1iZXRhIC0gUEFTU19JTiwgLWFscGhhIC0gUEFTU19JTiwgcGx5ICsgMSwgaCBeIFpTLCAxKSAtIFBBU1NfSU4KICAgICAgICAgICAgaWYgYWJvcnRbMF06CiAgICAgICAgICAgICAgICByZXR1cm4gMAogICAgICAgICAgICBpZiB2YWwgPiBiZXN0OgogICAgICAgICAgICAgICAgYmVzdCA9IHZhbAogICAgICAgICAgICAgICAgYm0gPSBOb25lCiAgICAgICAgICAgICAgICBpZiB2YWwgPiBhbHBoYToKICAgICAgICAgICAgICAgICAgICBhbHBoYSA9IHZhbAoKICAgICAgICBzdiA9IGJlc3QKICAgICAgICBpZiBzdiA+IFdJTiAtIDEwMDA6CiAgICAgICAgICAgIHN2ICs9IHBseQogICAgICAgIGVsaWYgc3YgPCAtV0lOICsgMTAwMDoKICAgICAgICAgICAgc3YgLT0gcGx5CiAgICAgICAgaWYgYmVzdCA8PSBhMDoKICAgICAgICAgICAgZmwgPSAyCiAgICAgICAgZWxpZiBiZXN0ID49IGJldGE6CiAgICAgICAgICAgIGZsID0gMQogICAgICAgIGVsc2U6CiAgICAgICAgICAgIGZsID0gMAogICAgICAgIHR0W2hrXSA9IChkZXB0aCwgZmwsIHN2LCBibSkKICAgICAgICByZXR1cm4gYmVzdAoKICAgIGRlZiBkZWNpZGUoKToKICAgICAgICByb290ID0gZ2VuKDAsIDApCiAgICAgICAgaWYgbm90IHJvb3Q6CiAgICAgICAgICAgIHJldHVybiAoMCwgMCkKCiAgICAgICAgZ3NldDAgPSBHT0FMWzBdCiAgICAgICAgZm9yIG0gaW4gcm9vdDoKICAgICAgICAgICAgaWYgbVszXSBpbiBnc2V0MCBvciAobVs0XSBhbmQgY250WzFdID09IDEpOgogICAgICAgICAgICAgICAgcmV0dXJuIChtWzFdLCBESVJOW21bM10gLSBtWzJdXSkKCiAgICAgICAgaWYgd2luc19ub3coMSk6CiAgICAgICAgICAgIHNhZmUgPSBbXQogICAgICAgICAgICBmb3IgbSBpbiByb290OgogICAgICAgICAgICAgICAgYzAgPSBtWzFdCiAgICAgICAgICAgICAgICBwMCA9IG1bMl0KICAgICAgICAgICAgICAgIHEwID0gbVszXQogICAgICAgICAgICAgICAgY2FwMCA9IG1bNF0KICAgICAgICAgICAgICAgIGJvYXJkW3AwXSA9IDAKICAgICAgICAgICAgICAgIGJvYXJkW3EwXSA9IGMwCiAgICAgICAgICAgICAgICBwc1tjMF0gPSBxMAogICAgICAgICAgICAgICAgaWYgY2FwMDoKICAgICAgICAgICAgICAgICAgICBwc1tjYXAwXSA9IC0xCiAgICAgICAgICAgICAgICAgICAgY250WzFdIC09IDEKICAgICAgICAgICAgICAgIGlmIG5vdCB3aW5zX25vdygxKToKICAgICAgICAgICAgICAgICAgICBzYWZlLmFwcGVuZChtKQogICAgICAgICAgICAgICAgaWYgY2FwMDoKICAgICAgICAgICAgICAgICAgICBjbnRbMV0gKz0gMQogICAgICAgICAgICAgICAgICAgIHBzW2NhcDBdID0gcTAKICAgICAgICAgICAgICAgIGJvYXJkW3EwXSA9IGNhcDAKICAgICAgICAgICAgICAgIGJvYXJkW3AwXSA9IGMwCiAgICAgICAgICAgICAgICBwc1tjMF0gPSBwMAogICAgICAgICAgICBpZiBzYWZlOgogICAgICAgICAgICAgICAgcm9vdCA9IHNhZmUKCiAgICAgICAgaWYgbGVuKHJvb3QpID09IDE6CiAgICAgICAgICAgIHJldHVybiAocm9vdFswXVsxXSwgRElSTltyb290WzBdWzNdIC0gcm9vdFswXVsyXV0pCgogICAgICAgIGgwID0gMAogICAgICAgIGZvciBjIGluIHJhbmdlKDEsIDIwKToKICAgICAgICAgICAgaWYgcHNbY10gPj0gMDoKICAgICAgICAgICAgICAgIGgwIF49IFpbY11bcHNbY11dCgogICAgICAgIHNlZW4gPSBtZW1vLnNldGRlZmF1bHQoJ3NlZW4nLCB7fSkKICAgICAgICBjZmcgPSBtZW1vLnNldGRlZmF1bHQoJ2NmZycsIHt9KQogICAgICAgIHBlbl91bml0ID0gMTMwICsgMiAqIG1pbih0dXJuLCAyMDApCiAgICAgICAgY2ZnX3VuaXQgPSAoNDUgKyA0ICogc3RhZykgKiAoMC4yNSBpZiBiZWhpbmQgZWxzZSAxLjApCgogICAgICAgIG9yZGVyID0gW10KICAgICAgICBmb3IgbSBpbiByb290OgogICAgICAgICAgICBjID0gbVsxXQogICAgICAgICAgICBwID0gbVsyXQogICAgICAgICAgICBxID0gbVszXQogICAgICAgICAgICBjYXAgPSBtWzRdCiAgICAgICAgICAgIHQgPSB0cFtjXQogICAgICAgICAgICBwcmVkX3QgPSBQUkVEW3RdCiAgICAgICAgICAgIHByZXlfdCA9IFBSRVlbdF0KICAgICAgICAgICAgcm9sZSA9IHJvbGVzLmdldChjLCAnSFVOVEVSJykKICAgICAgICAgICAgdGIgPSBtWzBdICogMTAKICAgICAgICAgICAgaWYgY2FwOgogICAgICAgICAgICAgICAgdGIgKz0gNTAwMAoKICAgICAgICAgICAgbWluX3ByZWRfcCA9IDk5CiAgICAgICAgICAgIG1pbl9wcmVkX3EgPSA5OQogICAgICAgICAgICBtaW5fcHJleV9xID0gOTkKICAgICAgICAgICAgcm93X3AgPSBEVFtwXQogICAgICAgICAgICByb3dfcSA9IERUW3FdCiAgICAgICAgICAgIGZvciBlYyBpbiByYW5nZSgxMSwgMjApOgogICAgICAgICAgICAgICAgZXAgPSBwc1tlY10KICAgICAgICAgICAgICAgIGlmIGVwID49IDAgYW5kIGVjICE9IGNhcDoKICAgICAgICAgICAgICAgICAgICBldCA9IHRwW2VjXQogICAgICAgICAgICAgICAgICAgIGlmIGV0ID09IHByZWRfdDoKICAgICAgICAgICAgICAgICAgICAgICAgaWYgcm93X3BbZXBdIDwgbWluX3ByZWRfcDoKICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1pbl9wcmVkX3AgPSByb3dfcFtlcF0KICAgICAgICAgICAgICAgICAgICAgICAgaWYgcm93X3FbZXBdIDwgbWluX3ByZWRfcToKICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1pbl9wcmVkX3EgPSByb3dfcVtlcF0KICAgICAgICAgICAgICAgICAgICBlbGlmIGV0ID09IHByZXlfdDoKICAgICAgICAgICAgICAgICAgICAgICAgaWYgcm93X3FbZXBdIDwgbWluX3ByZXlfcToKICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1pbl9wcmV5X3EgPSByb3dfcVtlcF0KICAgICAgICAgICAgaWYgbWluX3ByZWRfcCA9PSAxIGFuZCBtaW5fcHJlZF9xID4gMToKICAgICAgICAgICAgICAgIHRiICs9IDM1MAogICAgICAgICAgICBpZiBtaW5fcHJlZF9xID09IDE6CiAgICAgICAgICAgICAgICB0YiAtPSA2MDAKICAgICAgICAgICAgaWYgcm9sZSA9PSAnUlVOTkVSJzoKICAgICAgICAgICAgICAgIHRiICs9IChEMFtwXSAtIEQwW3FdKSAqIDQ1ICsgKEFEVjBbcV0gLSBBRFYwW3BdKSAqIDIwCiAgICAgICAgICAgIGVsaWYgcm9sZSA9PSAnREVGRU5ERVInOgogICAgICAgICAgICAgICAgdGIgKz0gKEQxW3BdIC0gRDFbcV0pICogMzUKICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgIHRiICs9IG1heCgwLCAxOCAtIG1pbl9wcmV5X3EpICogMjUKICAgICAgICAgICAgb3JkZXIuYXBwZW5kKCh0YiwgbSkpCiAgICAgICAgb3JkZXIuc29ydChyZXZlcnNlPVRydWUpCiAgICAgICAgb3JkZXIgPSBbeFsxXSBmb3IgeCBpbiBvcmRlcl0KCiAgICAgICAgcGVucyA9IHt9CiAgICAgICAgZm9yIG0gaW4gb3JkZXI6CiAgICAgICAgICAgIGMgPSBtWzFdCiAgICAgICAgICAgIHAgPSBtWzJdCiAgICAgICAgICAgIHEgPSBtWzNdCiAgICAgICAgICAgIGNhcCA9IG1bNF0KICAgICAgICAgICAgYm9hcmRbcF0gPSAwCiAgICAgICAgICAgIGJvYXJkW3FdID0gYwogICAgICAgICAgICBwc1tjXSA9IHEKICAgICAgICAgICAgaWYgY2FwOgogICAgICAgICAgICAgICAgcHNbY2FwXSA9IC0xCiAgICAgICAgICAgIGtleSA9IHR1cGxlKHBzKQogICAgICAgICAgICBjayA9IHR1cGxlKHBzWzE6MTBdKQogICAgICAgICAgICBpZiBjYXA6CiAgICAgICAgICAgICAgICBwc1tjYXBdID0gcQogICAgICAgICAgICBib2FyZFtxXSA9IGNhcAogICAgICAgICAgICBib2FyZFtwXSA9IGMKICAgICAgICAgICAgcHNbY10gPSBwCiAgICAgICAgICAgIHBlbnNbKGMsIHAsIHEpXSA9IG1pbig3NTAsIGludChwZW5fdW5pdCAqIHNlZW4uZ2V0KGtleSwgMCkgKyBjZmdfdW5pdCAqIGNmZy5nZXQoY2ssIDApKSkKCiAgICAgICAgY2FuX3Bhc3MgPSAoCiAgICAgICAgICAgIFBBU1NfT04gYW5kIHR1cm4gPiAxIGFuZCBtZW1vLmdldCgncGMnLCAwKSA8IDIgYW5kICgxNTUuMCAtIHVzZWQpID4gMTUKICAgICAgICAgICAgYW5kIG5vdCB3aW5zX25vdygxKSBhbmQgbm90IHdpbnNfbm93KDApCiAgICAgICAgKQoKICAgICAgICBiZXN0X21vdmUgPSBvcmRlclswXQogICAgICAgIGZvciBkZXB0aCBpbiByYW5nZSgxLCA0Mik6CiAgICAgICAgICAgIGJlc3RfYWRqID0gLUlORgogICAgICAgICAgICBjdXJfYmVzdCA9IE5vbmUKICAgICAgICAgICAgZG9uZSA9IDAKICAgICAgICAgICAgdmFscyA9IFtdCiAgICAgICAgICAgIGZvciBtIGluIG9yZGVyOgogICAgICAgICAgICAgICAgaWYgdGltZS5wcm9jZXNzX3RpbWUoKSAtIHN0YXJ0X3RpbWUgPiAwLjg1OgogICAgICAgICAgICAgICAgICAgIGFib3J0WzBdID0gVHJ1ZQogICAgICAgICAgICAgICAgICAgIGJyZWFrCiAgICAgICAgICAgICAgICBjID0gbVsxXQogICAgICAgICAgICAgICAgcCA9IG1bMl0KICAgICAgICAgICAgICAgIHEgPSBtWzNdCiAgICAgICAgICAgICAgICBjYXAgPSBtWzRdCiAgICAgICAgICAgICAgICBwZW4gPSBwZW5zWyhjLCBwLCBxKV0KICAgICAgICAgICAgICAgIGFyYXcgPSBiZXN0X2FkaiArIHBlbiBpZiBiZXN0X2FkaiA+IC1JTkYgZWxzZSAtSU5GCiAgICAgICAgICAgICAgICBib2FyZFtwXSA9IDAKICAgICAgICAgICAgICAgIGJvYXJkW3FdID0gYwogICAgICAgICAgICAgICAgcHNbY10gPSBxCiAgICAgICAgICAgICAgICBoMiA9IGgwIF4gWltjXVtwXSBeIFpbY11bcV0gXiBaUwogICAgICAgICAgICAgICAgaWYgY2FwOgogICAgICAgICAgICAgICAgICAgIHBzW2NhcF0gPSAtMQogICAgICAgICAgICAgICAgICAgIGNudFsxXSAtPSAxCiAgICAgICAgICAgICAgICAgICAgaDIgXj0gWltjYXBdW3FdCiAgICAgICAgICAgICAgICB2YWwgPSAtc2VhcmNoKDEsIGRlcHRoIC0gMSwgLUlORiwgLWFyYXcgaWYgYXJhdyA+IC1JTkYgZWxzZSBJTkYsIDEsIGgyKQogICAgICAgICAgICAgICAgaWYgY2FwOgogICAgICAgICAgICAgICAgICAgIGNudFsxXSArPSAxCiAgICAgICAgICAgICAgICAgICAgcHNbY2FwXSA9IHEKICAgICAgICAgICAgICAgIGJvYXJkW3FdID0gY2FwCiAgICAgICAgICAgICAgICBib2FyZFtwXSA9IGMKICAgICAgICAgICAgICAgIHBzW2NdID0gcAogICAgICAgICAgICAgICAgaWYgYWJvcnRbMF06CiAgICAgICAgICAgICAgICAgICAgYnJlYWsKICAgICAgICAgICAgICAgIGRvbmUgKz0gMQogICAgICAgICAgICAgICAgYWRqID0gdmFsIC0gcGVuIGlmIHZhbCA8IFdJTiAtIDEwMDAgZWxzZSB2YWwKICAgICAgICAgICAgICAgIHZhbHMuYXBwZW5kKChhZGosIG0pKQogICAgICAgICAgICAgICAgaWYgYWRqID4gYmVzdF9hZGo6CiAgICAgICAgICAgICAgICAgICAgYmVzdF9hZGogPSBhZGoKICAgICAgICAgICAgICAgICAgICBjdXJfYmVzdCA9IG0KCiAgICAgICAgICAgIGlmIGNhbl9wYXNzIGFuZCBjdXJfYmVzdCBpcyBub3QgTm9uZSBhbmQgbm90IGFib3J0WzBdOgogICAgICAgICAgICAgICAgYXJhdyA9IGJlc3RfYWRqICsgUEFTU19ST09UIGlmIGJlc3RfYWRqID4gLUlORiBlbHNlIC1JTkYKICAgICAgICAgICAgICAgIHZhbCA9IC1zZWFyY2goMSwgZGVwdGggLSAxLCAtSU5GLCAtYXJhdyBpZiBhcmF3ID4gLUlORiBlbHNlIElORiwgMSwgaDAgXiBaUywgMSkKICAgICAgICAgICAgICAgIGlmIG5vdCBhYm9ydFswXToKICAgICAgICAgICAgICAgICAgICBhZGogPSB2YWwgLSBQQVNTX1JPT1QgaWYgdmFsIDwgV0lOIC0gMTAwMCBlbHNlIHZhbAogICAgICAgICAgICAgICAgICAgIHZhbHMuYXBwZW5kKChhZGosIFBBU1NNKSkKICAgICAgICAgICAgICAgICAgICBpZiBhZGogPiBiZXN0X2FkajoKICAgICAgICAgICAgICAgICAgICAgICAgYmVzdF9hZGogPSBhZGoKICAgICAgICAgICAgICAgICAgICAgICAgY3VyX2Jlc3QgPSBQQVNTTQoKICAgICAgICAgICAgaWYgY3VyX2Jlc3QgaXMgbm90IE5vbmUgYW5kIChub3QgYWJvcnRbMF0gb3IgZG9uZSA+PSAxKToKICAgICAgICAgICAgICAgIGJlc3RfbW92ZSA9IGN1cl9iZXN0CiAgICAgICAgICAgICAgICBpZiBub3QgYWJvcnRbMF06CiAgICAgICAgICAgICAgICAgICAgdmFscy5zb3J0KGtleT1sYW1iZGEgejogelswXSwgcmV2ZXJzZT1UcnVlKQogICAgICAgICAgICAgICAgICAgIG9yZGVyID0gW3RfaXRlbVsxXSBmb3IgdF9pdGVtIGluIHZhbHMgaWYgdF9pdGVtWzFdIGlzIG5vdCBQQVNTTV0KICAgICAgICAgICAgICAgIGVsaWYgY3VyX2Jlc3QgaXMgbm90IFBBU1NNOgogICAgICAgICAgICAgICAgICAgIG9yZGVyLnJlbW92ZShjdXJfYmVzdCkKICAgICAgICAgICAgICAgICAgICBvcmRlci5pbnNlcnQoMCwgY3VyX2Jlc3QpCiAgICAgICAgICAgIGlmIGFib3J0WzBdOgogICAgICAgICAgICAgICAgYnJlYWsKICAgICAgICAgICAgaWYgYmVzdF9hZGogPiBXSU4gLSAxMDAwIG9yIGJlc3RfYWRqIDwgLVdJTiArIDEwMDA6CiAgICAgICAgICAgICAgICBicmVhawogICAgICAgICAgICBpZiB0aW1lLnByb2Nlc3NfdGltZSgpID4gZGVhZGxpbmUgb3IgdGltZS5wcm9jZXNzX3RpbWUoKSAtIHN0YXJ0X3RpbWUgPiAwLjg1OgogICAgICAgICAgICAgICAgYnJlYWsKCiAgICAgICAgaWYgYmVzdF9tb3ZlIGlzIFBBU1NNOgogICAgICAgICAgICBtZW1vWydwYyddID0gbWVtby5nZXQoJ3BjJywgMCkgKyAxCiAgICAgICAgICAgIG1lbW9bJ3VzZWQnXSA9IHVzZWQgKyAodGltZS5wcm9jZXNzX3RpbWUoKSAtIHN0YXJ0X3RpbWUpCiAgICAgICAgICAgIHRpbWUuc2xlZXAoUEFTU19TTEVFUCkKICAgICAgICAgICAgcmV0dXJuICgwLCAwKQoKICAgICAgICBtZW1vWydwYyddID0gMAogICAgICAgIGMgPSBiZXN0X21vdmVbMV0KICAgICAgICBwID0gYmVzdF9tb3ZlWzJdCiAgICAgICAgcSA9IGJlc3RfbW92ZVszXQogICAgICAgIGNhcCA9IGJlc3RfbW92ZVs0XQogICAgICAgIGJvYXJkW3BdID0gMAogICAgICAgIGJvYXJkW3FdID0gYwogICAgICAgIHBzW2NdID0gcQogICAgICAgIGlmIGNhcDoKICAgICAgICAgICAgcHNbY2FwXSA9IC0xCiAgICAgICAga2V5ID0gdHVwbGUocHMpCiAgICAgICAgc2VlbltrZXldID0gc2Vlbi5nZXQoa2V5LCAwKSArIDEKICAgICAgICBjayA9IHR1cGxlKHBzWzE6MTBdKQogICAgICAgIGNmZ1tja10gPSBjZmcuZ2V0KGNrLCAwKSArIDEKICAgICAgICByZXR1cm4gKGMsIERJUk5bcSAtIHBdKQoKICAgIHRyeToKICAgICAgICByZXMgPSBkZWNpZGUoKQogICAgZXhjZXB0IEV4Y2VwdGlvbjoKICAgICAgICByZXMgPSAoMCwgMCkKICAgICAgICBiZXN0ayA9IC1JTkYKICAgICAgICBmb3IgcCBpbiBnYW1lU3RhdGUuYWxseToKICAgICAgICAgICAgZm9yIGQgaW4gcmFuZ2UoMSwgOSk6CiAgICAgICAgICAgICAgICBkeCwgZHkgPSAoKC0xLCAxKSwgKDAsIDEpLCAoMSwgMSksICgxLCAwKSwgKDEsIC0xKSwgKDAsIC0xKSwgKC0xLCAtMSksICgtMSwgMCkpW2QgLSAxXQogICAgICAgICAgICAgICAgbnggPSBwLnggKyBkeAogICAgICAgICAgICAgICAgbnkgPSBwLnkgKyBkeQogICAgICAgICAgICAgICAgaWYgbnggPCAxIG9yIG54ID4gVyBvciBueSA8IDEgb3IgbnkgPiBIIG9yIChueSAqIFNUUklERSArIG54KSBpbiBXQUxMX1NFVDoKICAgICAgICAgICAgICAgICAgICBjb250aW51ZQogICAgICAgICAgICAgICAgb2sgPSBUcnVlCiAgICAgICAgICAgICAgICBmb3IgYSBpbiBnYW1lU3RhdGUuYWxseToKICAgICAgICAgICAgICAgICAgICBpZiBhLnggPT0gbnggYW5kIGEueSA9PSBueToKICAgICAgICAgICAgICAgICAgICAgICAgb2sgPSBGYWxzZQogICAgICAgICAgICAgICAgZm9yIGUgaW4gZ2FtZVN0YXRlLm9wcG9uZW50OgogICAgICAgICAgICAgICAgICAgIGlmIGUueCA9PSBueCBhbmQgZS55ID09IG55OgogICAgICAgICAgICAgICAgICAgICAgICBpZiBub3QgKChwLlR5cGUgPT0gJ1InIGFuZCBlLlR5cGUgPT0gJ1MnKSBvciAocC5UeXBlID09ICdTJyBhbmQgZS5UeXBlID09ICdQJykgb3IgKHAuVHlwZSA9PSAnUCcgYW5kIGUuVHlwZSA9PSAnUicpKToKICAgICAgICAgICAgICAgICAgICAgICAgICAgIG9rID0gRmFsc2UKICAgICAgICAgICAgICAgIGlmIG9rIGFuZCBBRFYwW255ICogU1RSSURFICsgbnhdID4gYmVzdGs6CiAgICAgICAgICAgICAgICAgICAgYmVzdGsgPSBBRFYwW255ICogU1RSSURFICsgbnhdCiAgICAgICAgICAgICAgICAgICAgcmVzID0gKHAucGlkLCBkKQoKICAgIG1lbW9bJ3VzZWQnXSA9IHVzZWQgKyAodGltZS5wcm9jZXNzX3RpbWUoKSAtIHN0YXJ0X3RpbWUpCiAgICByZXR1cm4gcmVz