質(zhì)數(shù)一直以來都是數(shù)學(xué)領(lǐng)域中的一個重要概念。傳統(tǒng)的數(shù)論定義質(zhì)數(shù)為只有兩個正因子的自然數(shù)。然而，在一次變革中，小藍(lán)提出了一個新的質(zhì)數(shù)定義：絕對值只有兩個正因子的數(shù)均為質(zhì)數(shù)。根據(jù)小藍(lán)的定義，質(zhì)數(shù)序列如下：. . . , ?7, ?5, ?3, ?2, 2, 3, 5, 7, . . .

現(xiàn)給定一個包含 n 個整數(shù)的數(shù)組 a，記為 a1, a2, . . . , an，以及 q 個操作，每個操作由三個整數(shù) op、k 和 x 組成。小藍(lán)將按順序執(zhí)行這些操作，依次改變數(shù)組 a 中的元素值。具體地，對于一個操作：

- 若 op 等于 1，則對于數(shù)組 a 中滿足 i mod k = 0 的元素 ai，將其替換為從大到小第 x 個小于它的質(zhì)數(shù)。

- 若 op 等于 2，則對于數(shù)組 a 中滿足 i mod k = 0 的元素 ai，將其替換為從小到大第 x 個大于它的質(zhì)數(shù)。

由于小藍(lán)不喜歡負(fù)數(shù)，也不喜歡太大的數(shù)，所以如果在所有操作結(jié)束后某個元素的值小于 0，小藍(lán)會將其替換為 0；如果某個元素的值大于 1000000，小藍(lán)會將其替換為 1。

請問，在所有操作結(jié)束后，數(shù)組 a 中的元素分別為多少。

輸入的第一行包含兩個整數(shù) n 和 q ，用一個空格分隔，表示數(shù)組 a 的長度和操作的數(shù)量。

第二行包含 n 個整數(shù) a1, a2, . . . , an，表示初始時數(shù)組 a 中的元素。

接下來 q 行，每行包含三個整數(shù) op、k 和 x，表示一個操作。

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

2 7 0 13 12

【樣例說明】

初始時，數(shù)組 a 的元素為 [2, 3, 6, 9, 12]。

執(zhí)行第一個操作，將 a2 替換為從小到大第 1 個大于它的質(zhì)數(shù)，即 a2 變?yōu)?5。將 a4 替換為從小到大第 1 個大于它的質(zhì)數(shù)，即 a4 變?yōu)?11。數(shù)組變?yōu)閇2, 5, 6, 11, 12]。

執(zhí)行第二個操作，將 a2 替換為從小到大第 1 個大于它的質(zhì)數(shù)，即 a2 變?yōu)?7。將 a4 替換為從小到大第 1 個大于它的質(zhì)數(shù)，即 a4 變?yōu)?13。數(shù)組變?yōu)閇2, 7, 6, 13, 12]。

執(zhí)行第三個操作，將 a3 替換為從大到小第 4 個小于它的質(zhì)數(shù)，即 a3 變?yōu)?2。數(shù)組變?yōu)?[2, 7, ?2, 13, 12]。

操作結(jié)束后，將數(shù)組中所有小于 0 的元素變?yōu)?0，大于 1000000 的元素變?yōu)?1，因此最后的數(shù)組為 [2, 7, 0, 13, 12]。

【評測用例規(guī)模與約定】

對于 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⁶。