Хмарочоси#5731

Хмарочоси

1 секунда

64 мегабайти

Дуже легка

У прибережному селі є проспект хмарочосів. Кожен хмарочос має ширину $100$ м і певну висоту. Через високу вартість землі, будь-які два сусідні хмарочоси стоять впритул один до одного. Проспект розташований близько до пляжу, тому вулиця знаходиться на рівні моря.

На жаль, цього року через глобальне потепління рівень моря почав підвищуватися на один метр щодня. Якщо висота хмарочоса не перевищує поточний рівень моря, він вважається затопленим.

Регіон — це максимальна множина незатоплених, суміжних хмарочосів. Цей термін має особливе значення, оскільки достатньо доставити товари (як-от електроенергію, моркву чи капусту) до будь-якого окремого хмарочоса в кожному регіоні. Отже, міський голова хоче знати, скільки регіонів буде у важкі дні, що настануть.

Нижче наведено приклад проспекту з $5$ хмарочосами після $2$ днів.

Вхідні дані

Вхід містить кілька тестових випадків. Перший рядок містить ціле число $t$ ( $t \leq 15$ t \leq 15), що позначає кількість тестових випадків. Далі йдуть $t$ тестових випадків. Кожен з них починається з рядка, що містить два числа $n$ і $d$ ( $1 \leq n, d \leq 1 0^{6}$ 1 \leq n, d \leq 10^6), де $n$ — це кількість хмарочосів, а $d$ — кількість днів, які цікавлять мера. Хмарочоси пронумеровані зліва направо. Наступний рядок містить $n$ цілих чисел $h_{1}$ h_1, $h_{2}$ h_2, ..., $h_{n}$ h_n, де $1 \leq h_{i} \leq 1 0^{9}$ 1 \leq h_{i} \leq 10^9 — це висота хмарочоса $i$ . Третій рядок одного тестового випадку містить $d$ чисел $t_{j}$ t_j, таких що $0 \leq t_{1} < t_{2} < ... < t_{d - 1} < t_{d} \leq 1 0^{9}$ 0 \leq t_1 < t_2 < ... < t_{d-1} < t_{d} \leq 10^9.

Вихідні дані

Для кожного тестового випадку виведіть $d$ чисел $r_{1}$ r_1, $r_{2}$ r_2, ..., $r_{d}$ r_d, де $r_{j}$ r_j — це кількість регіонів на день $t_{j}$ t_j.

Приклади

Приклад 1