题目背景

本题原题题面中的 $op$ 表述出现矛盾，洛谷题面对此进行了修正。

本题目前暂无数据，请不要提交本题。

题目描述

质数一直以来都是数学领域中的一个重要概念。传统的数论定义质数为只有两个正因子的自然数。然而，在一次变革中，小蓝提出了一个新的质数定义：绝对值只有两个正因子的数均为质数。根据小蓝的定义，质数序列如下：$\ldots, -7, -5, -3, -2, 2, 3, 5, 7, \ldots$

现给定一个包含 $n$ 个整数的数组 $a$，记为 $a_1, a_2, \ldots, a_n$，以及 $q$ 个操作，每个操作由三个整数 $op, k$ 和 $x$ 组成。小蓝将按顺序执行这些操作，依次改变数组 $a$ 中的元素值。具体地，对于一个操作：

• 若 $op$ 等于 $1$，则对于数组 $a$ 中满足 $i \bmod k = 0$ 的元素 $a_i$，将其替换为从大到小第 $x$ 个小于它的质数。
• 若 $op$ 等于 $2$，则对于数组 $a$ 中满足 $i \bmod k = 0$ 的元素 $a_i$，将其替换为从小到大第 $x$ 个大于它的质数。

由于小蓝不喜欢负数，也不喜欢太大的数，所以如果在所有操作结束后某个元素的值小于 $0$，小蓝会将其替换为 $0$；如果某个元素的值大于 $1000000$，小蓝会将其替换为 $1$。

请问，在所有操作结束后，数组 $a$ 中的元素分别为多少。

输入格式

输入的第一行包含两个整数 $n$ 和 $q$，用一个空格分隔，表示数组 $a$ 的长度和操作的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示初始时数组 $a$ 中的元素。

接下来 $q$ 行，每行包含三个整数 $op$、$k$ 和 $x$，表示一个操作。

输出格式

输出一行，包含 $n$ 个整数，表示在所有操作结束后，数组 $a$ 中的元素值。

5 3
2 3 6 9 12
2 2 1
2 2 1
1 3 4

2 7 0 13 12

提示

样例说明

• 初始时，数组 $a$ 的元素为 $[2, 3, 6, 9, 12]$。
• 执行第一个操作，将 $a_2$ 替换为从小到大第 1 个大于它的质数，即 $a_2$ 变为 5。将 $a_4$ 替换为从小到大第 1 个大于它的质数，即 $a_4$ 变为 11。数组变为 $[2, 5, 6, 11, 12]$。
• 执行第二个操作，将 $a_2$ 替换为从小到大第 1 个大于它的质数，即 $a_2$ 变为 7。将 $a_4$ 替换为从小到大第 1 个大于它的质数，即 $a_4$ 变为 13。数组变为 $[2, 7, 6, 13, 12]$。
• 执行第三个操作，将 $a_3$ 替换为从大到小第 4 个小于它的质数，即 $a_3$ 变为 -2。数组变为 $[2, 7, -2, 13, 12]$。
• 操作结束后，将数组中所有小于 0 的元素变为 0，大于 1000000 的元素变为 1，因此最后的数组为 $[2, 7, 0, 13, 12]$。

评测用例规模与约定

• 对于 $30\%$ 的评测用例，$1 \leq n, q \leq 2 \times 10^3$，$1 \leq op \leq 2$，$1 \leq k \leq n$，$1 \leq x, a_i \leq 10^5$。
• 对于所有评测用例，$1 \leq n, q \leq 2 \times 10^5$，$1 \leq op \leq 2$，$1 \leq k \leq n$，$1 \leq x, a_i \leq 10^6$。