마천루

바닷가 마을에 고층 빌딩이 늘어선 대로가 하나 있다. 각 빌딩은 폭이 100m이고 저마다 정해진 높이를 가진다. 땅값이 매우 비싸기 때문에 이웃한 두 빌딩은 서로 맞붙어 있다. 대로는 해변에 바로 붙어 있어서 거리의 높이는 정확히 해수면과 같다.

안타깝게도 올해는 지구 온난화 때문에 해수면이 매일 1m씩 상승하기 시작했다. 어떤 빌딩의 높이가 현재 해수면보다 높지 않으면(즉, 해수면 이하이면) 그 빌딩은 침수된 것으로 본다. 구역이란 침수되지 않은 채 서로 인접해 있는 빌딩들의 극대(maximal) 집합을 말한다. 각 구역에는 어느 한 빌딩에만 물자(전기, 당근, 양배추 등)를 전달하면 충분하기 때문에 이 개념이 특히 중요하다. 그래서 시장은 앞으로 다가올 힘든 날들에 구역이 몇 개나 생기는지 알고 싶어 한다.

아래는 빌딩 5개짜리 대로에서 2일이 지난 뒤의 모습을 나타낸 예시이다.

입력에는 여러 개의 테스트 케이스가 들어 있다. 첫째 줄에 테스트 케이스의 개수 $t$ ($t \le 15$)가 주어진다. 이어서 $t$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄에는 두 정수 $n$과 $d$ ($1 \le n, d \le 10^6$)가 주어진다. $n$은 빌딩의 수, $d$는 시장이 질의하려는 날의 수이다. 빌딩은 왼쪽에서 오른쪽으로 번호가 매겨진다. 둘째 줄에는 $n$개의 정수 $h_1, h_2, \dots, h_n$이 주어지며, $1 \le h_i \le 10^9$는 빌딩 $i$의 높이이다. 셋째 줄에는 $d$개의 정수 $t_j$가 주어지며 $0 \le t_1 < t_2 < \dots < t_d \le 10^9$를 만족한다.

각 테스트 케이스마다 $d$개의 수 $r_1, r_2, \dots, r_d$를 한 줄에 공백으로 구분하여 출력한다. 여기서 $r_j$는 날 $t_j$에서의 구역의 수이다.