Через складні задачі деякі учасники вирішили втекти зі змагання. Однак, щоб цьому запобігти, ЗЛІ автори задач спорудили лабіринт біля виходу зі стадіону. Лабіринт — це сітка розміру $n \times m$, у якій є вхід, вихід і $k$ чорних дір. Учасники, які випадково наступлять на будь-яку чорну діру, проваляться в неї й ніколи не зможуть утекти зі змагання.

Ба більше, автори задач можуть змінювати координати входу й виходу. Ви, нещасний учасник, починаєте біля входу й хочете дістатися виходу, не потрапивши в жодну чорну діру. За один крок ви можете перейти лише в одну з чотирьох сусідніх клітинок. Ви хочете знати: після кожної зміни координат входу й виходу авторами задач яка мінімальна кількість кроків потрібна, щоб дістатися виходу від входу?

Вхідні дані

Перший рядок вхідних даних містить чотири цілі числа $n,m,k,q$ ($1 \le n,m \le 200\,000$, $nm \le 200\,000$, $0 \le k \le 42$, $1 \le q \le 100\,000$) — кількість рядків, кількість стовпців, кількість чорних дір у лабіринті та кількість запитів відповідно.

Наступні $k$ рядків містять опис чорних дір. Кожен із них містить два цілі числа $x,y$ ($1 \le x \le n$, $1 \le y \le m$) — координати чорної діри. Жодні дві чорні діри не розташовані в одній позиції.

Останні $q$ рядків містять опис запитів. Кожен із $q$ рядків містить чотири цілі числа $x_s,y_s,x_t,y_t$ ($1 \le x_s,x_t \le n$, $1 \le y_s,y_t \le m$), де $(x_s,y_s)$ — координати входу, а $(x_t,y_t)$ — виходу.

Вихідні дані

Для кожного запиту в окремому рядку виведіть число — мінімальну кількість кроків, потрібну, щоб дістатися виходу від входу. Якщо дістатися виходу неможливо, виведіть $-1$. Якщо вхід або вихід збігається з чорною дірою, це слід вважати неможливим.

Приклади

Вхідні дані 1

5 5 4 7
2 2
2 3
3 2
3 3
2 1 3 4
1 1 1 1
2 2 2 2
1 1 1 5
2 2 5 5
2 1 2 4
1 1 3 3

Вихідні дані 1

6
0
-1
4
-1
5
-1

Вхідні дані 2

2 3 2 1
1 2
2 1
1 1 2 3

Вихідні дані 2

-1

Примітка

Нижче показано лабіринт і перший запит із першого прикладу.

(a) Лабіринт. (b) Один із можливих найкоротших шляхів для першого запиту.

Позначення: вхід; вихід; чорна діра; один крок.

Рисунок 1: Ілюстрації до прикладів тестових даних.