Cho đơn đồ thị vô hướng, liên thông, không có trọng số bao gồm $2n$ đỉnh, các đỉnh được đánh số từ $0$ đến $2n-1$. Các cạnh của đồ thị được xây dựng như sau:

• Có cạnh nối giữa hai đỉnh $0$ và $2n-1$ của đồ thị.
• Có cạnh nối giữa hai đỉnh $u$ và $u+1$ của đồ thị với mọi $0\le u<2n-1$.
• Có cạnh nối giữa hai đỉnh $k_i$ và $k_i+n$ của đồ thị với mọi $1\le i\le m$.

Vì vậy, đồ thị có tổng cộng $2n+m$ cạnh.

Thực hiện $q$ truy vấn, với mỗi truy vấn thứ $j$ $(1\le j\le q)$, yêu cầu tìm độ dài đường đi ngắn nhất giữa hai đỉnh $x_j$ và $y_j$.

Input

• Dòng đầu tiên chứa ba số nguyên $n,m,q$ $(2\le n\le 5\times {10}^8$ $;$ $1\le m\le 5\times {10}^5$ $;$ $1\le q\le 2\times {10}^4)$.
• Dòng thứ hai chứa $m$ số nguyên $k_i$ $(0\le k_1<k_2<...<k_m\le n-1)$.
• $q$ dòng tiếp theo, dòng thứ $j$ chứa hai số nguyên $x_j$ và $y_j$ $(0\le x_j,y_j\le 2n-1)$.

Output

• Với mỗi truy vấn, in ra độ dài đường đi ngắn nhất giữa hai đỉnh $x_j$ và $y_j$ trên một dòng.

Examples

Sample Input

3 2 3
0 2
1 5
2 0
4 1

Sample Output

2
2
3

Scoring

• Subtask $1$ $-$ $500$ điểm: $n,m,q\le 1000$
• Subtask $2$ $-$ $750$ điểm: $n\le {10}^7$ $;$ $m,q\le 1000$
• Subtask $3$ $-$ $750$ điểm: $x_j=0$ với mọi truy vấn
• Subtask $4$ $-$ $500$ điểm: Không có ràng buộc gì thêm

Notes

Trong ví dụ, đồ thị được mô tả như trong hình sau: