iBLP

记号简介

无限基本Laver图案(Infinite Basic Laver Pattern)是由test_alpha0的记号Basic Laver Pattren改造而来。IBLP目前尚不理想，还存在许多的坏图案。test_alpha0规定其极限表达式为(1,0)1(2,1,0)1(3,2,1,0)2(4,3,2)1(5,4,3,2)2(6,5,4)1，因为现在认为在该图案下方不存在坏图案，而其上方不远处就出现了很多坏图案。尽管如此，IBLP仍然被认为是目前最强的记号。本页面介绍的规则对应NE上的DEN2。

定义

定义1 （IBLP）

一个IBLP是一个四元组 $A = (n, (A_{1}, \dots, A_{n}), (l_{1}, \dots, l_{n}), (M_{1}, \dots, M_{n}))$ ，

其中：

$(1) n \in ℕ$ 。

$(2)$ 对每个 $i \in {1, \dots, n}$ ， $A_{i}$ 是严格递增的非负整数序列，满足 $l e n (A_{i}) \geq 2 且 \max (A_{i}) = i$ 。

$(3)$ 对每个 $i \in {1, \dots, n}$ ，步长 $l_{i} \in ℕ$ 。

$(4)$ 对每个 $i \in {1, \dots, n}$ ，标记集合 $M_{i} \subseteq A_{i}$

约定所有编号从 1 开始； $A_{i} [k]$ 表示第 k 个元素， $A_{i} [- j] = A_{i} [l e n (A_{i}) - j + 1]$ 表示倒数第 j 个元素。

定义2 （长行、中等行、短行）

行 $i$ 称为长行若 $l e n (A_{i}) > 2 l_{i}$ ，称为中等行若 $l e n (A_{i}) = 2 l_{i}$ ，称为短行若 $l e n (A_{i}) < 2 l_{i}$ 。

定义3 （零图案、后继图案、极限图案）

若 n = 0，称 A 为零图案。若 $n > 0 且 l e n (A_{n}) = 2 且 \min (A_{n}) = 0$ ，称 A 为后继图案。否则称 A 为极限图案。

定义4 （行比较键）

令 $A_{i} = (A_{1} < a_{2} < \dots < a_{m}) 且 L = l_{i}$ 。定义保留序列

