LLC “Company for Companies” has been creating and eliminating businesses for a whole N days. Before this, the company was called something else, but that did not prevent them from having a huge clientele even now. Every day, they create profitable firms by adding a new client to their system and eliminate unprofitable firms by removing a client from their system. For each day, the change in the number of clients in the system d_i is known.

Vadim works as an analyst at this company, and he has just received Q company questions—during the time interval from the l_j-th to the r_j-th day, he needs to find two different dates for which the absolute total change in the number of clients would be minimal. Note that if for one pair of dates the total number of clients increased by 3, and for another it decreased by 5, then the first pair is better; if for the first pair it increased by 9, and for the second it increased by 2, then the second is better. Vadim immediately understood that this was needed to confuse investors and sponsors a bit, but he could not figure out how to find the suitable dates. Help him answer each of the company questions.

The first line contains two integers N and Q—the number of days the company has been operating and the number of company questions (2 ≤ N ≤ 30 000, 1 ≤ Q ≤ 30 000).

The second line contains N integers d_i—the change in the number of clients in the system on the i-th day (−10⁹ ≤ d_i ≤ 10⁹).

The following Q lines describe the company questions with two integers l_j and r_j—the time interval considered in the j-th question (1 ≤ l_j < r_j ≤ N).

For each question, output two different dates for which the absolute total change in the number of clients would be minimal. If there are multiple such pairs, output any.