#include <bits/stdc++.h>
using namespace std;
int lungime;
set <int> capat;
inline int Distanta (const int nod_1 , const int nod_2)
{
return min(abs(nod_1 - nod_2) , 2 * lungime - abs(nod_1 - nod_2));
}
int main ()
{
ios :: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int numar_muchii , numar_intrebari;
cin >> lungime >> numar_muchii >> numar_intrebari;
while (numar_muchii--)
{
int inceput;
cin >> inceput;
capat.insert(inceput);
capat.insert(inceput + lungime);
}
while (numar_intrebari--)
{
int inceput , sfarsit;
cin >> inceput >> sfarsit;
int rezultat = Distanta(inceput , sfarsit);
set <int> :: iterator locatie = capat.lower_bound(inceput);
if (locatie != capat.end())
{ rezultat = min(rezultat , Distanta(inceput , *locatie) + 1 + Distanta((*locatie + lungime) % (2 * lungime) , sfarsit)); }
else
{
locatie = capat.begin();
rezultat = min(rezultat , Distanta(inceput , *locatie) + 1 + Distanta((*locatie + lungime) % (2 * lungime) , sfarsit));
locatie = capat.find(*capat.rbegin());
}
if (locatie != capat.begin()) { locatie--; }
else { locatie = capat.find(*capat.rbegin()); }
rezultat = min(rezultat , Distanta(inceput , *locatie) + 1 + Distanta((*locatie + lungime) % (2 * lungime) , sfarsit));
cout << rezultat << '\n';
}
return 0;
}