$K_{i} = {\begin{cases} (a_{1}, a_{2}, \dots, a_{m}), & L \leq 1; \\ (a_{1}, a_{L + 1}, a_{L + 2}, \dots, a_{m}), & 2 \leq L \leq m; \\ (a_{1}, a_{2}, \dots, a_{m}), & L \geq 2 且 m < L . \end{cases}$

定义行键为 $\overset{\leftarrow}{K_{i}}$ （即 $K_{i}$ 逆序，从大到小）。

定义5 （IBLP的大小比较）

给定两个 IBLP $A 、 B$ ，从 $i = 1$ 起逐行比较其

行键 $\overset{\leftarrow}{K_{i} (A)} 与 \overset{\leftarrow}{K_{i} (B)}$ 的字典序；第一处不同决定大小。若前 $\min (n_{a}, n_{b})$ 行都相等，则行数较小者更小。

定义6 （一行的根 $p (i)$ ）

对 $i \in {1, \dots, n}$ ，定义 $p (i) = A_{i} [- (l_{i} + 1)]$ .

定义7 （传递序列 $t r_{i} (j)$ ）

固定行 i。若 $j = A_{i} [k] (1 \leq k \leq l e n (A_{i})) 且 k \geq l_{i}$ ，定义阈值 $θ = A_{i} [k - l_{i}]$ 。令 $t_{0} = j$ ，并在 $t_{m} > θ 且 p (t_{m}) 有定义$ 时令 $t_{m + 1} = p (t_{m})$ 。若存在最小 $m > 0$ 使 $t_{m} = θ$ ，则定义 $t r_{i} (j) = (t_{0}, t_{1}, \dots, t_{m})$ ，否则称 $t r_{i} (j)$ 无定义。若 $k \leq l_{i}$ ，亦称无定义。

定义8 （部分函数 $f_{A}$ ）

设 A 非零且有至少1行。令 $a_{1} = A_{n} [1] = \min (A_{n}) ， L = l_{n} ， p = p (n) = A_{n} [- (L + 1)]$ 。定义部分函数 $f_{A} : ℕ ⇀ ℕ$ ：

$(1)$ 若 $x < a_{1}$ ，则 $f_{A} (x) = x$ ；

$(2)$ 若 $x = A_{n} [k] 且 x < p 且 k + L \leq l e n (A_{n})$ ，则 $f_{A} (x) = A_{n} [k + L]$ ；

$(3)$ 若 $x \geq p$ ，则 $f_{A} (x) = x + n - p$ ；

$(4)$ 其余情形 $f_{A} (x)$ 无定义。

定义9 （copy 的行与步长）

设 A 行数为 $n \geq 1$ ，令 $p = p (n)$ 。若 copy 过程中出现 $f_{A} (x)$ 无定义，则 $c o p y (A)$ 无定义。否则定义 $A^{'} = c o p y (A)$ 行数为 $n^{'} = 2 n - p$ ，满足：

$(1)$ 对 $1 \leq i \leq n - 1 ： {A_{i}}^{'} = A_{i} ， {l_{i}}^{'} = l_{i} ， {M_{i}}^{'} = M_{i}$ ；

$(2)$ 对每个 $i \in {1, \dots, n - p + 1}$ ，令源行 $σ = p + i - 1$ ，目标行 $τ = n - 1 + i$ i，定义 ${A_{τ}}^{'} = s o r t ({f_{A} (x) | x \in A_{σ}}) ， {l_{τ}}^{'} = l_{σ}$ ，要求 $\forall x \in A_{σ} ， f_{A} (x) 有定义$ 。

定义10 （copy的标记过滤）

延续上一定义。对目标行 $τ$ 中元素 $x \in {A_{τ}}^{'}$ ，令

$y \in A_{σ}$ 为其唯一来源（即 $f_{A} (y) = x$ ）。则 $x \in {M_{τ}}^{'}$ 当且仅当：

$y \in M_{σ}$ ，并且满足下列之一：

$t r_{σ} (y)$ 有定义且 $t r_{σ} (y) [- 2] \geq p$ ；
令 $y_{0}$ 为 $t r_{σ} (y)$ 中首次出现的 $< p$ 的元素（等价于“最大的

$< p$ 的元素”）。要么 $y_{0} < a_{1}$ ；要么存在 k 使 $y_{0} = A_{n} [k] 且 k + L \leq l e n (A_{n}) 且 A_{n} [k + L] \in M_{n}$ ，并且若 x 在 ${A_{τ}}^{'}$ 中的位置为 q（从 1 开始），则当 $q + 1 - l_{σ} \geq 1$ 时需满足 ${A_{τ}}^{'} [q + 1 - l_{σ}] \leq a_{1} .$

定义11 （E(A,0)）

若 A 非零且 n ≥ 1，则 E(A, 0) 为删除最后一行后的图案（行数变为 n − 1，其余行、步长、标记保持不变）。

定义12 （E(A, m)的copy阶段 (m≥1)）

设A是极限图案。令 $A^{(0)} = A$ 。若第一次 $c o p y (A^{(0)})$ 无定义，则称 A 为坏图案并定义 $E (A, m) = E (A, 0)$ 。否则定义

$A^{(1)} = c o p y (A^{(0)}), A^{(2)} = c o p y (A^{(1)}), \dots, A^{(m)} = c o p y (A^{(m - 1)})$ ,

并令 $B = E (A^{(m)}, 0)$

接下来对B做补全，初始行号 $r = n$ （这里 n 为原始 A 的行数）。补全过程允许使用临时记录映射 $R e c$ （行号 $\mapsto$ 有限序列），结束后丢弃。

定义13 （标记补全）

固定当前行 r。令 $ℬ = {b \in M_{r} | b \in A_{r}}$ 并按升序枚举其元素 $b_{1} < b_{2} < \dots < b_{k}$ （该集合在本轮开始时冻结，新产生标记不加入本轮）。对每个 $b_{i}$ 依次：

$(1)$ 若 $t r_{i} (b_{i})$ 无定义则跳过；

$(2)$ 令 $t = t r_{r} (b_{i}) [- 2]$ 。若 $R e c (t)$ 不存在或为空则跳过，否则记 $s = R e c (t)$ ；

$(3)$ 若对所有 $j = 3, 4, \dots, l e n (t r_{r} (b_{i}))$ 都有 $t r_{r} (b_{i}) [- j + 1] + 1 \in A_{t r_{r} (b_{i}) [- j]}$ ，那么把s 及 $b_{i} + 1, b_{i} + 2, \dots, b_{i} + l e n (s)$ 加入 $A_{r}$ ，并重新排序去重使

之严格递增。更新标记：s 中元素不标记， $b_{i} + 1, b_{i} + 2, \dots, b_{i} + l e n (s)$ 全标

记，其余标记保留（按上述规则修正）。更新步长： $l_{r} = l_{r} + l e n (s)$ 。

定义14 （原生补全）

固定当前行 r。若 $A_{r}$ 为长行，则原生补全不执行并返回 0。否则令 $p_{r} = p (r) = A_{r} [- (l_{r} + 1)] ， a = A_{r} [- l_{r}]$ .

构造序列 s：令 $u_{0} = a$ ，并在 $A_{u_{m}} [- 2]$ 存在且 $> p_{r}$ 时令 $u_{m + 1} = A_{u_{m}} [- 2]$ 并把 $u_{m + 1}$ 追加到 s，直至无法继续。令 $t = l e n (s)$ 。若 $t = 0$ 返回 0；若 $t > 0$ ，令 $R e c (r) = s$ 并继续：

$(1)$ 在 r 后插入 t 行，使原本行号 $> r$ 的行号整体加 t；

$(2)$ 仅对原本行号 $> r$ 的那些行，在其中把所有 $> r$ 的元素加 t，并同步

标记集合，步长不变；

$(3)$ 令旧行及旧步长为 $A_{r}^{o l d}, l_{r}^{o l d}$ 。将旧行替换为 t + 1 行：

$A_{r + t} = s o r t (A_{r}^{o l d} \cup s \cup {r + 1, r + 2, \dots, r + t}) ， l_{r + t} = l_{r}^{o l d} + t$ .

标记规则：除s和r+t外均标记。

$(4)$ 对 $i = t, t - 1, \dots, 1$ ，由 $A_{r + i}$ 构造 $A_{r + i - 1}$ ：删除元素 $r + i$ ，并删除元素 $A_{r + i} [- l_{r + i}]$ ，去除 $r + i - 1$ 的标记，并令 $l_{r + i - 1} = l_{r + i} - 1$ 。

$(5)$ 中等行例外：若 $i = t$ 且 $A_{r}^{o l d}$ 为中等行，则在构造 $A_{r + i - 1}$ 时不删除 $A_{r + i} [- l_{r + i}]$ 且不减步长（令 $l_{r + i - 1} = l_{r + i}$ ），但仍删除 $r + i$ 并去除 $r + i - 1$ 的标记。

原生补全返回t。

定义15 （补全主循环(用于 E(A, m))）

令初始 $r = n$ （n 为原始 A 的行数）。当 r 不超过当前 B 的行数时循环：先对行 r 执行标记补全，再执行原生补全得到 t，然后更新 $r = r + t + 1$ 。当 r 越界时补全结束，丢弃 $R e c$ ，所得 B 即为 $E (A, m)$ 。

展开器

iblp的展开器在NE上可以找到，同时也可以使用如下Python代码直观地看到每个图案的行为。

import bisect


def _clone_rows(rows):
    return [row[:] for row in rows]


def _clone_mask(mask):
    return [set(s) for s in mask]


def _find_index(sorted_row, val):
    i = bisect.bisect_left(sorted_row, val)
    if i < len(sorted_row) and sorted_row[i] == val:
        return i
    return None


def _shift_sorted_row_inplace(sorted_row, threshold, delta):
    if delta == 0:
        return
    i = bisect.bisect_left(sorted_row, threshold)
    for j in range(i, len(sorted_row)):
        sorted_row[j] += delta


def _shift_mark_set(mark_set, threshold, delta):
    if delta == 0 or not mark_set:
        return mark_set
    new = set()
    for x in mark_set:
        new.add(x + delta if x >= threshold else x)
    return new


class ModifyUnpleasant(Exception):
    pass


MSG_UNPLEASANT = (
    "Something unpleasant happened. Please contact the author (E-mail: qwerasdfyh@126.com) "
    "about the previous pattern so he can improve the rule design."
)


class BasicLaverPattern:
    def __init__(self, rows, mask=None):
        self.rows = _clone_rows(rows)
        if mask is None:
            self.mask = [set() for _ in self.rows]
        else:
            self.mask = _clone_mask(mask)
        if self.mask:
            self.mask[0] = set()
        self._normalize_rows_inplace()

    def _normalize_rows_inplace(self, start_row=1):
        for r in range(max(1, start_row), len(self.rows)):
            row = self.rows[r]
            if row and row[-1] == r + 1:
                row.pop()
                self.mask[r].discard(r + 1)

    def clone(self):
        return BasicLaverPattern(self.rows, self.mask)

    def is_zero(self):
        return len(self.rows) == 1 and len(self.rows[0]) == 0

    def is_successor(self):
        if self.is_zero():
            return False
        last = self.rows[-1]
        return len(last) == 2 and last[0] == 0

    def draw(self):
        if self.is_zero():
            return
        base_list = self.rows[0]
        other_lists = self.rows[1:]
        if not other_lists:
            return
        max_len = max((seq[-1] for seq in other_lists if seq), default=0) + 1
        result = []
        for i, seq in enumerate(other_lists, start=1):
            line = [' '] * max_len
            mset = self.mask[i]
            for num in seq:
                if 0 <= num < max_len:
                    line[num] = 'a' if num in mset else 'o'
            if i <= len(base_list) and seq:
                last_circle_index = seq[-1]
                result.append(''.join(line[:last_circle_index + 1]) + f" {base_list[i-1]}")
        for line in result:
            print(line)

    def to_string(self):
        if self.is_zero():
            return ""
        base_list = self.rows[0]
        out = []
        for i in range(1, len(self.rows)):
            seq = self.rows[i]
            mset = self.mask[i]
            parts = []
            for x in reversed(seq):
                parts.append(f"*{x}" if x in mset else str(x))
            step = base_list[i - 1] if i - 1 < len(base_list) else 0
            out.append("(" + ",".join(parts) + ")" + str(step))
        return "".join(out)

    def cut(self):
        if self.is_zero():
            return False
        if len(self.rows) <= 1:
            return False
        if len(self.rows[0]) == 0:
            self.rows = [[]]
            self.mask = [set()]
            return False
        self.rows[0].pop()
        self.rows.pop()
        self.mask.pop()
        if len(self.rows) == 1 and len(self.rows[0]) == 0:
            self.mask = [set()]
        self._normalize_rows_inplace()
        return True

    def _transmission_penultimate_and_terminal_checked(self, row_idx, n_value):
        rows = self.rows
        base = rows[0]
        if n_value <= 0 or n_value >= len(rows):
            return None
        row = rows[row_idx]
        l_m = base[row_idx - 1]
        k = _find_index(row, n_value)
        if k is None or k - l_m < 0:
            return None
        threshold = row[k - l_m]

        cur = n_value
        visited = {cur}
        while True:
            if cur <= 0 or cur >= len(rows):
                return None
            l_s = base[cur - 1]
            if len(rows[cur]) < l_s + 1:
                return None
            nxt = rows[cur][-l_s - 1]
            if nxt > threshold:
                if nxt + 1 != cur + 1:
                    if _find_index(rows[cur], nxt + 1) is None:
                        return None
            prev, cur = cur, nxt
            if cur <= threshold:
                return (prev, cur)
            if cur in visited:
                return None
            visited.add(cur)

    def _first_not_copied_in_transmission(self, orig_rows, orig_base, copied_set, row_idx, n_value):
        row = orig_rows[row_idx]
        l_m = orig_base[row_idx - 1]
        k = _find_index(row, n_value)
        if k is None or k - l_m < 0:
            raise RuntimeError("Unpleasant.")
        threshold = row[k - l_m]
        cur = n_value
        seq = [cur]
        visited = {cur}
        while True:
            l_s = orig_base[cur - 1]
            if len(orig_rows[cur]) < l_s + 1:
                raise RuntimeError("Unpleasant.")
            nxt = orig_rows[cur][-l_s - 1]
            seq.append(nxt)
            cur = nxt
            if cur <= threshold:
                break
            if cur in visited:
                raise RuntimeError("Unpleasant.")
            visited.add(cur)
        t = seq[-2]
        terminal = seq[-1]
        tprime = None
        for x in seq:
            if x not in copied_set:
                tprime = x
                break
        return tprime, t, terminal

    def _slice_right_block(self, row_idx, anchor, q):
        row = self.rows[row_idx]
        pos = _find_index(row, anchor)
        if pos is None:
            raise RuntimeError("Unpleasant.")
        block = row[pos + 1: pos + 1 + q]
        if len(block) != q:
            raise RuntimeError("Unpleasant.")
        return block

    def _mark_completion_for_row(self, r, meta, native_done):
        base = self.rows[0]
        row0 = self.rows[r]
        initial_marks = [x for x in row0 if x in self.mask[r]]
        before = set(row0)
        added_total = 0

        for n in initial_marks:
            if _find_index(self.rows[r], n) is None:
                continue
            if n <= 0 or n >= len(meta):
                continue
            info = meta[n]
            if not info or not info.get("native_generated", False):
                continue

            tn = self._transmission_penultimate_and_terminal_checked(r, n)
            if tn is None:
                continue
            t, n_terminal = tn
            q = native_done.get(t, 0)
            if q <= 0:
                continue

            target_row = t + q
            left_block = self._slice_right_block(target_row, n_terminal, q)
            right_block = list(range(n + 1, n + q + 1))

            new_vals = set(left_block) | set(right_block)
            truly_new = new_vals - before
            if truly_new:
                added_total += len(truly_new)
                before |= truly_new

            row_set = set(self.rows[r])
            row_set.update(new_vals)
            self.rows[r] = sorted(row_set)

            self.mask[r].difference_update(left_block)
            self.mask[r].update(right_block)

        if added_total > 0:
            base[r - 1] += (added_total // 2)

    def _shift_values_ge(self, start_row_idx, threshold, delta):
        for i in range(start_row_idx, len(self.rows)):
            _shift_sorted_row_inplace(self.rows[i], threshold, delta)
            self.mask[i] = _shift_mark_set(self.mask[i], threshold, delta)

    def _native_completion_step(self, m, meta):
        rows = self.rows
        base = rows[0]
        l = base[m - 1]
        e = len(rows[m])

        if e > 2 * l:
            return False, 0

        if l <= 0 or e < l:
            return False, 0

        s = [rows[m][-l]]
        while True:
            if s[-1] <= 0 or s[-1] >= len(rows):
                return False, 0
            if len(rows[s[-1]]) < 2:
                return False, 0
            s.append(rows[s[-1]][-2])
            if len(rows[m]) < l + 1:
                return False, 0
            if s[-1] <= rows[m][-l - 1]:
                break

        k = len(s) - 1
        if k == 1:
            return False, 0
        s.pop()
        q = k - 1
        if q <= 0:
            return False, 0

        marks_m_orig = set(self.mask[m])
        self._shift_values_ge(m, m + 1, q)

        if e == 2 * l:
            c = rows[m][:]
        else:
            c = rows[m][:l - 1] + rows[m][l:]

        ext = s[1:][::-1] + list(range(m + 1, m + q + 1))
        rows[m].extend(ext)
        rows[m].sort()
        base[m - 1] += q

        d = []
        for i in range(q):
            d_i = c + s[q - i:] + list(range(m + 1, m + i + 2))
            d.append(sorted(d_i))

        old_e = e + 1
        base[:] = base[:m - 1] + list(range(old_e - l, old_e - l + q)) + base[m - 1:]
        rows[:] = rows[:m] + d + rows[m:]
        self.mask[:] = self.mask[:m] + [set() for _ in range(q)] + self.mask[m:]

        meta_insert = [{"native_generated": True, "native_q": q} for _ in range(q)]
        meta[:] = meta[:m] + meta_insert + meta[m:]

        marks_to_propagate = {x + q if x >= m + 1 else x for x in marks_m_orig}
        for row_idx in range(m, m + q + 1):
            self.mask[row_idx].update(marks_to_propagate)
        for j in range(1, q + 1):
            self.mask[m + j].update(range(m, m + j))

        self.mask[m + q].discard(m + 1 + q)
        self._normalize_rows_inplace(start_row=m)
        return True, q

    def modify(self, copy_only=False, silent=False):
        try:
            orig_rows = _clone_rows(self.rows)
            orig_mask = _clone_mask(self.mask)
            orig_base = orig_rows[0][:]
            orig_last_mask = set(orig_mask[-1]) if orig_mask else set()

            rows = self.rows
            base0 = rows[0]
            n_before_cut = len(base0)
            l_last = base0[n_before_cut - 1]
            b = rows[-1][:]
            b0 = b[0]
            p_leftmost = b[0]

            self.cut()
            rows = self.rows
            base0 = rows[0]

            u = b[-l_last - 1]
            v_copy = n_before_cut
            base0.extend(orig_base[u - 1: v_copy])

            b_map = {}
            limit = len(b) - l_last
            for i in range(limit):
                key = b[i]
                if key not in b_map:
                    b_map[key] = b[i + l_last]

            def map_elem(x):
                if x < b0:
                    return x
                if x > u:
                    return x - u + n_before_cut
                return b_map.get(x, -1)

            copied_set = set(range(u, v_copy + 1))

            for row_idx in range(u, v_copy + 1):
                src_row = orig_rows[row_idx]
                new_seq = []
                for elem in src_row:
                    new_val = map_elem(elem)
                    if new_val == -1:
                        if not silent:
                            print(MSG_UNPLEASANT)
                        raise ModifyUnpleasant
                    new_seq.append(new_val)
                new_seq.sort()
                rows.append(new_seq)

                new_marks = set()
                src_marks = orig_mask[row_idx]
                if src_marks:
                    l_m = orig_base[row_idx - 1]
                    for marked_val in src_marks:
                        if _find_index(orig_rows[row_idx], marked_val) is None:
                            continue
                        tprime, t, _terminal = self._first_not_copied_in_transmission(
                            orig_rows, orig_base, copied_set, row_idx, marked_val
                        )
                        keep = False
                        if t in copied_set:
                            keep = True
                        else:
                            if tprime is not None and tprime < p_leftmost:
                                keep = True
                            elif tprime is not None:
                                u_img = b_map.get(tprime, None)
                                if u_img is not None and u_img in orig_last_mask:
                                    mv_img = map_elem(marked_val)
                                    if mv_img != -1:
                                        pos_u = _find_index(new_seq, mv_img)
                                        if pos_u is not None:
                                            idx_check = pos_u - l_m + 1
                                            if idx_check >= 0 and new_seq[idx_check] <= p_leftmost:
                                                keep = True
                        if keep:
                            new_marks.add(map_elem(marked_val))
                self.mask.append(new_marks)

            if copy_only:
                self._normalize_rows_inplace()
                return self.clone()

            meta = [None] * len(self.rows)
            native_done = {}

            m = n_before_cut
            while True:
                base0 = self.rows[0]
                if m > len(base0):
                    break
                self._mark_completion_for_row(m, meta, native_done)
                did, q = self._native_completion_step(m, meta)
                if did:
                    native_done[m] = q
                    m += q + 1
                else:
                    m += 1

            self._normalize_rows_inplace()
            return self.clone()

        except ModifyUnpleasant:
            raise
        except RuntimeError as e:
            if str(e) == "Unpleasant.":
                if not silent:
                    print(MSG_UNPLEASANT)
                raise ModifyUnpleasant
            raise


initial_rows = [
    [1, 1, 2, 2, 2],
    [0, 1],
    [0, 1, 2],
    [0, 1, 2, 3],
    [0, 1, 2, 3, 4],
    [2, 3, 4, 5]
]
initial_mask = [set() for _ in initial_rows]
initial_mask[4] = {3}


def _encode_expr(pat: BasicLaverPattern):
    base = pat.rows[0]
    expr = []
    for i in range(1, len(pat.rows)):
        L = base[i - 1] if (i - 1) < len(base) else 0
        vals_desc = list(reversed(pat.rows[i]))
        mset = pat.mask[i]
        row = [L] + [[v, (v in mset)] for v in vals_desc]
        expr.append(row)
    return expr


def _decode_expr(expr):
    base = [row[0] for row in expr]
    rows = [base]
    mask = [set()]
    for row in expr:
        vals = [x[0] for x in row[1:]]
        vals = sorted(set(vals))
        rows.append(vals)
        mask.append({x[0] for x in row[1:] if x[1]})
    return BasicLaverPattern(rows, mask)


def _deepcopy_expr(expr):
    return [[row[0]] + [[x[0], bool(x[1])] for x in row[1:]] for row in expr]


def _values(row):
    return [row[0]] + [x[0] for x in row[1:]]


def _cut_expr(expr):
    return _deepcopy_expr(expr[:-1])


def _pleasant_until(rows, t):
    tv = _values(t)
    L = t[0]
    tcheck = tv[1 + L:]
    if not tcheck:
        return -1

    tmax = tcheck[0]
    tmin = tcheck[-1]
    tset = set(tcheck)

    for n, s in enumerate(rows):
        scheck = _values(s)[1:]
        i1 = -1
        for idx, x in enumerate(scheck):
            if x < tmax:
                i1 = idx
                break
        i2 = -1
        for idx in range(len(scheck) - 1, -1, -1):
            if scheck[idx] > tmin:
                i2 = idx
                break

        if i1 != -1 and i2 != -1 and i1 <= i2:
            mid = scheck[i1:i2 + 1]
            if any(x not in tset for x in mid):
                return n
    return -1


def _seq_from(expr, i, j):
    row = expr[i]
    val = row[j][0]
    L = row[0]
    threshold = row[j + L][0] if (j + L) < len(row) else 0

    record = [[i + 1, j], [val]]
    while val > threshold:
        row = expr[val - 1]
        idx = 1 + row[0]
        record[-1].append(idx)
        val = row[idx][0] if idx < len(row) else 0
        record.append([val])

    record.pop()
    return record


def _apv(s_vals, t_vals):
    L = t_vals[0]
    t_last = t_vals[-1]
    t_1 = t_vals[1]
    t_1L = t_vals[1 + L] if (1 + L) < len(t_vals) else 0

    out = []
    for x in s_vals:
        if x < t_last:
            out.append(x)
        elif x >= t_1L:
            out.append(x - t_1L + t_1)
        else:
            k = -1
            for idx in range(len(t_vals) - 1, -1, -1):
                if t_vals[idx] == x:
                    k = idx
                    break
            out.append(None if k == -1 else t_vals[k - L])
    return out


def _ap(row_s, row_t):
    svals = _values(row_s)[1:]
    tvals = _values(row_t)
    mapped = _apv(svals, tvals)
    return [row_s[0]] + [[x, False] for x in mapped]


def _copy_block(raw, flag):
    active = raw[-1]
    expr = _cut_expr(raw)

    begin = active[1 + active[0]][0]
    end = (begin + flag) if (flag != -1) else (len(raw) + 1)
    offset = len(raw) - begin

    expr.extend([_ap(row, active) for row in raw[begin - 1:end - 1]])

    active_min = active[-1][0]
    begin_rowno = begin

    for i in range(begin - 1, end - 1):
        row = raw[i]
        target_row = expr[i + offset]
        for j in range(1, len(row)):
            if not row[j][1]:
                continue

            seq = _seq_from(raw, i, j)

            nomove = -1
            for k, item in enumerate(seq):
                if item[0] < begin_rowno:
                    nomove = k
                    break

            if nomove == -1:
                target_row[j][1] = True
                continue

            if seq[nomove][0] < active_min:
                target_row[j][1] = True
                continue

            c = seq[nomove - 1][0] + offset
            rowc = expr[c - 1]
            b = rowc[seq[nomove - 1][1]][0]

            idx_check = j + target_row[0] - 1
            left_ok = (idx_check < len(target_row)) and (target_row[idx_check][0] <= active_min)
            active_has_b_mark = any((x[0] == b and x[1]) for x in active[1:])

            if left_ok and active_has_b_mark:
                target_row[j][1] = True

    return expr


def _comp_to(raw, r, already):
    expr = _deepcopy_expr(raw)
    for j in range(len(raw[r]) - 1, 0, -1):
        if not raw[r][j][1]:
            continue
        n = raw[r][j][0]
        seq = _seq_from(raw, r, j)
        t = seq[-1][0]
        T = already[t - 1] if (t - 1) < len(already) else None
        if not T:
            continue
        q = len(T)
        entries = (
            [[x[0], bool(x[1])] for x in expr[r][1:]] +
            [[x, False] for x in T] +
            [[n + 1 + uu, True] for uu in range(q)]
        )
        entries.sort(key=lambda z: z[0], reverse=True)
        expr[r] = [expr[r][0] + q] + entries
    return expr


def _comp_from(raw, r, T):
    q = len(T)

    expr = [[row[0]] + [[x[0], bool(x[1])] for x in row[1:]] for row in raw[:r]]

    if len(raw[r]) < raw[r][0] * 2 + 1:
        lr = raw[r][0]
        cr = raw[r][1:-raw[r][0]] + raw[r][1 + raw[r][0]:]
    else:
        lr = raw[r][0] + 1
        cr = raw[r][1:]

    need_len = r + q + 1
    if len(expr) < need_len:
        expr.extend([None] * (need_len - len(expr)))

    for qq in range(q):
        entries = (
            [[x[0], bool(x[1])] for x in cr] +
            [[x, False] for x in T[:1 + qq]] +
            [[raw[r][1][0] + 1 + uu, False] for uu in range(qq)]
        )
        entries.sort(key=lambda z: z[0], reverse=True)
        expr[r + qq] = [lr + qq] + entries

    entries = (
        [[x[0], bool(x[1])] for x in raw[r][1:]] +
        [[x, False] for x in T] +
        [[raw[r][1][0] + 1 + uu, False] for uu in range(q)]
    )
    entries.sort(key=lambda z: z[0], reverse=True)
    expr[r + q] = [raw[r][0] + q] + entries

    for qq in range(1, q + 1):
        for uu in range(2, 1 + qq + 1):
            expr[r + qq][uu][1] = True

    threshold = raw[r][1][0]

    def m(entry, idx):
        if idx == 0:
            return entry
        vv = entry[0]
        if vv <= threshold:
            return [vv, bool(entry[1])]
        return [vv + q, bool(entry[1])]

    for row in raw[r + 1:]:
        new_row = []
        for idx, entry in enumerate(row):
            new_row.append(m(entry, idx))
        expr.append(new_row)

    return expr


def _expand_pleasant_only(raw, FSterm, longer=False):
    if FSterm < 0:
        FSterm = 0

    active = raw[-1]
    L = active[0]
    if (1 + L) >= len(active) or (active[1 + L][0] == 0):
        return _cut_expr(raw)

    begin = active[1 + L][0]
    flag = _pleasant_until(raw[begin - 1:-1], active)
    if flag != -1:
        raise ModifyUnpleasant

    expr = _deepcopy_expr(raw)
    for _ in range(FSterm):
        expr = _copy_block(expr, -1)

    expr = _copy_block(expr, 1) if longer else _cut_expr(expr)

    already = []
    r = len(raw) - 1
    while r < len(expr):
        expr = _comp_to(expr, r, already)

        if not (len(expr[r]) <= expr[r][0] * 2 + 1):
            r += 1
            continue

        idx0 = expr[r][expr[r][0]][0]
        T = [idx0]
        bound = expr[r][expr[r][0] + 1][0]

        while T[0] > bound:
            rr = T[0] - 1
            T.insert(0, expr[rr][2][0])

        T = T[1:-1]
        if len(T) < 1:
            r += 1
            continue

        expr = _comp_from(expr, r, T)

        while len(already) <= r:
            already.append(None)
        already[r] = T

        r += len(T) + 1

    return expr


def _expand_like_model(pattern: BasicLaverPattern, FSterm: int, longer: bool, silent: bool):
    if pattern.is_zero():
        return pattern.clone(), 0
    if pattern.is_successor():
        q = pattern.clone()
        q.cut()
        return q, 0

    base0 = pattern.rows[0]
    if not base0:
        q = pattern.clone()
        q.cut()
        return q, 0

    if FSterm <= 0:
        q = pattern.clone()
        q.cut()
        return q, 0

    try:
        raw = _encode_expr(pattern)
        res = _expand_pleasant_only(raw, FSterm=FSterm, longer=longer)
        p2 = _decode_expr(res)
        return p2.clone(), 1
    except ModifyUnpleasant:
        if not silent:
            print(MSG_UNPLEASANT)
        q = pattern.clone()
        q.cut()
        return q, 0


def _apply_special_one(pattern: BasicLaverPattern, silent=False):
    if pattern.is_zero():
        return pattern.clone(), 0
    if pattern.is_successor():
        p = pattern.clone()
        p.cut()
        return p, 0

    p = pattern.clone()
    try:
        orig_rows = _clone_rows(p.rows)
        orig_mask = _clone_mask(p.mask)
        orig_base = orig_rows[0][:]
        orig_last_mask = set(orig_mask[-1]) if orig_mask else set()

        rows = p.rows
        base0 = rows[0]
        n_before_cut = len(base0)
        if n_before_cut <= 0:
            p2 = p.clone()
            p2.cut()
            return p2, 0

        original_total_rows = len(rows)

        l_last = base0[n_before_cut - 1]
        b = rows[-1][:]
        if not b:
            p2 = p.clone()
            p2.cut()
            return p2, 0
        b0 = b[0]
        p_leftmost = b[0]

        p.cut()
        rows = p.rows
        base0 = rows[0]

        if l_last < 0 or len(b) < l_last + 1:
            if not silent:
                print(MSG_UNPLEASANT)
            raise ModifyUnpleasant
        u = b[-l_last - 1]

        if u - 1 < 0 or u - 1 >= len(orig_base):
            if not silent:
                print(MSG_UNPLEASANT)
            raise ModifyUnpleasant
        base0.append(orig_base[u - 1])

        b_map = {}
        limit = len(b) - l_last
        for i in range(limit):
            key = b[i]
            if key not in b_map:
                b_map[key] = b[i + l_last]

        def map_elem(x):
            if x < b0:
                return x
            if x > u:
                return x - u + n_before_cut
            return b_map.get(x, -1)

        copied_set = {u}

        if u <= 0 or u >= len(orig_rows):
            if not silent:
                print(MSG_UNPLEASANT)
            raise ModifyUnpleasant

        src_row = orig_rows[u]
        new_seq = []
        for elem in src_row:
            new_val = map_elem(elem)
            if new_val == -1:
                if not silent:
                    print(MSG_UNPLEASANT)
                raise ModifyUnpleasant
            new_seq.append(new_val)
        new_seq.sort()
        rows.append(new_seq)

        new_marks = set()
        src_marks = orig_mask[u]
        if src_marks:
            l_m = orig_base[u - 1]
            for marked_val in src_marks:
                if _find_index(orig_rows[u], marked_val) is None:
                    continue
                tprime, t, _terminal = p._first_not_copied_in_transmission(
                    orig_rows, orig_base, copied_set, u, marked_val
                )
                keep = False
                if t in copied_set:
                    keep = True
                else:
                    if tprime is not None and tprime < p_leftmost:
                        keep = True
                    elif tprime is not None:
                        u_img = b_map.get(tprime, None)
                        if u_img is not None and u_img in orig_last_mask:
                            mv_img = map_elem(marked_val)
                            if mv_img != -1:
                                pos_u = _find_index(new_seq, mv_img)
                                if pos_u is not None:
                                    idx_check = pos_u - l_m + 1
                                    if idx_check >= 0 and new_seq[idx_check] <= p_leftmost:
                                        keep = True
                if keep:
                    mv = map_elem(marked_val)
                    if mv != -1:
                        new_marks.add(mv)

        p.mask.append(new_marks)
        p._normalize_rows_inplace(start_row=len(p.rows) - 1)

        meta = [None] * len(p.rows)
        m = len(p.rows[0])
        did, q = p._native_completion_step(m, meta)

        if did and q > 0:
            for _ in range(q):
                p.cut()

        while len(p.rows) > original_total_rows:
            p.cut()

        p._normalize_rows_inplace()
        return p.clone(), 1

    except ModifyUnpleasant:
        q = pattern.clone()
        q.cut()
        return q, 0
    except RuntimeError as e:
        if str(e) == "Unpleasant.":
            if not silent:
                print(MSG_UNPLEASANT)
            q = pattern.clone()
            q.cut()
            return q, 0
        raise


def _apply_number(pattern, n, silent=False):
    if pattern.is_zero():
        return pattern.clone(), 0

    if n == 0:
        p = pattern.clone()
        p.cut()
        return p, 0

    if pattern.is_successor():
        p = pattern.clone()
        p.cut()
        return p, 0

    if n == 1:
        return _apply_special_one(pattern, silent=silent)

    FSterm = n - 1
    nxt, ok = _expand_like_model(pattern, FSterm=FSterm, longer=False, silent=silent)
    if ok == 0:
        return nxt, 0
    return nxt, n


def reconstruct_pattern_list(op_numbers, silent=False):
    pattern_list = [BasicLaverPattern(initial_rows, initial_mask)]
    executed = []
    for n in op_numbers:
        cur = pattern_list[-1]
        nxt, actual = _apply_number(cur, n, silent=silent)
        executed.append(actual)
        pattern_list.append(nxt)
    return executed, pattern_list, None


def _cmp_lists(a, b):
    la, lb = len(a), len(b)
    m = la if la < lb else lb
    for i in range(m):
        if a[i] < b[i]:
            return -1
        if a[i] > b[i]:
            return 1
    if la < lb:
        return -1
    if la > lb:
        return 1
    return 0


def _row_key_for_compare(pat, row_idx):
    base = pat.rows[0]
    row = pat.rows[row_idx]
    l = base[row_idx - 1] if row_idx - 1 < len(base) else 0
    if l <= 1:
        keep = row[:]
    else:
        if len(row) < l:
            keep = row[:]
        else:
            keep = [row[0]] + row[l:]
    keep = keep[::-1]
    return keep


def compare_patterns(a, b):
    ra = len(a.rows) - 1
    rb = len(b.rows) - 1
    m = ra if ra < rb else rb
    for i in range(1, m + 1):
        ka = _row_key_for_compare(a, i)
        kb = _row_key_for_compare(b, i)
        c = _cmp_lists(ka, kb)
        if c != 0:
            return c
    if ra < rb:
        return -1
    if ra > rb:
        return 1
    return 0


def _is_prefix(seg, full):
    if len(seg.rows) > len(full.rows):
        return False
    if seg.rows[0] != full.rows[0][:len(seg.rows[0])]:
        return False
    for i in range(1, len(seg.rows)):
        if seg.rows[i] != full.rows[i]:
            return False
    return True


def _is_proper_prefix(seg, full):
    return _is_prefix(seg, full) and (len(seg.rows) < len(full.rows))


def _pattern_equal(a: BasicLaverPattern, b: BasicLaverPattern):
    return a.rows == b.rows and a.mask == b.mask


def _pattern_signature(p: BasicLaverPattern):
    rows_sig = tuple(tuple(r) for r in p.rows)
    mask_sig = tuple(tuple(sorted(s)) for s in p.mask)
    return rows_sig, mask_sig


_EXPAND_COUNTS_CACHE = {}


def _expand_row_counts_from(start_pat: BasicLaverPattern, n: int):
    if n < 0:
        n = 0
    key = (_pattern_signature(start_pat), n)
    if key in _EXPAND_COUNTS_CACHE:
        return _EXPAND_COUNTS_CACHE[key][:]

    counts = [len(start_pat.rows)]
    for k in range(1, n + 1):
        res, _act = _apply_number(start_pat, k, silent=True)
        counts.append(len(res.rows))

    _EXPAND_COUNTS_CACHE[key] = counts[:]
    return counts


def _simplify(op_numbers, pattern_list):
    target = pattern_list[-1].clone()

    s = op_numbers[:]
    executed, pats, _ = reconstruct_pattern_list(s, silent=True)
    s = executed
    pattern_list = pats

    i = len(s) - 1
    while i >= 0:
        if i >= len(s):
            i = len(s) - 1
        if i < 0:
            break
        if s[i] == 0:
            i -= 1
            continue

        while True:
            if i >= len(s):
                break
            n = s[i]

            z = 0
            j = i + 1
            while j < len(s) and s[j] == 0:
                z += 1
                j += 1

            candidate = None
            need = None

            if n == 1:
                if z >= 1:
                    candidate = s[:i] + s[i + 1:]
                else:
                    break
            else:
                start_pat = pattern_list[i]
                counts = _expand_row_counts_from(start_pat, n)
                need = counts[n] - counts[n - 1]
                if need < 0:
                    need = 0

                if z < need:
                    break

                candidate = s[:]
                candidate[i] = n - 1
                if need > 0:
                    del candidate[i + 1: i + 1 + need]

            cand_exec, cand_pats, _ = reconstruct_pattern_list(candidate, silent=True)
            if not cand_pats or not _pattern_equal(cand_pats[-1], target):
                break

            s = cand_exec
            pattern_list = cand_pats

            if i >= len(s):
                break
            if s[i] == 0:
                break

        i = min(i, len(s) - 1)
        i -= 1
        while i >= 0 and s[i] == 0:
            i -= 1

    executed, pattern_list, _ = reconstruct_pattern_list(s, silent=True)
    return executed, pattern_list


def _seq_str(nums):
    return ",".join(str(x) for x in nums)


def _parse_o_string(s):
    s = s.strip()
    if s == "":
        return BasicLaverPattern([[]], [set()]), None

    pos = 0
    rows_desc = []
    steps = []
    n = len(s)

    while pos < n:
        if s[pos] != "(":
            return None, "error"
        pos += 1
        close = s.find(")", pos)
        if close == -1:
            return None, "error"
        inside = s[pos:close].strip()
        pos = close + 1

        nums = []
        if inside != "":
            parts = inside.split(",")
            for part in parts:
                part = part.strip()
                if part.startswith("*"):
                    part = part[1:].strip()
                if part == "" or (not part.isdigit()):
                    return None, "error"
                nums.append(int(part))

        nums_asc = sorted(nums)
        for i in range(1, len(nums_asc)):
            if nums_asc[i] == nums_asc[i - 1]:
                return None, "error"

        if pos >= n or (not s[pos].isdigit()):
            return None, "error"
        j = pos
        while j < n and s[j].isdigit():
            j += 1
        step = int(s[pos:j])
        pos = j

        rows_desc.append(nums_asc)
        steps.append(step)

    rows = [steps[:]] + rows_desc
    mask = [set()] + [set() for _ in rows_desc]
    return BasicLaverPattern(rows, mask), None


def _read_find_pattern(I):
    initial = BasicLaverPattern(initial_rows, initial_mask)
    C = initial.clone()

    ops = []
    pats = [C.clone()]

    if compare_patterns(C, I) <= 0:
        return C, ops, pats

    MAX_OUTER = 50000
    MAX_N = 20000
    outer = 0

    while outer < MAX_OUTER:
        outer += 1

        if compare_patterns(C, I) == 0:
            return C, ops, pats

        n = 0
        while n <= MAX_N:
            Cn, actual = _apply_number(C, n, silent=True)

            if _is_proper_prefix(Cn, I):
                n += 1
                continue

            if (compare_patterns(Cn, I) < 0) and (not _is_prefix(Cn, I)):
                return C, ops, pats

            if compare_patterns(Cn, I) >= 0:
                if Cn.rows == C.rows and Cn.mask == C.mask:
                    return C, ops, pats
                C = Cn
                ops.append(actual)
                pats.append(C.clone())
                break

            n += 1

        else:
            return C, ops, pats

    return C, ops, pats


def main_program():
    op_numbers = []
    executed, pattern_list, _ = reconstruct_pattern_list(op_numbers, silent=True)
    op_numbers = executed

    while True:
        cur = pattern_list[-1]
        print("\nCurrent pattern:")
        if cur.is_zero():
            print("(empty)")
        else:
            cur.draw()

        print(f"Operation sequence: {_seq_str(op_numbers)}")

        if cur.is_zero():
            pattern_type = "Zero"
        elif cur.is_successor():
            pattern_type = "Successor"
        else:
            pattern_type = "Limit"

        msg = f"This is a {pattern_type} pattern."
        msg += " Natural Number: Operation."
        msg += " O: Output."
        msg += " R: Read."
        if len(pattern_list) > 1:
            msg += " U: Undo."
        msg += " S: Simplify."
        msg += " I: Input operations."
        print(msg)

        user_input = input("Enter your operation: ").strip().upper()

        if user_input.isdigit():
            n_in = int(user_input)
            nxt, actual = _apply_number(cur, n_in, silent=False)
            pattern_list.append(nxt)
            op_numbers.append(actual)
            if actual == 0:
                print("Applied cut operation.")
            else:
                print(f"Applied operation {actual}.")
            continue

        if user_input == 'O':
            print(cur.to_string())
            continue

        if user_input == 'R':
            raw = input("Input pattern string (from O): ").strip()
            pat, err = _parse_o_string(raw)
            if err:
                print("error")
                continue
            found, ops, pats = _read_find_pattern(pat)
            op_numbers = ops
            pattern_list = pats
            print(found.to_string())
            continue

        if user_input == 'U' and len(pattern_list) > 1:
            op_numbers = op_numbers[:-1]
            executed, pattern_list, _ = reconstruct_pattern_list(op_numbers, silent=True)
            op_numbers = executed
            print("Undo the last operation.")
            continue

        if user_input == 'S':
            new_ops, new_patterns = _simplify(op_numbers, pattern_list)
            if new_ops != op_numbers:
                op_numbers = new_ops
                pattern_list = new_patterns
                print(f"Simplified operation sequence: {_seq_str(op_numbers)}")
            else:
                print("No further simplifications possible.")
            continue

        if user_input == 'I':
            raw = input("Input the operation sequence (comma-separated natural numbers, e.g., 3,0,2,1): ").strip()
            if raw == "":
                parsed = []
            else:
                parts = [p.strip() for p in raw.split(",")]
                if any(p == "" or (not p.isdigit()) for p in parts):
                    print("error")
                    continue
                parsed = [int(p) for p in parts]
            executed, pattern_list, _ = reconstruct_pattern_list(parsed, silent=True)
            op_numbers = executed
            continue

        print("Invalid operation. Please try again.")


if __name__ == "__main__":
    main_program()