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

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

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

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

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

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

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

第二行包含 n 个整数 a1, a2, . . . , an，表示初始时数组 a 中的元素。

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

【样例说明】

初始时，数组 a 的元素为 [2, 3, 6, 9, 12]。

执行第一个操作，将 a2 替换为从小到大第 1 个大于它的质数，即 a2 变为 5。将 a4 替换为从小到大第 1 个大于它的质数，即 a4 变为 11。数组变为[2, 5, 6, 11, 12]。

执行第二个操作，将 a2 替换为从小到大第 1 个大于它的质数，即 a2 变为 7。将 a4 替换为从小到大第 1 个大于它的质数，即 a4 变为 13。数组变为[2, 7, 6, 13, 12]。

执行第三个操作，将 a3 替换为从大到小第 4 个小于它的质数，即 a3 变为−2。数组变为 [2, 7, −2, 13, 12]。

操作结束后，将数组中所有小于 0 的元素变为 0，大于 1000000 的元素变为 1，因此最后的数组为 [2, 7, 0, 13, 12]。

【评测用例规模与约定】

对于 30% 的评测用例，1 ≤ n, q ≤ 2 × 10³，1 ≤ op ≤ 2，1 ≤ k ≤ n，1 ≤ x, a_i ≤ 10⁵。对于所有评测用例，1 ≤ n, q ≤ 2 × 10⁵，1 ≤ op ≤ 2，1 ≤ k ≤ n，1 ≤ x, a_i ≤10⁶。