Time Limit: 6000/3000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

> Podracing was a dangerous racing sport on planets such as Malastare, Theron, and Tatooine. Racers could perform multiple laps on a particular race track, moving at dangerous and, at times, deadly speeds. The races were performed using craft known as Podracers or pods, which were small, one-man craft propelled by large engines. Races could then be projected in entertainment establishments throughout the galaxy.

>

> — Wookieepedia

Anakin Skywalker is the only human known to compete in Podracing. To win this dangerous racing, in which the participant may lose his life, little Anakin has to practice with his friends under a much softer rule.

Participants have to compete in a circular track ($L$ in length). At the beginning of the racing (time zero), all podracers are at distinct locations. The $i$-th podracer starts at location $d_i$ $(0 \le d_i \lt L)$, then the Podracing starts. Since all Anakin’s friends built their own podracers, they have distinct speeds. The speed of the $i$-th participant is $v_i$ (the speed can either be positive or negative. A positive speed indicates a clockwise podracer and a negative speed indicates a counterclockwise podracer).

Furthermore, the $i$-th participant has a power of $w_i$. During the racing, participants may meet (being located at the same place at the same time). To better record the progress of the racing, Anakin decides to mark the participants whose powers are strictly less than the maximum power of the participants he ever met, indicating that they are a loser. Since they are just practicing, being marked does not mean the participant is out, he can continue competing and mark someone else with less power.

When no one can be marked, the racing terminates.

Find the terminal time of the racing.

>

> — Wookieepedia

Anakin Skywalker is the only human known to compete in Podracing. To win this dangerous racing, in which the participant may lose his life, little Anakin has to practice with his friends under a much softer rule.

Participants have to compete in a circular track ($L$ in length). At the beginning of the racing (time zero), all podracers are at distinct locations. The $i$-th podracer starts at location $d_i$ $(0 \le d_i \lt L)$, then the Podracing starts. Since all Anakin’s friends built their own podracers, they have distinct speeds. The speed of the $i$-th participant is $v_i$ (the speed can either be positive or negative. A positive speed indicates a clockwise podracer and a negative speed indicates a counterclockwise podracer).

Furthermore, the $i$-th participant has a power of $w_i$. During the racing, participants may meet (being located at the same place at the same time). To better record the progress of the racing, Anakin decides to mark the participants whose powers are strictly less than the maximum power of the participants he ever met, indicating that they are a loser. Since they are just practicing, being marked does not mean the participant is out, he can continue competing and mark someone else with less power.

When no one can be marked, the racing terminates.

Find the terminal time of the racing.

The first line of the input contains an integer $T$ ($T\le20$), denoting the number of test cases.

For each test case, the first line contains two integers $n, L$ ($1 \le L \le 10^6$).

The next line contains $n$ distinct integers, denoting $d_i$ ($0 \le d_i \lt L$).

The next line contains $n$ distinct integers, denoting $v_i$ ($|v_i|\le10^6$).

The next line contains $n$ integers, denoting $w_i$ ($0 \le w_i \le n$).

The sum of $n$ in all test cases won't be greater than $10^5$.

For each test case, the first line contains two integers $n, L$ ($1 \le L \le 10^6$).

The next line contains $n$ distinct integers, denoting $d_i$ ($0 \le d_i \lt L$).

The next line contains $n$ distinct integers, denoting $v_i$ ($|v_i|\le10^6$).

The next line contains $n$ integers, denoting $w_i$ ($0 \le w_i \le n$).

The sum of $n$ in all test cases won't be greater than $10^5$.

提交代码