ストーリー

nauclhltくんはじゃんけんをした時の指の本数の総和が何通り存在するのか気になりました。

出せる手に対称性が無いものをじゃんけんと呼んで良いのかは分かりませんが、気にしません。

問題文

手にちょうど$F$本の指を持つ$N$人がじゃんけんをします。
じゃんけんをするとは、それぞれの人が3つの手のうち1つを独立に選んで出す行為をいいます。
$i(1\leq i\leq N)$番目の人は以下の3つの手から出す手を選ぶことができます。

• 手1: $A_i$本の指を立てる
• 手2: $B_i$本の指を立てる
• 手3: $C_i$本の指を立てる

整数$n(1\leq n\leq N)$に対して、$f(n)$を次のように定義します。

• 人$1, 2, \cdots, n$の$n$人でじゃんけんをしたときに、立っている指の本数の和としてあり得る非負整数の個数

例えば、$N=2, F=5, A=(0, 0), B=(2, 2), C=(5, 5)$のとき、$f(1)=3, f(2)=6$です。

$F, A, B, C$および正整数$N$が与えられるので、$k=1, 2, \cdots, N$に対して$f(k)$を求めてください。

入力

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

• $1\leq N\leq 1.5\times 10^4$
• $1\leq F\leq 60$
• $0\leq A_i, B_i, C_i\leq F$

出力

$N$行出力してください。$k(1\leq k\leq N)$行目には、$f(k)$の値を出力してください。
最後に改行してください。

サンプル

3 5
0 0 0
2 2 2
5 5 5

3
6
10