046 - I Love 46(★3) 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点: 3

問題文

3 つの長さ N の数列 A = (A_1, A_2, \cdots, A_N), B = (B_1, B_2, \cdots, B_N), C = (C_1, C_2, \cdots, C_N) が与えられます。

A_i + B_j + C_k46 の倍数となるような (i, j, k) (1 \leq i,j,k \leq N) の選び方の総数を出力してください。

制約

  • 1 \leq N \leq 10^5
  • 0 \leq A_i, B_j, C_k \leq 10^9
  • 入力は全て整数

入力

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

N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N
C_1 C_2 \cdots C_N

出力

答えを 1 行に出力してください。


入力例 1

3
10 13 93
5 27 35
55 28 52

出力例 1

3

A_i + B_j + C_k46 の倍数となる (i, j, k) の選び方は (1, 2, 1) (2, 1, 2) (2, 2, 3)3 つです。


入力例 2

3
10 56 102
16 62 108
20 66 112

出力例 2

27

どのような選び方をしても 3 つの整数の和が 46 の倍数になります。


入力例 3

20
238 395 46 238 264 114 354 52 324 14 472 64 307 280 209 24 165 194 179 248
270 83 377 332 173 21 362 75 66 342 229 117 124 481 48 235 376 13 420 74
175 427 76 278 486 169 311 47 348 225 41 482 355 356 263 95 170 156 340 289

出力例 3

183

出典

「競プロ典型90問」46日目