Problem Description

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.

Input Format

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.

Output Format

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

3 23
8 1
10 4
6 0

8
2
8

6 883
196483 132
330788 4353
137168 35030
615316 264202
387442 0
407154 0

579
432
0
27
807
845

3 30996377
948664793464517468 401148893358688606
945266152577109588 398323527798785832
185133025738933982 77893802910442339

29793121
28589865
30695563

5 992362009
248232552654965455 563160474979616
553521216364206023 14357560845404368
668113789984338832 146840018434951169
620025528908068087 506797735136774536
522926854352266209 860580850297773973

150959267
319548082
888288513
0
0

Hint

[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$
4	No special constraints	$35$

Translated by ChatGPT 5