B. Равенство по модулю
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано положительное целое число $$$m$$$ и две последовательности положительных целых чисел: $$$a=[a_1, a_2, \ldots, a_n]$$$ и $$$b=[b_1, b_2, \ldots, b_n]$$$. Обе последовательности имеют одинаковую длину $$$n$$$.

Напомним, что перестановкой называется последовательность из $$$n$$$ различных положительных чисел от $$$1$$$ до $$$n$$$. Например, следующие последовательности являются перестановками: $$$[1]$$$, $$$[1,2]$$$, $$$[2,1]$$$, $$$[6,7,3,4,1,2,5]$$$. Следующие последовательности перестановками не являются: $$$[0]$$$, $$$[1,1]$$$, $$$[2,3]$$$.

Вам нужно найти неотрицательное целое число $$$x$$$, увеличить все элементы $$$a_i$$$ на $$$x$$$, по модулю $$$m$$$ (другими словами, вы заменяете $$$a_i$$$ на $$$(a_i + x) \bmod m$$$), чтобы было возможно переставить элементы последовательности $$$a$$$, чтобы она стала равна $$$b$$$, среди таких нужно найти минимально возможное $$$x$$$.

Иначе говоря, вам необходимо найти наименьшее неотрицательное целое число $$$x$$$, для которого возможно найти какую-то перестановку $$$p=[p_1, p_2, \ldots, p_n]$$$, что для всех $$$1 \leq i \leq n$$$, $$$(a_i + x) \bmod m = b_{p_i}$$$, где $$$y \bmod m$$$ — остаток при делении $$$y$$$ на $$$m$$$.

Например, если $$$m=3$$$, $$$a = [0, 0, 2, 1], b = [2, 0, 1, 1]$$$, вы можете выбрать $$$x=1$$$, и $$$a$$$ будет равна $$$[1, 1, 0, 2]$$$, вы можете переставить элементы, чтобы получить $$$[2, 0, 1, 1]$$$, что равно последовательности $$$b$$$.

Входные данные

В первой строке записаны два целых числа $$$n,m$$$ ($$$1 \leq n \leq 2000, 1 \leq m \leq 10^9$$$): количество элементов в последовательности $$$m$$$.

Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i < m$$$).

В третьей строке записаны $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \leq b_i < m$$$).

Гарантируется, что можно найти неотрицательное целое число $$$x$$$, для которого возможно найти какую-то перестановку $$$p_1, p_2, \ldots, p_n$$$, что $$$(a_i + x) \bmod m = b_{p_i}$$$.

Выходные данные

Выведите наименьшее неотрицательное целое число $$$x$$$, для которого возможно найти какую-то перестановку $$$p_1, p_2, \ldots, p_n$$$, что $$$(a_i + x) \bmod m = b_{p_i}$$$ для всех $$$1 \leq i \leq n$$$.

Примеры
Входные данные
4 3
0 0 2 1
2 0 1 1
Выходные данные
1
Входные данные
3 2
0 0 0
1 1 1
Выходные данные
1
Входные данные
5 10
0 0 0 1 2
2 1 0 0 0
Выходные данные
0