z-sequence
You will be given a sequence A containing N positive integers, a1, a2, ..., aN. Let S(i, j) = ai + ai + 1 + ... + aj, if i <= j.
You should find K - 1 indexes, m1 < m2 < ... < mK - 1 such that lb1 <= S(1, m1) <= ub1,..., lbi <= S(mi - 1 + 1, mi) <= ubi and lbK <= S(mK - 1 + 1, N) <= ubK.
In the case of multiple solution, print the lexicographically smallest one.
InputThe first line of the standard input contains two space-separated integers N (2 <= N <= 5 000) and K (1 <= K - 1 <= N - 1). Next N lines contain integers a1, a2, ..., aN, respectively, 1 <= ai <= 10^5]].
i-th of the next K lines contain integers lbi and ubi, 1 <= lbi <= ubi <= 10^9.
i-th of the next K lines contain integers lbi and ubi, 1 <= lbi <= ubi <= 10^9.
OutputOn the first line of the standard output you should print space-separated K - 1 indices of the solution as already explained. If such solution does not exist, you should print only one integer -1.
Input:
Output:
4 3
1
2
3
4
1 3
2 4
3 10Output:
1 2Input:
Output:
4 3
1
2
3
4
1 3
2 4
3 4Output:
2 3Input:
Output:
4 3
1
2
3
4
1 3
2 4
3 3Output:
-1Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.