问题 4913 --序列变换

4913: 序列变换

题目描述

  小W当前有一个正整数m和两个长度相等的序列:$a = [a_1, a_2, \ldots, a_n]$ 和 $b = [b_1, b_2, \ldots, b_n]$。
现在,我们可以选择一个非负整数 $x$ ,然后把所有的 $a_i$ 都加上 $x$ 以后再模 $m$(也就是我们把
要 $a_i$ 变成 $((a_i + x)mod\ m)$ 。接下来,我们可以重新排列 $a$ 序列,如果可以让 $a$ 序列变成 $b$ 序列,就是一次成功的变换。
这样的 $x$ 有很多,我们需要找出最小的 $x$ 。
例如,如果 $m = 3, a = [0, 0, 2, 1], b = [2, 0, 1, 1]$,那么我们可以选择 $x = 1$,这样 $a$ 序列就变成了 $[1, 1, 0, 2]$,重排以后就可以变成 $b$ 序列了。

输入

输入的第一行是两个正整数 $n$ 和 $m$ ,表示序列的长度和要模的数。
接下来一行有 $n$ 个非负整数,表示$a_1, a_2, \ldots, a_n$。
接下来一行有 $n$ 个非负整数,表示$b_1, b_2, \ldots, b_n$。

输出

输出最小的非负整数 $x$ ,使得 $a$ 序列能够成功变成 $a$ 序列。
数据保证一定存在这样的非负整数 $x$。

样例输入输出

输入#1 复制
4 3
0 0 2 1
2 0 1 1
输出#1 复制
1
输入#2 复制
3 2
0 0 0
1 1 1
输出#2 复制
1
输入#3 复制
5 10
0 0 0 1 2
2 1 0 0 0
输出#3 复制
0

提示

样例2说明 明显给a序列中每个数都加1就可以了。
样例3说明 只要加0就可以,因为其实只要直接重排就可以了。
【数据范围】
$70\%$的数据,$1  \leq  n  \leq  100, 1  \leq  m  \leq  100, 0  \leq  a_i, b_i < m$。
$100\%$的数据,$1  \leq  n  \leq  2000, 1  \leq  m  \leq  10^9, 0  \leq  a_i, b_i < m$。

序号 标题 作者 发表时间 费用 订购数 操作