质数变革

题目描述

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

现给定一个包含 $n$ 个整数的数组 $a$，记为 $a_1, a_2, . . . , 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, . . . , a_n$，表示初始时数组 $a$ 中的元素。

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

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 ≤ n, q ≤ 2 × 10^3，1 ≤ op ≤ 2，1 ≤ k ≤ n，1 ≤ x, a_i ≤ 10^5$。 对于所有评测用例，$1 ≤ n, q ≤ 2 × 10^5，1 ≤ op ≤ 2，1 ≤ k ≤ n，1 ≤ x, a_i ≤10^6$。