题目描述

There are $N$ ants on a circle. The circle has $L$ spots numbered from $1$ to $L$ clockwise, with spot $L$ adjacent to spot $1$. Ants start at different spots, and want to reach different spots. 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 spots. 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 spots $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.

输入格式

The first line contains two integers $N$ ($1 \le N \le 1000$) and $L$ ($1 \le L \le 10^9$), indicating respectively the number of ants and the number of spots.

The second line contains $N$ different integers $A_1, A_2, \ldots, A_N$ ($1 \le A_i \le 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 \le B_i \le L$ for $i = 1, 2, \ldots, N$), such that $B_i$ is the target spot of the $i$-th ant.

输出格式

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.

2 2
2 1
2 1

0

2 2
1 2
2 1

1

1 10
1
7

4

3 5
1 3 2
5 2 4

*

3 5
1 3 2
4 2 5

2

提示

Explanation of Sample 1:

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

Explanation of Sample 2:

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

Explanation of Sample 5:

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