SPOJ.com - Problem ZSEQ

ZSEQ - ZSequence

no tags

You will be given a sequence A containing N positive integers, a₁, a₂ ... a_N.

Let S(i, j) = a_i + a_{i + 1} + ... + a_j, if i <= j.

You should find K - 1 indexes, m₁ < m₂ < ... < m_{K - 1} such that lb₁ <= S(1, m₁) <= ub₁ ... lb_i <= S(m_{i - 1} + 1, m_i) <= ub_i and lb_K <= S(m_{K - 1} + 1, N) <= ub_K.

If there are multiple solution, print the first lexicographically.

Input

The 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 a₁, a₂ ... a_N, respectively, 1 <= a_i <= 10⁵.

i-th of the next K lines contain integers lb_i and ub_i, 1 <= lb_i <= ub_i <= 10⁹.

Output

On 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.

Example

Input:
4 3
1
2
3
4
1 3
2 4
3 10

Output:
1 2

Input:
4 3
1
2
3
4
1 3
2 4
3 4

Output:
2 3

Input:
4 3
1
2
3
4
1 3
2 4
3 3

Output:
-1

Submit solution!

hide comments



	Shaka Shadows: 2010-10-04 19:32:12 Even when there is no point in setting a customized memory limit, here memory is not what we have to worry about (except for Java solutions of course). Time limit is the big deal here. Thanks Slobodan, if we take away the memory stuffs, I do think actually it is a good problem.
	Slobodan: 2009-10-13 00:52:40 Well, I hope you will forgive me this time. I already set memory limit and some members maybe spent more time trying to solve with that constraint. I promise that in future I will not add problems to SPOJ with limited memory, at least those for Java and if it can't be specified how much memory JVM will use. Please, don't get me wrong, I just don't think it would be ok to some members to change memory limit now.
	Nikhil Garg: 2009-10-08 09:49:14 We can change the amount of memory allocated for java program but that cant be done from inside a program. That has to be set at the JVM settings on command prompt that too with sudo power only. So this is as good as saying - problem is not solvable in java !
	[Trichromatic] XilinX: 2009-09-29 14:42:00 Mmm, I do agree with Jelle van den Hooff. I've got Accepted.
	Slobodan: 2009-09-20 14:07:39 > The question is why would you want a memory limit? The most important reason is because I first set it on another judge and there I've set that memory limit. I don't agree that the problem is bad if you have strict memory limit. Actually, you always have some memory limit. Why do you think such problems are bad?
	Jelle van den Hooff: 2009-09-20 13:55:49 Case in point: 5000^2 _bits_ is only 3 megabytes, so I just don't get the limit.
	Jelle van den Hooff: 2009-09-20 13:53:54 The question is why would you want a memory limit? If the difficulty in the problem comes from having a strict memory limit then the problem is bad. Nearly all of the SPOJ problems don't have a memory limit (even the ones taken from other judges).
	Slobodan: 2009-09-20 11:29:10 Well, is there a way to specify memory limit for certain language?
	[Trichromatic] XilinX: 2009-09-20 10:48:31 The memory limit is useless. For some languages like Java, the memory used is always ~200MB, even though the program just solves problem TEST.

Submit solution!

Added by:	Slobodan
Date:	2009-09-19
Time limit:	0.100s-1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ERL JS-RHINO
Resource:	Z-Trening, own problem