Из-за сложности задач некоторые участники решают сбежать с этого соревнования. Однако, чтобы этого не случилось, ЗЛЫЕ авторы задач построили лабиринт у выхода со стадиона. Лабиринт представляет собой сетку $n\times m$, в которой находятся вход, выход и $k$ чёрных дыр. Участник, случайно наступивший на чёрную дыру, провалится в неё и уже никогда не сможет сбежать с соревнования.

Хуже того, авторы задач могут менять координаты входа и выхода. Вы — бедный участник, который начинает путь со входа и хочет добраться до выхода, не наступив ни на одну чёрную дыру. За один шаг вы можете перейти только в одну из четырёх соседних клеток. Вы хотите знать, какое минимальное количество шагов нужно для пути от входа до выхода после каждого изменения их координат авторами задач.

Входные данные

Первая строка входных данных содержит четыре целых числа $n,m,k,q$ ($1\le n,m\le200\,000$, $nm\le200\,000$, $0\le k\le42$, $1\le q\le100\,000$) — количество строк, количество столбцов, количество чёрных дыр в лабиринте и количество запросов соответственно.

Следующие $k$ строк описывают чёрные дыры. Каждая содержит два целых числа $x,y$ ($1\le x\le n$, $1\le y\le m$) — координаты чёрной дыры. Никакие две чёрные дыры не находятся в одной клетке.

Последние $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: Иллюстрации к примеру.