Blue's Prime Transformation

In number theory, a traditional prime is defined as a natural number greater than 1 with exactly two positive divisors. In a twist proposed by Xiao Lan, a number is considered prime if its absolute value has exactly two positive divisors. Under this new definition, the prime sequence becomes: \( \ldots, -7, -5, -3, -2, 2, 3, 5, 7, \ldots \).

You are given an array \(a\) of \(n\) integers: \(a_1, a_2, \ldots, a_n\) and \(q\) operations. Each operation is described by three integers: \(op\), \(k\) and \(x\). The operations are to be executed in order, modifying the array \(a\) sequentially. For each operation:

• If \(op = 1\): For every index \(i\) (1-indexed) satisfying \(i \bmod k = 0\), replace \(a_i\) with the \(x\)-th prime (in descending order) that is strictly less than \(a_i\).
• If \(op = 2\): For every index \(i\) satisfying \(i \bmod k = 0\), replace \(a_i\) with the \(x\)-th prime (in ascending order) that is strictly greater than \(a_i\).

After all operations, Xiao Lan applies a final adjustment: if an element is less than \(0\), it is replaced with \(0\); if an element is greater than \(1000000\), it is replaced with \(1\). Determine the final state of the array \(a\).

Note: A number \(p\) is considered prime by Xiao Lan's definition if \(|p| \ge 2\) and the number of positive divisors of \(|p|\) is exactly 2.

inputFormat

The first line contains two integers \(n\) and \(q\), representing the number of array elements and the number of operations.

The second line contains \(n\) space-separated integers representing the array \(a_1, a_2, \ldots, a_n\).

The following \(q\) lines each contain three integers \(op\), \(k\), and \(x\) describing an operation.

outputFormat

Output the final state of the array after all operations, with the elements separated by spaces.

sample

5 2
2 3 4 5 6
1 2 1
2 3 2

2 2 7 3 6