Story

nauclhlt became curious about how many different values the total number of fingers can take when playing rock-paper-scissors.

It is not clear whether a game whose available hands have no symmetry can be called rock-paper-scissors, but he does not care.

Problem Statement

$N$ people, each having exactly $F$ fingers on their hand, play rock-paper-scissors.
Playing rock-paper-scissors means that each person independently chooses one of three hands and shows it.
Person $i(1\leq i\leq N)$ can choose the hand to show from the following three hands.

• Hand 1: Raise $A_i$ fingers
• Hand 2: Raise $B_i$ fingers
• Hand 3: Raise $C_i$ fingers

For an integer $n(1\leq n\leq N)$, define $f(n)$ as follows.

• The number of non-negative integers that can be the sum of the numbers of raised fingers when the $n$ people, persons $1, 2, \cdots, n$, play rock-paper-scissors

For example, when $N=2, F=5, A=(0, 0), B=(2, 2), C=(5, 5)$, we have $f(1)=3, f(2)=6$.

Given $F, A, B, C$ and a positive integer $N$, find $f(k)$ for $k=1, 2, \cdots, N$.

Input

$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$

Output

Print $N$ lines. On the $k(1\leq k\leq N)$-th line, print the value of $f(k)$.
Print a newline at the end.

Sample

3 5
0 0 0
2 2 2
5 5 5

3
6
10