Question
Array Quest
In a land of digits, Zara and Eli each hold unique arrays - Zara’s of size n, Eli’s of size m. For each number in Eli’s array, find the longest subsequence from Zara’s array where the sum of elements is at most Eli’s number. A subsequence keeps the original order but may skip elements. Determine the maximum subsequence size for each of Eli’s numbers.
Input
The first line of the input contains n denoting the length of the Zara's array.
The second line of the input contains m denoting the length of the Eli's array.
The following line contains the n space-separated integers of the Zara's array.
The last line contains the m space-separated integers of the Eli's array.
Constraints
1 ≤ n, m ≤ 100000
1 ≤ zara[i], eli[i] ≤ 106
The second line of the input contains m denoting the length of the Eli's array.
The following line contains the n space-separated integers of the Zara's array.
The last line contains the m space-separated integers of the Eli's array.
Constraints
1 ≤ n, m ≤ 100000
1 ≤ zara[i], eli[i] ≤ 106
Output
Print a space-separated array answer of length m.
Example
Sample Input
4
3
4 5 2 1
3 10 21
Sample Output
2 3 4
Explanation
- The subsequence [2, 1] has a sum less than or equal to 3. It can be proven that 2 is the maximum size of such a subsequence, so answer[0] = 2.
- The subsequence [4, 5, 1] has a sum less than or equal to 10. It can be proven that 3 is the maximum size of such a subsequence, so answer[1] = 3.
- The subsequence [4, 5, 2, 1] has a sum less than or equal to 21. It can be proven that 4 is the maximum size of such a subsequence, so answer[2] = 4.
4
3
4 5 2 1
3 10 21
Sample Output
2 3 4
Explanation
- The subsequence [2, 1] has a sum less than or equal to 3. It can be proven that 2 is the maximum size of such a subsequence, so answer[0] = 2.
- The subsequence [4, 5, 1] has a sum less than or equal to 10. It can be proven that 3 is the maximum size of such a subsequence, so answer[1] = 3.
- The subsequence [4, 5, 2, 1] has a sum less than or equal to 21. It can be proven that 4 is the maximum size of such a subsequence, so answer[2] = 4.