AlgoLiga 2018

Burmistrz pewnej bardzo górzystej, gminy stwierdził, że dosyć ma już nudnego górskiego krajobrazu:

- Tylko skały i doliny, nic poza tym, tak dłużej być nie może! Potrzebujemy tu jakichś jezior, przecież teraz wszyscy jeżdżą na wakacje nad jeziora!

Od tej pory postanowił wyjątkowo oszczędnie dysponować budżetem tak, aby zaraz na początku przyszłego roku skonstruować wodociąg za pomocą którego wytworzy sztuczne jeziora pomiędzy górskimi szczytami. Jako, że burmistrza nikt już od jego wizji odwieźć raczej nie zdoła, trzeba mu pomóc na ile to tylko możliwe. Burmistrz obliczył, że jego wodociąg zalewać będzie równomiernie cały obszar z prędkością wynoszącą jeden metr na dobę (niezależnie od ukształtowania terenu, w końcu ziemia również musi nasiąknąć wodą, aby mogło powstać nad nią jezioro). Chciałby on, aby powstała ściśle określona liczba jezior. Poprosił Cię zatem o pomoc - napisz program, który obliczy ile jezior jest po dokładnie x dniach równomiernego zalewania obszaru.

Wejście

W pierwszej linii wejścia znajduje się liczba m (1 ≤ m ≤ 6) określające ilość zestawów danych. Każdy zestaw składa się z trzech linii: w pierwszej znajdują się dwie liczby n oraz d (1 ≤ n ≤ 10⁵, 1 ≤ d ≤ 10⁵) - pierwsza z nich określa szerokość zalewanego obszaru w metrach, druga zaś liczbę zapytań na które burmistrz będzie chciał poznać odpowiedź. Drugą linię każdego zestawu stanowi ciąg n liczb (z zakresu od 0 do 10⁹) - każda z nich opisuje wysokość, danego metra szerokości, ponad poziom 0. W trzeciej i ostatniej linii znajduje się ciąg d liczb (z zakresu od 0 do 10⁹) - są to zapytania jakie zada burmistrz, każda z liczb określa dobę zalewania po której nasz wizjoner chce znać liczbę jezior (jeziora znajdujące się skrajnie z lewej lub prawej strony naszej dwuwymiarowej gminy również należy dodać do wyniku).

Wyjście

Na wyjściu należy w osobnej linii dla każdego zestawu danych wypisać d liczb - każda z nich powinna określać liczbę jezior jakie powstały po upłynięciu wczytanego na wejściu czasu zalewania.

Przykład

Wejście:

1
12 6
1 4 2 3 1 1 3 4 4 2 3 2
5 0 1 4 2 3

Wyjście:

1
0
0
3
2
5