This task consists of 2 parts. Note that you do not need to complete part 1 in order to do part 2.

Adam always recall the past.

Adam arranged $N$ photos on a line. Some photos carries happy memories and some carries sad memories. For convenient, we describe the $i$-th photo with mood value $A_i$.

Part I (50 points)

Adam thinks a continues segment of photos has neutral mood if and only if the average of their mood values equals $K$.
Formally, $A_{l...r}$ has neutral mood if $1 \le l \le r \le N$ and $\frac{A_l+A_{l+1}+...+A_r}{r-l+1} = K$.
Find the number of segments that has neutral mood.

Part II (50 points)

Adam thinks a continues segment of photos has neutral mood if and only if the median of their mood values equals $K$.

The median of array $B_{1...M}$ is defined as the $(\lfloor \frac{M}{2} \rfloor+1)$-th smallest element.
For example, the median of the photos with values $[3,1,2,4]$ is $3$.

Formally, $A_{l...r}$ has neutral mood if $1 \le l \le r \le N$ and the $(\lfloor \frac{r-l+1}{2} \rfloor +1)$-th smallest mood value in the segment equals $K$.

Find the number of segments that has neutral mood.

Input

The first line consists of an integer $T$. If $T=1$, the test case is for part I. If $T=2$ it is for part II.
The second line consists of two integers $N$ and $K$.
The third line consists of $N$ integers representing $A_{1...N}$.

Output

Output the answer required on a single line.

Subtasks

For all cases,
$T=1$ or $T=2$
$1 \le N \le 10^6$
$-10^9 \le K,A_i \le 10^9$

Subtask 1 ($12$ pts): $T=1, N\le 1000$
Subtask 2 ($24$ pts): $T=1, K=0$
Subtask 3 ($14$ pts): $T=1$
Subtask 4 ($11$ pts): $T=2, N\le 100$
Subtask 5 ($22$ pts): $T=2, K=1, A_i$ is either $0$ or $1$.
Subtask 6 ($17$ pts): $T=2$