由于 \(\forall i,a_i < m,b_i < m\)，所以可能的边权要么是 \(a_i+b_j\)，要么是 \(a_i+b_j-m\)，下文简称其为一类边和二类边。
暴力建图太浪费了，发现与一个 \(a_i\) 的连边是二类边的 \(b_j\) 的值单调不减。
所以我们可以把所有点拆成入点和出点，简单理解为入点代表 \(b\)，出点代表 \(a\)。入点按照 \(b\) 的值排序，每个排序后的入点 \(i\) 往它大的一个入点 \(i+1\) 连一条边权为 \(b_{i+1}-b_i\) 的边。这样我们只需要对于每个出点 \(a_i\)，在 \(b\) 上二分出最小的 \(b_j\) 使得 \(a_i+b_j \ge m\)，让 \(a_i\) 向 \(b_j\) 连一条权值为 \(a_i+b_j-m\) 的边，就相当于处理出了 \(a_i\) 对应的所有二类边。
一类边同样处理，建一个源点，连向排序后的 \(b_1\) 对应的入点，边权为 \(b_1\)，这样，只要每个出点 \(a_i\) 向这个源点连一条权值为 \(a_i\) 的边，就相当于处理出了这个出点对应的所有一类边。不难发现这样建图，一类边的处理是不会与二类边的处理相互干涉的。
最后每个入点向对应的出点连一条边权为 \(0\) 的边，跑最短路即可。
复杂度 \(O(n \log n)\)，因为新图上点数和边数都是 \(O(n)\) 的。
Code