Description

Given a sequence A = a₁, a₂, ..., a_N and a number K.

A continuous subsequence A[L ... R] = a_L, ..., a_R of  A is called beautiful if the sum of A[L ... R] is K.

For example, if A = 3, 1, 2, 2, 4 and K = 6.

Then

• A[1, 3] = 3, 1, 2 is beautiful.
• A[1, 4] = 3, 1, 2, 2 is not beautiful because 3 + 1 + 2 + 2 is not 6.
• A[4, 5] = 2, 4 is beautiful.

 

Please find the number of beautiful continuous subsequence of A.

 

Input

The first line of the input contains a number T — the number of test cases.

The first line of each test case contains two numbers N K — the length of A and the number K described in the statement.

The second line of each test case contains N numbers — a₁, a₂, ..., a_N.

 

For each test,

1. T ≤ 10, N ≤ 10³, |a_i| ≤ 10⁹, |K| ≤ 10⁹.
2. T ≤ 10, N ≤ 10³, |a_i| ≤ 10⁹, |K| ≤ 10⁹.
3. T ≤ 10, N ≤ 10³, |a_i| ≤ 10⁹, |K| ≤ 10⁹.
4. T ≤ 10, N ≤ 10⁵, |a_i| ≤ 10⁹, |K| ≤ 10⁹.
5. T ≤ 10, N ≤ 10⁵, |a_i| ≤ 10⁹, |K| ≤ 10⁹.
6. T ≤ 10, N ≤ 10⁵, |a_i| ≤ 10⁹, |K| ≤ 10⁹.

 

Output

For each test case, print the number of beautiful continuous subsequence.

 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Elephants love to eat KuoTA (鍋貼), so Elfnt decided to open a restaurant called "八方來財", serving delicious KuoTA to satisfy their cravings.

On the grand opening day, many groups of elephants are lining up outside the restaurant. Each group consists $a_i$ elephants. To serve them efficiently and maximize profit, Elfnt follows a strategy:

• From time to time, Elfnt announces that a table with $x_j$ seats is available.
• When a table becomes available, the group with the largest number of elephants not exceeding $x_j$ gets to leave the line and enter the restaurant.
• If there are multiple groups with the same number of elephants, the one that is earliest in the queue gets chosen.

Each group can only enter the restaurant once, and each table can only seat one group.

Input

The first line contains two integers $n$ and $k$, representing the number of elephant groups and the number of tables that will become available.

The second line contains $n$ integers $a_1, a_2, ..., a_n$, where $a_i$ is the number of elephants in the $i$-th group (in queue order).

The third line contains $k$ integers $x_1, x_2, ..., x_k$, where $x_j$ is the number of seats of the $j$-th available table.

Constraints

• $1 \leq n, k \leq 2 \times 10^5$
• $1 \leq a_i, x_j \leq 10^9$

Subtask

1. (Testcases 1-4) The number of elephants in each groups is distinct, i.e., $a_i \neq a_k \ \forall \ i \neq k$
2. (Testcases 5-8) No additional constraints.

Output

Output a single line containing $n$ integers, each followed by a space (including the last one) and NO \n in the end.

The $i$-th number represents the order in which the $i$-th group enters the restaurant ($1$-based).

If a group never gets a seat, output $-1$ for that group.

Note

Visualizations for Sample 1 and Sample 2:

Sample1:

Sample2:

Sample Input  Download

Sample Output  Download

Tags

Discuss