## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Maximum Pairwise Modular Sum CodeChef Solution | CodeChef Problem Solution 2022

You are given an array $A$ containing $N$ integers, and a positive integer $M$. Find the maximum value of

${A}_{i}+{A}_{j}+\left(\left({A}_{i}-{A}_{j}\right)modM\right)$

across all pairs $1\le i,j\le N$.

Note that $xmodM$ refers to the smallest non-negative integer obtained as the remainder upon dividing $x$ by $M$. For example, $4mod3=1$ and $\left(-10\right)mod3=2$.

### Input Format

• The first line of input will contain a single integer $T$, the number of test cases. The description of test cases follows.
• Each test case consists of two lines of input.

• The first line of each test case contains two space-separated integers $N$ and $M$.
• The second line of each test case contains $N$ space-separated integers ${A}_{1},{A}_{2},\dots ,{A}_{N}$.

### Output Format

• For each test case, output on a new line the maximum value of ${A}_{i}+{A}_{j}+\left(\left({A}_{i}-{A}_{j}\right)modM\right)$.

### Constraints

• $1\le T\le 100$
• $2\le N\le 2\cdot {10}^{5}$
• $2\le M\le 5\cdot {10}^{8}$
• $0\le {A}_{i}\le 5\cdot {10}^{8}$
• The sum of $N$ across all test cases won't exceed $2\cdot {10}^{5}$.

• The sum of $N$ across all test cases won't exceed $1000$
• $2\le M\le 1000$