#160Medium

Subarray sums

Time: 1 s · Memory: 256 MB

Prefix sums

Statement

You are given an array of $n$ integers and a number $x$ . Count the non-empty subarrays whose sum is exactly $x$ .

Input format

The first line contains $n$ and $x$ ( $1 \le n \le 2 \cdot 10^5$ , $|x| \le 10^9$ ). The second line contains $n$ integers ( $|a_i| \le 10^9$ ).

Output format

A single number — the number of subarrays.

Examples

Input

5 7
2 -1 3 5 -2

Output

Note

The sum of $[l, r]$ is $x$ $\iff$ $p_{l-1} = p_r - x$ . Going from left to right, for every $r$ add how many earlier prefixes equal $p_r - x$ , then count $p_r$ itself. A dictionary (map/dict) works, or sorted prefixes with binary search.

There are negative numbers, so two pointers do not work. Prefixes reach $2 \cdot 10^{14}$ , the answer $2 \cdot 10^{10}$ .

Source: CSES, problem 1661.

Subarray sums

Time: 1 s · Memory: 256 MB

Prefix sums

Statement

You are given an array of $n$ integers and a number $x$ . Count the non-empty subarrays whose sum is exactly $x$ .

Input format

The first line contains $n$ and $x$ ( $1 \le n \le 2 \cdot 10^5$ , $|x| \le 10^9$ ). The second line contains $n$ integers ( $|a_i| \le 10^9$ ).

Output format

A single number — the number of subarrays.

Examples

Input

5 7
2 -1 3 5 -2

Output

Note

There are negative numbers, so two pointers do not work. Prefixes reach $2 \cdot 10^{14}$ , the answer $2 \cdot 10^{10}$ .

Source: CSES, problem 1661.