Disappeared Block

Time Limit: 10000/5000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

There are n columns of blocks on the ground, the ith columns has hi blocks.

One day, we observed a curious phenomenon that the bottom blocks will disappear in one second.

We need to predict what will happen in the future.

You job is to tell us that how many parts the blocks will be separated into at the ith second.


The input contains several test cases.

The first line contains an integer T(T ≤ 15) denoting the number of test cases. Then T test cases follow.

Each of them begins with a line containing two numbers n and m(1 ≤ n, m ≤ 106), n is the number of columns and m is the number of seconds which we wants to query.

The next line contains n integers h1,h2,..., hn where 1 ≤ hi ≤ 109 is the height of column i.

The third line of a single test case contains numbers sj(0 ≤ s1 < s2 < ... < sm-1 < sm ≤ 109).


For each test case, output one line containing "Case #x: " followed by m numbers x1,x2,...xj,...,xm, where xj is the number of parts at second sj.

Sample Input

4 3
3 2 6 4
0 1 2
5 5
1 3 5 1 3
0 1 3 4 10

Sample Output

Case #1: 1 1 2 
Case #2: 1 2 1 1 0




Solved Number133
Submit Number393
Problem Tags
two pointers
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^