#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
constexpr ll INF = 1e18;
constexpr int INF2 = 1e9 + 100;
ll a[200200];
int l[200200], r[200200], n, q;
pair<ll, int> operator + (const pair<ll, int> &x, const pair<ll, int> &y) {return make_pair(x.first + y.first, x.second + y.second);}
pair<ll, int> operator - (const pair<ll, int> &x, const pair<ll, int> &y) {return make_pair(x.first - y.first, x.second - y.second);}
ll myabs(ll x){return x<0?-x:x;}
struct Edge{
int s, e;
ll x;
Edge(){}
Edge(int _s, int _e, ll _x): s(_s), e(_e), x(_x) {}
bool operator < (const Edge &E) const{
return tie(x, s) > tie(E.x, E.s);
}
};
struct Linked_List{
int nxt[200200], prv[200200];
pair<ll, int> dist[200200], T; ///dist[i] = (i -> nxt[i])
priority_queue<Edge> pq;
ll a[200200];
void ch(int i, ll x, int y){
T = T - dist[i];
dist[i] = {x, y};
T = T + dist[i];
}
void init(ll s){
//printf(" a[0] = %lld\n", s);
for (int i=1;i<=n;i++) a[i] = ::a[i];
a[0] = s;
fill(nxt, nxt+n+1, -INF2);
fill(prv, prv+n+1, -INF2);
fill(dist, dist+n+1, make_pair(0LL, 0));
for (int i=0;i<n;){
int j = i+1;
ll dmn = a[j] - a[i], dmx = a[j] - a[i];
while(j<=n){
dmn = min(dmn, a[j] - a[j-1]);
dmx = max(dmx, a[j] - a[j-1]);
if (dmn < 0 && dmx > 0) break;
j++;
}
if (dmn==0 && dmx==0) break;
--j;
//printf(" i = %d / j = %d\n", i, j);
nxt[i] = j, prv[j] = i;
if (i){
ch(i, myabs(a[j]-a[i]), 1);
pq.emplace(i, j, dist[i].first);
}
i = j;
}
}
void process(int L){
while(!pq.empty()){
auto [s, e, x] = pq.top();
if (x>L) break;
pq.pop();
if (nxt[s]!=e) continue;
int ss = prv[s], ee = nxt[e];
///delete
nxt[s] = -INF2;
prv[e] = -INF2;
ch(s, 0, 0);
///link
assert(ss!=-INF2);
if (ee==-INF2) continue;
prv[s] = -INF2;
nxt[e] = -INF2;
ch(e, 0, 0);
nxt[ss] = ee, prv[ee] = ss;
if (ss){
ch(ss, myabs(a[ee]-a[ss]), 1);
pq.emplace(ss, ee, dist[ss].first);
}
}
}
ll query(int s, int L, int x){
process(L);
auto [sum, c] = T;
return sum - (ll)L*c + myabs(x - a[nxt[0]]);
}
}Llist, Rlist;
ll pmn[200200], pmx[200200], pL[200200], pR[200200], iL[200200], iR[200200], ans[200200];
ll calc(int L, int R){
int posL = upper_bound(pmn+1, pmn+n+1, -L) - pmn;
int posR = upper_bound(pmx+1, pmx+n+1, R) - pmx;
if (posL==n+1 && posR==n+1) return 0;
if (posL < posR){
int pos = upper_bound(pL+1, pL+n+1, R-L) - pL - 1;
return Rlist.query(iL[pos], R-L, L);
}
else{
assert(posL > posR);
int pos = upper_bound(pR+1, pR+n+1, R-L) - pR - 1;
return Llist.query(iR[pos], R-L, R);
}
assert(0);
return 0;
}
bool cmp(int i, int j){return r[i] - l[i] < r[j] - l[j];}
int main(){
scanf("%d %d", &q, &n);
for (int i=1;i<=q;i++) scanf("%d %d", l+i, r+i);
for (int i=1;i<=n;i++) scanf("%lld", a+i);
Llist.init(-INF);
Rlist.init(INF);
pmn[0] = -INF2, pmx[0] = -INF2, pL[0] = -INF2, pR[0] = -INF2;
for (int i=1;i<=n;i++){
if (pmn[i-1] < -a[i]) iL[i] = i;
else iL[i] = iL[i-1];
if (pmx[i-1] < a[i]) iR[i] = i;
else iR[i] = iR[i-1];
pmn[i] = max(pmn[i-1], -a[i]);
pmx[i] = max(pmx[i-1], a[i]);
pL[i] = max(pL[i-1], a[i] + pmn[i]);
pR[i] = max(pR[i-1], pmx[i] - a[i]);
}
vector<int> idx;
for (int i=1;i<=q;i++) idx.push_back(i);
sort(idx.begin(), idx.end(), cmp);
for (auto &i:idx) ans[i] = calc(l[i], r[i]);
for (int i=1;i<=q;i++) printf("%lld\n", ans[i]);
return 0;
}
