Један град има \(n\) становника и само једну улицу коју можемо преставити \(x\)-осом. За сваког становника је позната координата његове куће на \(x\)-оси, (могуће је да неколико кућа има исту координату). У овај град долази познати сајбер-преварант Џими Рудар који планира да отвори тачно две продавнице опреме за рударење биткоина - у једној ће продавати пијуке а у другој ашове. Џими Рудар зна да ће, након отварања продавница, сваки становник појурити у њему најближу продавницу да купи опрему а уколико су обе продавнице подједнако удаљене, становник ће случајно одабрати једну од њих (њима није битно да ли им треба пијук или ашов, битно да се рударе биткоини).

Џими жели да оптимално изгради продавнице и већ је направио \(m\) потенцијалних планова: сваки план је пар бројева \((А_i, B_i)\) и означава да Џими жели да сагради продавницу пијука на координати \(A_i\) и продавницу ашова на координати \(B_i\) на \(x\)-оси. Џими има молбу за вас: за сваки од \(m\) потенцијалних планова, израчунајте укупну раздаљину коју би прешли сви становници уколико би продавнице биле изграђене на координатама задатим у том плану. Уколико ово одрадите, добијате 5кг биткоина од Џимија! Подсетимо се да је растојање између тачака \(X\) и \(Y\) на \(x\)-оси једнако \(|X - Y|\).

Опис улаза

У првом реду стандардног улаза налазе се два природна броја \(n\) и \(m\), број кућа и број упита, редом. У наредном реду налази се \(n\) природних бројева \(X_i\) који представљају координате кућа. У наредних \(m\) редова налазе се по два природна броја \(A_i\) и \(B_i\) који представљају план за изградњу продавница на тим координатама.

Опис излаза

Исписати \(m\) природних бројева, у сваком реду по један, који представљају одговоре на датих \(m\) упита у одговарајућем редоследу.

Примери

Пример 1

Улаз

5 2
12 50 70 1 10
10 100
60 8

Излаз

81
33

Пример 2

Улаз

3 1
1000000000 1000000000 1000000000
1 2

Излаз

2999999994

Објашњење примера

У првом тест примеру, први план предвиђа изградњу продавнице пијука и ашова на координатама 10 и 100, редом. У том случају, први становник (са координатом 12) иде у продавницу пијука и прелази растојање \(|10 - 12| = 2\); други становник (координата 50) такође иде у продавницу пијука и прелази растојање \(|50 - 10| = 40\); трећи становник иде у продавницу ашова и прелази растојање \(|70 - 100| = 30\); четврти становник прелази растојање 9 док пети прелази растојање 0. Укупно пређено растојање је \(2 + 40 + 30 + 9 + 0 = 81\). У случају другог плана (продавнице на координатама 60 и 8) укупно пређено растојање је \(4 + 10 + 10 + 7 + 2 = 33\).

Ограничења

• \(1 \leq n \leq 10^5\)
• \(1 \leq m \leq 10^5\)
• \(1 \leq X_i \leq 10^9\)
• \(1 \leq A_i, B_i \leq 10^9\)

Тест примери су подељени у пет дисјунктних група: * У тест примерима који вреде \(20\) поена важиће \(1 \leq N, M \leq 1000\). * У тест примерима који вреде \(15\) поена важиће \(A_i = B_i\) за свако \(i\). * У тест примерима који вреде \(15\) поена важиће \(A_i \leq min X\) и \(max X \leq B_i\) за свако \(i\). * У тест примерима који вреде \(20\) поена важиће \(1 \leq A_i, B_i, X_i \leq 10^6\). * У тест примерима који вреде \(30\) поена нема додатних ограничења.