Trên một trục đường dài thẳng có \(n\) trạm xe buýt cách đều nhau, các trạm được đánh số từ \(1\) đến \(n\). Để đi lại giữa hai trạm liên tiếp bất kì bằng xe buýt mất \(a\) đồng. Trong \(n\) trạm có \(m\) trạm đặc biệt là các trạm \(p_1, p_2, ..., p_m (1 \leq p_1, p_2, \dots , p_m \leq n)\). Có loại xe buýt nhanh sẽ chỉ dừng đỗ tại các trạm đặc biệt này, nếu sử dụng xe buýt nhanh để đi từ trạm đặc biệt \(p_i\) đến trạm đặc biệt \(p_j\) sẽ mất \(b\) x \(|p_i - p_j|\) đồng.

Yêu cầu: Cho \(q\) câu hỏi, câu hỏi thứ \(k\) \((1 \leq k \leq q)\) cần trả lời đi từ trạm \(x_k\) \((1 \leq x_k \leq n)\) tới trạm \(y_k\) \((1 \leq y_k \leq n)\) hết ít nhất bao nhiêu tiền.

Input

• Dòng đầu chứa các số nguyên dương \(n, m, q, a, b\) \((a, b \leq 10^6; 2 \leq m \leq n);\)
• Dòng thứ hai chứa \(m\) số nguyên dương \(p_1, p_2, \dots, p_m;\)
• Dòng thứ \(k\) \((1 \leq k \leq q)\) chứa hai số nguyên dương \(x_k, y_k\).

Output

• Ghi ra thiết bị ra chuẩn gồm \(q\) dòng, dòng thứ \(k\) chứa một số là câu trả lời cho câu hỏi thứ \(k\).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n, m, q \leq 100; a = b\)
• Subtask \(2\) (\(25\%\) số điểm): \(n, m \leq 100; m = 2; p_1 = 1; p_2 = n\)
• Subtask \(3\) (\(25\%\) số điểm): \(n, m, q \leq 100\)
• Subtask \(4\) (\(25\%\) số điểm): \(n, m, q \leq 10^6\).

Example

5 2 2 2 1
2 4
1 5
2 3 

6
2