Drazil — это обезьяна. Он живет в парке круглой формы. Вокруг парка высажено n деревьев. Расстояние от i-го дерева до (i + 1)-го равняется d_i, расстояние от n-го дерева до первого дерева равняется d_n. Высота i-го дерева равняется h_i.

Drazil начинает каждый день с утренней пробежки. Утренняя пробежка состоит из следующих шагов:

• Drazil выбирает два различных дерева;
• Сперва он забирается на первое дерево;
• Затем он слезает с первого дерева, бежит вокруг парка (в одном из двух возможных направлений) ко второму дереву и забирается на него;
• Наконец, он слезает со второго дерева;

Но с недавнего времени рядом с некоторым множеством деревьев, образующим непрерывный отрезок, постоянно играют дети. Drazil терпеть не может детей, поэтому он не может выбирать деревья в близости от детей. Он даже не может перемещаться рядом с этими деревьями.

Если Drazil выберет два дерева x и y, то можно записать энергию, необходимую на утреннюю пробежку, как 2(h_x + h_y) + dist(x, y). Так как дети находятся на ровно одной из двух дуг, соединяющих x и y, то путь, по которому побежит Drazil, определяется однозначно, здесь за dist(x, y) обозначается его длина.

И вот, вы знаете, что на i-й день дети играют между a_i-ым и b_i-ым деревом. Более формально, если a_i ≤ b_i, то дети играют вокруг деревьев с индексами в диапазоне [a_i, b_i], в противном случае они играют вокруг деревьев с индексами в диапазоне .

Пожалуйста, помогите Drazil для каждого дня определить, какие два дерева он должен выбрать, чтобы потратить как можно больше энергии (ведь он хочет быть крутой стройной обезьянкой) и посчитайте количество энергии, которое будет затрачено на утреннюю пробежку.