Хмарочоси
У прибережному селі є проспект хмарочосів. Кожен хмарочос має ширину 100 м і певну висоту. Через високу вартість землі, будь-які два сусідні хмарочоси стоять впритул один до одного. Проспект розташований близько до пляжу, тому вулиця знаходиться на рівні моря.
На жаль, цього року через глобальне потепління рівень моря почав підвищуватися на один метр щодня. Якщо висота хмарочоса не перевищує поточний рівень моря, він вважається затопленим.
Регіон — це максимальна множина незатоплених, суміжних хмарочосів. Цей термін має особливе значення, оскільки достатньо доставити товари (як-от електроенергію, моркву чи капусту) до будь-якого окремого хмарочоса в кожному регіоні. Отже, міський голова хоче знати, скільки регіонів буде в важкі дні, що настануть.
Нижче наведено приклад проспекту з 5 хмарочосами після 2 днів.
Вхідні дані
Вхід містить кілька тестових випадків. Перша строка містить ціле число t (t ≤ 15), що позначає кількість тестових випадків. Далі йдуть t тестових випадків. Кожен з них починається з рядка, що містить два числа n і d (1 ≤ n, d ≤ 10^6), де n — це кількість хмарочосів, а d — кількість днів, які цікавлять мера. Хмарочоси пронумеровані зліва направо. Наступний рядок містить n цілих чисел h_1, h_2, ..., h_n, де 1 ≤ h_{i} ≤ 10^9 — це висота хмарочоса i. Третій рядок одного тестового випадку містить d чисел t_j, таких що 0 ≤ t_1 < t_2 < ... < t_{d-1} < t_{d} ≤ 10^9.
Вихідні дані
Для кожного тестового випадку виведіть d чисел r_1, r_2, ..., r_d, де r_j — це кількість регіонів на день t_j.