A. Ants on a Ring
time limit per test
3 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

There are $$$N$$$ ants on a circle. The circle has $$$L$$$ spot s numbered from $$$1$$$ to $$$L$$$ clockwise, with spot $$$L$$$ adjacent to spot $$$1$$$. Ants start at different spot s, and want to reach different spot s. To do so, in one second each ant may stay still or move around the circle to an adjacent spot (clockwise or counterclockwise).

No two ants can be at the same position on the circle at the same time, even between spot s. For instance, suppose that during a second an ant moves clockwise from spot $$$1$$$ to spot $$$2$$$. During that second, other ants cannot do any of the following:

  • Stay still at spot $$$2$$$ (ants would meet at spot $$$2$$$).
  • Move counterclockwise from spot $$$3$$$ to spot $$$2$$$ (ants would meet at spot $$$2$$$).
  • Move counterclockwise from spot $$$2$$$ to spot $$$1$$$ (ants would meet between spot s $$$1$$$ and $$$2$$$).

Determine whether it is possible for all ants to reach their targets, and if so, the minimum number of seconds required. That is, find the minimum $$$t$$$ such that after $$$t$$$ seconds, every ant can be at its target spot.

Input

The first line contains two integers $$$N$$$ ($$$1 \leq N \leq 1000$$$) and $$$L$$$ ($$$1 \leq L \leq 10^{9}$$$), indicating respectively the number of ants and the number of spot s.

The second line contains $$$N$$$ different integers $$${A_1}, {A_2}, \ldots, {A_N}$$$ ($$$1 \leq A_i \leq L$$$ for $$${i}={1}, {2}, \ldots, {N}$$$), where $$$A_i$$$ is the initial spot of the $$$i$$$-th ant.

The third line contains $$$N$$$ different integers $$${B_1}, {B_2}, \ldots, {B_N}$$$ ($$$1 \leq B_i \leq L$$$ for $$${i}={1}, {2}, \ldots, {N}$$$), such that $$$B_i$$$ is the target spot of the $$$i$$$-th ant.

Output

Output a single line with an integer indicating the minimum time required for all ants to reach their targets, or the character "*" (asterisk) if it is impossible.

Examples
Input
2 2
2 1
2 1
Output
0
Input
2 2
1 2
2 1
Output
1
Input
1 10
1
7
Output
4
Input
3 5
1 3 2
5 2 4
Output
*
Input
3 5
1 3 2
4 2 5
Output
2
Note

Explanation for example 1

The two ants start at their target spot s, so the answer is $$$0$$$.

Explanation for example 2

The two ants can move simultaneously either clockwise or counterclockwise, reaching their targets after just $$$1$$$ second.

Explanation for example 5

All three ants can move counterclockwise, with the second ant staying still for a second.