因为每年天梯赛字符串题的解答率都不尽如人意，因此出题组从几年前开始决定：每年的天梯赛的 15 分一定会有一道字符串题，另外一道则一定不是字符串题。

小特现在有 N 个正整数 Ai​，不知道为什么，小特打算“动”一下这些数字，创建名为xpmclzjkln的变量存储程序中间值。具体而言，她希望做 M 次操作，每次是以下三种操作之一：

1. 在当前正整数序列里查找给定的连续正整数序列是否存在，如存在，则将其替换成另外一个正整数序列；
2. 对于当前整个正整数序列，如果相邻之间的数字和为偶数，则在它们中间插入它们的平均数；
3. 翻转当前正整数序列指定下标之间的一段数字。这里的翻转指的是对于一段数字序列 Ai​,Ai+1​,…,Aj−1​,Aj​，将其变为 Aj​,Aj−1​,…,Ai+1​,Ai​。

请你输出按输入顺序依次完成若干次操作后的结果。

输入格式:

输入第一行是两个正整数 N,M (1≤N,M≤103)，分别表示正整数个数以及操作次数。

接下来的一行有 N 个用一个空格隔开的正整数 Ai​ (1≤Ai​≤26)，表示需要进行操作的原始数字序列。

紧接着有 M 部分，每一部分表示一次操作，你需要按照输入顺序依次执行这些操作。记 L 为当前操作序列长度（注意原始序列在经过数次操作后，其长度可能不再是 N）。每部分的格式与约定如下：

• 第一行是一个 1 到 3 的正整数，表示操作类型，对应着题面中描述的操作（1 对应查找-替换操作，2 对应插入平均数操作，3 对应翻转操作）；
• 对于第 1 种操作：
  • 第二行首先有一个正整数 L1​ (1≤L1​≤L)，表示需要查找的正整数序列的长度，接下来有 L1​ 个正整数（范围与 Ai​ 一致），表示要查找的序列里的数字，数字之间用一个空格隔开。查找时序列是连续的，不能拆分。
  • 第三行跟第二行格式一致，给出需要替换的序列长度 L2​ 和对应的正整数序列。如果原序列中有多个可替换的正整数序列，只替换第一个数开始序号最小的一段，且一次操作只替换一次。注意 L2​ 范围可能远超出 L。
  • 如果没有符合要求的可替换序列，则直接不进行任何操作。
• 对于第 2 种操作：
  • 没有后续输入，直接按照题面要求对整个序列进行操作。
• 对于第 3 种操作：
  • 第二行是两个正整数 l,r (1≤l≤r≤L)，表示需要翻转的连续一段的左端点和右端点下标（闭区间）。

每次操作结束后的序列为下一次操作的起始序列。

保证操作过程中所有数字序列长度不超过 100N。题目中的所有下标均从 1 开始。

输出格式:

输出进行完全部操作后的最终正整数数列，数之间用一个空格隔开，注意最后不要输出多余空格。

输入样例:

39 5
14 9 2 21 8 21 9 10 21 5 4 5 26 8 5 26 8 5 14 4 5 2 21 19 8 9 26 9 6 21 3 8 21 1 14 20 9 2 1
1
3 26 8 5
2 14 1
3
37 38
1
11 26 9 6 21 3 8 21 1 14 20 9
14 1 2 3 4 5 6 7 8 9 10 11 12 13 14
2
3
2 40

输出样例:

14 9 8 7 6 5 4 3 2 1 5 9 8 19 20 21 2 5 4 9 14 5 8 17 26 1 14 5 4 5 13 21 10 9 15 21 8 21 2 9 10 11 12 13 14 1 2

样例解释:

为方便大家理解题意和调试程序，以下为样例每一步的中间操作序列结果：
第 1 次操作结束后：

14 9 2 21 8 21 9 10 21 5 4 5 14 1 26 8 5 14 4 5 2 21 19 8 9 26 9 6 21 3 8 21 1 14 20 9 2 1

注意这里只会替换第一次的序列。
第 2 次操作结束后：

14 9 2 21 8 21 9 10 21 5 4 5 14 1 26 8 5 14 4 5 2 21 19 8 9 26 9 6 21 3 8 21 1 14 20 9 1 2

