Cho dãy số có \(N\) phần tử \((-10^7 \le A_i \le 10^7)\) và \(Q\) truy vấn (mỗi truy vấn gồm \(L\) và \(R\)). Hãy in ra vị trí mảng con có tổng là bé nhất trong đoạn \([L, R]\)

Ràng buộc:

• \(10 \le N, Q \le 10^5\)
• \(0 \le L \le R \le N\)

Dữ liệu vào:

• Dòng thứ nhất: có 2 số \(N\) và \(Q\)
• Q Dòng tiếp theo: mỗi dòng chứa 2 số \(L\) và \(R\)

Dữ liệu ra:

• Q dòng: mỗi dòng là vị trí \(l', r'\) có tổng bé nhất trong đoạn \(L, R\)

Lưu ý:

• vị trí bắt đầu từ \(0\)

Input

10 3
-1 -2 -3 3 4 5 -10 -20 -30 10000
1 5
0 6
1 9

Output

1 2
6 6
6 8