Problem 95: Towers

Știind că ai învățat destul de bine să configurezi servere de Neuralink (atât de bine, încât faci câte un server nou zilnic), te-ai hotărât să preiei controlul total asupra rețelei și să îți creezi și propriul sistem de turnuri de comunicare (ale căror poziții pot fi reprezentate ca puncte pe axa Ox). Te gândești să cumperi o rețea de turnuri, pe care vrei să o împarți în K subrețele, astfel încât fiecare turn să fie în exact o rețea. Singurul criteriu pe care îl ai este ca două turnuri din subrețeaua i să se afle la distanțe cel puțin $R_i$ (altfel ar fi redundante pentru rețeaua ta). Găsești mai multe oferte pentru rețele de turnuri pe care le poți cumpăra și vrei să vezi pentru fiecare dacă poate fi împărțită în subrețele după criteriul tău.

Date de intrare

Pe prima linie se găsește un număr T reprezentând numărul de oferte. Următoarele 3T linii conțin cele T scenarii.
Linia 3i + 1 conține valorile N și K pentru cel de-al i-lea scenariu.
Linia 3i + 2 conține valorile $R_i$ pentru cel de-al i-lea scenariu.
Linia 3i + 3 conține N valori $P_i$ , coordonatele turnurilor pentru cel de-al i-lea scenariu.

Date de ieșire

Se vor afișa T linii, pentru fiecare test 1 dacă turnurile se pot împărți după criteriul dat, respectiv 0 dacă nu.

Restricții și precizări

4 ≤ T ≤ 1000
1 ≤ K ≤ 3
$K < N < \frac{S}{4} ≤ 5 · 10^5$ , unde S este suma tuturor N-urilor dintr-un test.
$1 ≤ R_i ≤ 10^8$ pentru 1 ≤ i < K
$0 ≤ P_i ≤ 10^8$ pentru 1 ≤ i < N
$P_i < P_{i+1}$ pentru 1 ≤ i < N

Subtask 1 (4 puncte)

$S ≤ 2 · 10^6$
K = 1

Subtask 2 (5 puncte)

$S ≤ 2 · 10^6$
K = 3
$R_0 = R_1 = R_2$

Subtask 3 (9 puncte)

S ≤ 40
K = 3

Subtask 4 (11 puncte)

S ≤ 800
K = 3

Subtask 5 (13 puncte)

$S ≤ 2 · 10^6$
K = 2

Subtask 6 (14 puncte)

S ≤ 6 000
K = 3

Subtask 7 (22 puncte)

$S ≤ 5 · 10^5$
K = 3

Subtask 8 (22 puncte)

$S ≤ 2 · 10^6$
K = 3

Exemplu

stdin

2
7 2
8 5
1 2 4 9 11 14 15
7 3
8 5 10
1 2 4 9 11 14 15

stdout

0
1

Explicații

Pentru prima ofertă, nu există o împărțire validă în subrețele.
Pentru a doua ofertă, poți forma prima subrețea din turnurile de la coordonatele 1 și 11, cea de-a doua din turnurile de la coordonatele 2, 9 și 14, iar cea de-a treia din turnurile de la coordonatele 4 și 15.

Towers