3-philia, 3-phobia

2 secs 1024 MB
riano_'s icon riano_

配点:400400

問題文

milkcoffee君とriano君は、それぞれ NN 個の数をもらいました。(ただし、 NN33 の倍数です。) ここで、両者がもらった数の組 A1,A2,A3,...,ANA_1,A_2,A_3,...,A_N は同じです。

22 人はそれぞれ独立に、これらを 33 個ずつの数の組に分けることになりました。 milkcoffee君は 33 が好きなので、どの組の和も 33 で割り切れるように分けたいと思っています。 riano君は 33 が嫌いなので、どの組の和も 33 で割り切れないように分けたいと思っています。

22 人がそれぞれ目的を達成することが可能かどうかを判定してください。

制約

  • 3N3×1053 \leq N \leq 3\times 10^5
  • NN33 の倍数である
  • 1Ai1091\leq A_i \leq 10^9 (1iN)(1\leq i\leq N)
  • 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられます。

NN

A1A_1 A2A_2 ... ANA_N

出力

11 行目には、milkcoffee君が目的を達成できる場合 Yes を、そうでない場合 No を出力してください。

22 行目には、riano君について同様の出力をしてください。

サンプル

入力1
6
1 2 3 4 5 6
出力1
Yes
Yes

milkcoffee君は (1,2,3),(4,5,6)(1,2,3),(4,5,6) 、riano君は (1,2,4),(3,5,6)(1,2,4),(3,5,6) と分ければよいです。

入力2
9
3 1 4 1 5 9 2 6 5
出力2
Yes
Yes
入力3
6
12 28 2268 3776 10000000 1000000000
出力3
No
Yes

提出


Go (1.21)