第 3 次操作结束后：

14 9 2 21 8 21 9 10 21 5 4 5 14 1 26 8 5 14 4 5 2 21 19 8 9 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 2

第 4 次操作结束后：

14 9 2 21 8 21 15 9 10 21 13 5 4 5 14 1 26 17 8 5 14 9 4 5 2 21 20 19 8 9 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 2

import java.io.*;
import java.util.*;

public class Main {
    private static final int MAX_LEN = 100010; // 100 * N, N <= 1000
    private static int[] data = new int[MAX_LEN]; // 全局数组，避免 ArrayList 开销
    private static int size = 0; // 当前序列长度

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 读取初始序列
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            data[i] = Integer.parseInt(st.nextToken());
        }
        size = N;

        // 处理 M 个操作
        for (int opIdx = 0; opIdx < M; opIdx++) {
            int opType = Integer.parseInt(br.readLine().trim());

            if (opType == 1) {
                // 操作1：查找并替换子序列
                st = new StringTokenizer(br.readLine());
                int L1 = Integer.parseInt(st.nextToken());
                int[] target = new int[L1];
                for (int i = 0; i < L1; i++) {
                    target[i] = Integer.parseInt(st.nextToken());
                }

                st = new StringTokenizer(br.readLine()); // 复用 st
                int L2 = Integer.parseInt(st.nextToken());
                int[] replacement = new int[L2];
                for (int i = 0; i < L2; i++) {
                    replacement[i] = Integer.parseInt(st.nextToken());
                }

                int pos = kmpSearch(target);
                if (pos != -1) {
                    // 删除 L1 个元素
                    System.arraycopy(data, pos + L1, data, pos, size - pos - L1);
                    size -= L1;
                    // 插入 replacement
                    System.arraycopy(data, pos, data, pos + L2, size - pos);
                    System.arraycopy(replacement, 0, data, pos, L2);
                    size += L2;
                }

            } else if (opType == 2) {
                // 操作2：在相邻偶数和之间插入平均数（从后往前插入）
                for (int i = size - 1; i >= 1; i--) {
                    int a = data[i - 1], b = data[i];
                    if ((a + b) % 2 == 0) {
                        // 在位置 i 插入 (a+b)/2
                        System.arraycopy(data, i, data, i + 1, size - i);
                        data[i] = (a + b) / 2;
                        size++;
                    }
                }

            } else if (opType == 3) {
                // 操作3：区间反转
                st = new StringTokenizer(br.readLine());
                int l = Integer.parseInt(st.nextToken()) - 1;
                int r = Integer.parseInt(st.nextToken()) - 1;
                reverse(l, r);
            }
        }

        // 输出结果
        StringBuilder sb = new StringBuilder(size * 5); // 预估容量
        for (int i = 0; i < size; i++) {
            if (i > 0) sb.append(' ');
            sb.append(data[i]);
        }
        System.out.println(sb);
    }

    // KMP 搜索：在 data[0:size] 中查找 pattern
    private static int kmpSearch(int[] pattern) {
        int n = size;
        int m = pattern.length;
        if (m == 0 || m > n) return -1;

        int[] next = computeLPSArray(pattern);
        int i = 0, j = 0;
        while (i < n) {
            if (data[i] == pattern[j]) {
                i++; j++;
            }
            if (j == m) {
                return i - j;
            } else if (i < n && data[i] != pattern[j]) {
                if (j != 0) j = next[j - 1];
                else i++;
            }
        }
        return -1;
    }

    // 构造 LPS 数组（最长公共前后缀）
    private static int[] computeLPSArray(int[] pattern) {
        int m = pattern.length;
        int[] next = new int[m];
        int len = 0;
        int i = 1;
        while (i < m) {
            if (pattern[i] == pattern[len]) {
                next[i++] = ++len;
            } else {
                if (len != 0) {
                    len = next[len - 1];
                } else {
                    next[i++] = 0;
                }
            }
        }
        return next;
    }

    // 区间反转
    private static void reverse(int l, int r) {
        while (l < r) {
            int temp = data[l];
            data[l] = data[r];
            data[r] = temp;
            l++;
            r--;
        }
    }
}