该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

$. . . , −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$ mod $k = 0$ 的元素 $a_i$，将其替换为从大到小第 $x$ 个小于它的质数。
• 若 $op$ 等于 $2$，则对于数组 $a$ 中满足 $i$ mod $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$ 中的元素值。

样例输入输出

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 ≤ 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, ai ≤10^6$。