Welcome to ZOJ
Select Problem
ZOJ Problem Set - 4101
Element Swapping

Time Limit: 1 Second      Memory Limit: 65536 KB

DreamGrid has an integer sequence $a_1, a_2, \dots, a_n$ and he likes it very much. Unfortunately, his naughty roommate BaoBao swapped two elements $a_i$ and $a_j$ ($1 \le i < j \le n$) in the sequence when DreamGrid wasn't at home. When DreamGrid comes back, he finds with dismay that his precious sequence has been changed into $a_1, a_2, \dots a_{i-1}, a_j, a_{i+1}, \dots, a_{j-1}, a_i, a_{j+1}, \dots, a_n$!

What's worse is that DreamGrid cannot remember his precious sequence. What he only remembers are the two values $$x = \sum_{k=1}^nka_k \qquad \text{and} \qquad y = \sum_{k=1}^nka_k^2$$ Given the sequence after swapping and the two values DreamGrid remembers, please help DreamGrid count the number of possible element pairs $(a_i, a_j)$ BaoBao swaps.

Note that as DreamGrid is poor at memorizing numbers, the value of $x$ or $y$ might not match the sequence, and no possible element pair can be found in this situation.

Two element pairs $(a_i, a_j)$ ($1 \le i < j \le n$) and $(a_p, a_q)$ ($1 \le p < q \le n$) are considered different if $i \ne p$ or $j \ne q$.


There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains three integers $n$, $x$ and $y$ ($2 \le n \le 10^5, 1 \le x, y \le 10^{18}$), indicating the length of the sequence and the two values DreamGrid remembers.

The second line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^5$), indicating the sequence after swapping. It's guaranteed that $\sum\limits_{k=1}^n kb_k \le 10^{18}$ and $\sum\limits_{k=1}^n kb_k^2 \le 10^{18}$.

It's guaranteed that the sum of $n$ of all test cases will not exceed $2 \times 10^6$.


For each test case output one line containing one integer, indicating the number of possible element pairs BaoBao swaps.

Sample Input

6 61 237
1 1 4 5 1 4
3 20190429 92409102
1 2 3

Sample Output



For the first sample test case, it’s possible that BaoBao swaps the 2nd and the 3rd element, or the 5th and the 6th element.

Author: WENG, Caizhi
Source: The 16th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple
Submit    Status