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