1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
#!/usr/bin/env python3
import sys
import math
import numpy as np

#––– FORMAT OPERACJI –––
# Operacja sumy: "1 x y"  (A_new = A_x ∪ A_y)
# Operacja przecięcia: "2 x y"  (A_new = A_x ∩ A_y)
# Operacja negacji: "3 x"  (A_new = A′_x, czyli dopełnienie A_x w [1,n])

# Globalna lista operacji oraz licznik następnego indeksu.
ops = []    # lista napisów (str) opisujących operacje
next_idx = None  # kolejne indeksy dla nowych zbiorów

def new_op(op_type, x, y=None):
    """
    Rejestruje nową operację i zwraca indeks nowo utworzonego zbioru.
    op_type: "1" dla sumy, "2" dla przecięcia, "3" dla negacji.
    x, y: indeksy operandów (dla negacji tylko x).
    """
    global next_idx, ops
    if op_type == "3":
        s = f"3 {x}"
    else:
        s = f"{op_type} {x} {y}"
    ops.append(s)
    cur = next_idx
    next_idx += 1
    return cur

def main():
    global next_idx, ops
    data = sys.stdin.read().strip().split()
    if not data: 
        return
    # Wczytujemy n oraz s (rozmiar docelowego zbioru B)
    n = int(data[0])
    s = int(data[1])
    B = list(map(int, data[2:2+s]))  # elementy B – rosnąco, 1 ≤ b₁ < b₂ < … < b_s ≤ n

    # Jeśli B jest pełnym zbiorem (czyli B = {1,2,…,n}) to A1 = [1,n] już jest uniwersum.
    if s == n:
        print(0)
        return

    # Indeksy początkowych zbiorów A1, A2, …, An to 1,2,…,n.
    # Następnie operacje będą produkowały zbiory o indeksach n+1, n+2, …
    next_idx = n + 1

    # Funkcja pomocnicza – dla danego v, chcemy "singleton" F(v) = A_v ∩ (complement (∪{ A_{k*v} for k=2..⌊n/v⌋ }))
    # Jeśli v > n/2, A_v = {v} już jest singleton.
    singleton = dict()  # dla każdego v ∈ B zapisujemy indeks zbioru zawierającego {v}
    
    for v in B:
        if v > n//2:
            # Dla v > n/2 mamy A_v = {v}
            singleton[v] = v
        else:
            # Obliczamy listę mnożników: M = [2*v, 3*v, ..., ⌊n/v⌋*v]
            maxk = n // v
            if maxk < 2:
                # w teorii nie wystąpi, bo v ≤ n//2 zapewnia maxk ≥ 2
                singleton[v] = v
            else:
                M = [k*v for k in range(2, maxk+1)]
                # Obliczamy U = ∪_{j in M} A_j.
                # Jeśli M ma tylko jeden element, U = A_{M[0]}, inaczej łączymy sumami.
                if len(M) == 1:
                    U = M[0]
                else:
                    # Rozpoczynamy od A_{M[0]}
                    U = M[0]
                    for j in M[1:]:
                        U = new_op("1", U, j)
                # U jest sumą A_{2*v} ∪ A_{3*v} ∪ … ∪ A_{maxk*v}.
                # Obliczamy dopełnienie U: C = A′_U.
                C = new_op("3", U)
                # F(v) = A_v ∩ C.
                Fv = new_op("2", v, C)
                singleton[v] = Fv

    # Teraz chcemy złożyć zbiór B jako sumę (union) wszystkich F(v) dla v ∈ B.
    # Zbieramy indeksy wszystkich pojedynczych zbiorów
    list_singletons = [singleton[v] for v in B]
    if len(list_singletons) == 0:
        S = new_op("3", 1)  # np. puste – ale s>=1 więc to nie powinno wystąpić
    elif len(list_singletons) == 1:
        S = list_singletons[0]
    else:
        # Łączymy sumą w sposób sekwencyjny (można też robić drzewo binarne, by zmniejszyć liczbę operacji,
        # ale tu wystarczy sekwencyjnie – łączymy po kolei)
        cur = list_singletons[0]
        for idx in list_singletons[1:]:
            cur = new_op("1", cur, idx)
        S = cur

    # S to indeks zbioru, który (przy poprawności konstrukcji) powinien być równy B.
    # Wypisujemy ciąg operacji – liczba operacji to len(ops).
    m_ops = len(ops)
    # Sprawdzamy limit – jeżeli operacji jest więcej niż 100000, wypisujemy (dla pewności) błąd.
    if m_ops > 100000:
        # Można zamiast tego wypisać dowolny poprawny ciąg – poniższy kod nie powinien się zdarzyć dla przykładowych testów.
        print("0")
        return
    out_lines = [str(m_ops)]
    out_lines.extend(ops)
    sys.stdout.write("\n".join(out_lines))

if __name__ == '__main__':
    main()