from collections import deque

def aho_corasick(patterns: list[str], text: str) -> list[list]:
    trie = [{"next": {}, "fail": 0, "output": []}]

    # Construir el trie
    for idx, pattern in enumerate(patterns):
        node = 0
        for ch in pattern:
            if ch not in trie[node]["next"]:
                trie[node]["next"][ch] = len(trie)
                trie.append({"next": {}, "fail": 0, "output": []})
            node = trie[node]["next"][ch]
        trie[node]["output"].append((idx, pattern))

    # Construir enlaces de fallo
    q = deque()

    for nxt in trie[0]["next"].values():
        q.append(nxt)

    while q:
        v = q.popleft()

        for ch, nxt in trie[v]["next"].items():
            q.append(nxt)

            f = trie[v]["fail"]
            while f and ch not in trie[f]["next"]:
                f = trie[f]["fail"]

            if ch in trie[f]["next"]:
                trie[nxt]["fail"] = trie[f]["next"][ch]
            else:
                trie[nxt]["fail"] = 0

            trie[nxt]["output"].extend(trie[trie[nxt]["fail"]]["output"])

    # Buscar coincidencias
    result = []
    node = 0

    for i, ch in enumerate(text):
        while node and ch not in trie[node]["next"]:
            node = trie[node]["fail"]

        if ch in trie[node]["next"]:
            node = trie[node]["next"][ch]
        else:
            node = 0

        for idx, pattern in trie[node]["output"]:
            start = i - len(pattern) + 1
            result.append((start, len(pattern), idx, pattern))

    # Ordenar por posición, luego por longitud y luego por índice original
    result.sort(key=lambda x: (x[0], x[1], x[2]))

    return [[pattern, start] for start, _, _, pattern in result]