{"raw_statement":[{"iden":"problem statement","content":"You are given sequences of non-negative integers $A=(A_1,A_2,\\dots ,A_N),B=(B_1,B_2,\\dots ,B_N)$ of length $N$ and a positive integer $M$.\nWhen the elements of $A$ can be rearranged freely, find the minimum possible value of $\\max_{1\\le i\\le N} ((A_i+B_i) \\bmod M)$.\n$T$ test cases are given, so find the answer for each."},{"iden":"constraints","content":"*   $1 \\le T \\le 10^5$\n*   $1 \\le N \\le 3 \\times 10^5$\n*   $1 \\le M \\le 10^9$\n*   $0 \\le A_i,B_i \\lt M$\n*   The sum of $N$ over all test cases is at most $3 \\times 10^5$.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$\\text{case}_1$\n$\\text{case}_2$\n$\\vdots$\n$\\text{case}_T$\n\nEach test case is given in the following format:\n\n$N$ $M$\n$A_1$ $A_2$ $\\ldots$ $A_N$\n$B_1$ $B_2$ $\\ldots$ $B_N$"},{"iden":"sample input 1","content":"3\n3 6\n3 1 4\n2 0 1\n1 1000000000\n999999999\n999999999\n10 201\n144 150 176 154 110 187 38 136 111 46\n96 109 73 63 85 1 156 7 13 171"},{"iden":"sample output 1","content":"3\n999999998\n111\n\nFor the first test case, if we rearrange $A$ to $4,3,1$, then $(A_i+B_i) \\bmod M$ becomes $0,3,2$ respectively, and the $\\max$ of these is $3$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}