⚠いろいろ壊れているかもしれません\textcolor{#fe0}{⚠いろいろ壊れているかもしれません}

問題文

NN 個の非負整数 A1,A2,,ANA_1, A_2, \ldots, A_N からなる配列があります。

これに対する QQ 個のクエリを処理したあとの配列の内容を答えてください。

jj 番目のクエリは「配列を AimodBjA_i \bmod B_j の昇順で安定ソートせよ」という内容です。

制約

  • 1N2×1051 \le N \le 2\times 10^5
  • 1Q1041 \le Q \le 10^4
  • 0Ai1090 \le A_i \le 10^9
  • 1Bj1091 \le B_j \le 10^9
  • 入力はすべて整数である

入力

N QA1 A2  ANB1 B2  BMN\ Q\\ A_1\ A_2\ \cdots\ A_N\\ B_1\ B_2\ \cdots\ B_M

出力

配列の内容を、 11 行にスペース区切りで出力せよ。

入出力例

入力例1
5 3
1 2 3 4 5
3 2 4
出力例1
4 1 5 2 3

配列は [1,2,3,4,5][3,1,4,2,5][4,2,3,1,5][4,1,5,2,3][1, 2, 3, 4, 5] \to [3, 1, 4, 2, 5] \to [4, 2, 3, 1, 5] \to [4, 1, 5, 2, 3] とソートされます。

Submit


Go (1.21)