题目描述

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

解释 #1

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

执行第一个操作，将 $a_2$ 替换为从小到大第 $1$ 个大于它的质数，即 $a_2$ 变为 $5$。

将 $a_2$ 替换为从小到大第 $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≤x_i,a_i≤10^5$;

• 对于所有评测用例，$1≤n,q≤2*10^5$，$1≤op≤2$，$1≤k≤n$，$1≤x_i,a_i≤10^6$。