Question
Sequence Seek
In a realm of digits, Maya and Leo each possess unique arrays - Maya’s of size n, Leo’s of size m. For each number in Leo’s array, select the longest subsequence from Maya’s array where the sum is at most Leo’s number. A subsequence retains the original order but may omit elements. Find the maximum subsequence size for each of Leo’s numbers.
Input
The first line of the input contains n denoting the length of the Maya’s array.
The second line of the input contains m denoting the length of the Leo's array.
The following line contains the n space-separated integers of the Maya’s array.
The last line contains the m space-separated integers of the Leo's array.
Constraints
1 ≤ n, m ≤ 100000
1 ≤ maya[i], leo[i] ≤ 106
The second line of the input contains m denoting the length of the Leo's array.
The following line contains the n space-separated integers of the Maya’s array.
The last line contains the m space-separated integers of the Leo's array.
Constraints
1 ≤ n, m ≤ 100000
1 ≤ maya[i], leo[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.