P10118 『STA - R4』And

Given non-negative integers $A, B$, define an ordered pair of non-negative integers $(x, y)$ to be good if and only if: - $0 \le x \le y$. - $x + y = A$. - $x \operatorname{AND} y = B$. Here, $\operatorname{AND}$ denotes the bitwise AND operation, which is represented by the `&` operator in C++. You need to compute the sum of $y - x$ over all good ordered pairs of non-negative integers $(x, y)$. Since this value may be very large, you only need to output the result modulo $M$. Formally, you need to compute $$\left(\sum\limits_{x \ge 0}\sum\limits_{y \ge 0}\left(y - x\right)\left[\operatorname{good}(x, y)\right]\right)\bmod M$$ where $\operatorname{good}(x, y)$ is true if and only if the ordered pair of non-negative integers $(x, y)$ is good.

**This problem contains multiple queries in a single test file.** The first line contains two integers $T, M$, representing the number of queries and the modulus. The next $T$ lines each contain two non-negative integers $A, B$, representing one query.

For each query, output one integer per line, representing the answer.

**[Sample #1 Explanation]** For the first query, the good pairs are $\left(1, 7\right)$ and $\left(3, 5\right)$, so the answer is $\left(7 - 1\right) + \left(5 - 3\right) = 8$. For the second query, the only good pair is $\left(4, 6\right)$, so the answer is $6 - 4 = 2$. For the third query, the good pairs are $\left(0, 6\right)$ and $\left(2, 4\right)$, so the answer is $\left(6 - 0\right) + \left(4 - 2\right) = 8$. **[Sample #2 Explanation]** All queries satisfy the constraints of Subtask 1, and the last two queries also satisfy the constraints of Subtask 3. In particular, under the constraints of the third query, there is no good ordered pair of non-negative integers, so the answer is $0$. **[Sample #3 Explanation]** All queries satisfy the constraints of Subtask 2. **[Sample #4 Explanation]** All queries satisfy the constraints of Subtask 4. In particular, under the constraints of the fourth and fifth queries, there is no good ordered pair of non-negative integers, so the answer is $0$. **[Constraints]** **This problem uses bundled testdata.** For $100\%$ of the testdata: - $1 \le T \le 3 \times 10^5$. - $0 \le A, B < 2^{60}$. - $5 \le M \le 1.1 \times 10^9$. - $M$ is a prime number. The detailed subtasks are as follows: |Subtask ID|Constraints|Score| |:--------:|:--------:|:--------:| |1|$T \le 200, 0 \le A, B \le 8 \times 10^5$|$15$| |2|For each query, the number of good pairs does not exceed $1000$|$25$| |3|$B = 0$|$25$| |4|No special constraints|$35$| Translated by ChatGPT 5