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