ООО «Фирма для фирм» занимается созданием и устранением бизнесов уже целых N дней. До этого компания называлась по-другому, но это не помешало им иметь огромную клиентуру и до сих пор. Ежедневно они создают прибыльные фирмы, добавляя нового клиента в свою систему, и устраняют убыточные фирмы, удаляя клиента из своей системы. Для каждого дня известно изменение числа клиентов в системе d_i.

Вадим работает в этой компании аналитиком, и ему только что пришло Q фирменных вопросов — на промежутке времени от l_j-го до r_j-го дня надо найти две различные даты, абсолютное суммарное изменение количества клиентов для которых было бы минимальным. Заметьте, что если для одной пары дат суммарное число клиентов увеличилось на 3, а для другой — уменьшилось на 5, то первая пара лучше, а если для первой пары  — увеличилось на 9, для второй  — увеличилось на 2, то лучше вторая. Вадим сразу понял, что это нужно, чтобы немного запутать инвесторов и спонсоров, но так и не смог понять, как найти подходящие даты. Помогите ему ответить на каждый из фирменных вопросов.

В первой строке дано два целых числа N и Q — количество дней работы фирмы и количество фирменных вопросов (2 ≤ N ≤ 30 000, 1 ≤ Q ≤ 30 000).

Во второй строке даны N целых чисел d_i — изменение числа клиентов в системе в i-й день (−10⁹ ≤ d_i ≤ 10⁹).

В следующих Q строках описаны фирменные вопросы двумя целыми числами l_j и r_j — рассматриваемый промежуток времени в j-м вопросе (1 ≤ l_j < r_j ≤ N).

Для каждого вопроса выведите две различные даты, абсолютное суммарное изменение количества клиентов для которых было бы минимальным. Если таких пар несколько, выведите любую.