Migrated from Lutece 2867 Kanade Hates 3

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

有一天，Kanade 看 $3$ 十分不顺眼，可能是因为它是第二大的质数，也可能因为是第一个奇质数，总之她希望这一天不和 $3$ 有关。

她今天在做某道题的数据，这道题的数据中包含一个长度为 $n$ 的正整数数列 $a_i$。Kanade 不希望数列中出现任何 $3$ 的正整数倍，因此她决定如下操作，直到数列中不含任何 $3$ 的正整数倍：

1. 选择最左边第一个是 $3$ 的正整数倍的数；
2. 将它平均分成 $3$ 份，插回数列的原位置。

例如数列 $\{1,3,2\}$，最左边第一个是 $3$ 的正整数倍的数为 $3$，将它平均分为三份后变成 $\{1,1,1\}$，插回原数列后，数列变为 $\{1,1,1,1,2\}$。

经过这种操作后，数列变得很长很长。Kanade 想知道，最后的数列中第 $q_1,q_2,\ldots,q_m$ 项的值分别为多少。

Input

第一行两个整数 $n,m\ (1\le n,m\le 2\times 10^5)$，分别表示原数列的长度和询问个数。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n\ (1\le a_i\le 10^9)$，表示原数列。

第三行 $m$ 个整数 $q_1,q_2,\ldots,q_m\ (1\le q_i\le l)$，表示 Kanade 的询问，其中 $l$ 表示最后状态下数列的长度。保证询问的数列下标按从小到大的顺序给出，即对于 $1\le i<m$，都有 $q_i<q_{i+1}$。

Output

对于所有询问输出一行，第 $i$ 个数表示最后数列第 $q_i$ 项的值。两个数之间用一个空格隔开。

Samples

4 16
6 12 9 5
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

2 2 2 4 4 4 1 1 1 1 1 1 1 1 1 5

Note

最后的询问就是最后的全部数列。

Resources

The 20th UESTC Programming Contest Preliminary