Mały T zaplanował obszar wystawowy jako dwuwymiarową siatkę o rozmiarze $n \times n$. Najbardziej zewnętrzna część siatki jest otoczona pierścieniem ścian wystawowych, co oznacza, że wszystkie komórki o współrzędnych $0$ lub $n+1$ są komórkami ścian. Ponadto wewnątrz obszaru wystawowego rozproszonych jest $m$ komórek ścian, z których $i$-ta ($1 \le i \le m$) ma współrzędne $(x_i, y_i)$. Gwarantuje się, że wszystkie komórki ścian tworzą strukturę czterospójną.

Po przeprowadzeniu testów terenowych, mały T podsumował zasady zużycia czasu podczas poruszania się po siatce. W szczególności, między komórkami możliwe są dwa rodzaje ruchu:

• Ruch o jedną komórkę w kierunku pionowym lub poziomym, tj. z $(x, y)$ do $(x-1, y)$, $(x+1, y)$, $(x, y-1)$ lub $(x, y+1)$, wymaga zużycia $2$ jednostek czasu.
• Ruch o jedną komórkę po przekątnej, tj. z $(x, y)$ do $(x-1, y-1)$, $(x-1, y+1)$, $(x+1, y-1)$ lub $(x+1, y+1)$, wymaga zużycia $3$ jednostek czasu.

Oczywiście, komórka docelowa nie może być komórką ściany. Uwaga: podczas ruchu po przekątnej można przejść bezpośrednio przez szczelinę między dwiema ukośnie położonymi komórkami ścian. Na przykład, nawet jeśli $(x, y+1)$ oraz $(x+1, y)$ są komórkami ścian, nadal można zużyć $3$ jednostki czasu, aby przejść bezpośrednio z $(x, y)$ po przekątnej do $(x+1, y+1)$.

Mały S rozmieścił w obszarze wystawowym łącznie $q$ skarbów. Dla każdego $i$-tego ($1 \le i \le q$) skarbu ogłasza ona jego położenie $(tx_i, ty_i)$, podczas gdy Twoja pozycja w momencie ogłoszenia wynosi $(sx_i, sy_i)$. Aby jak najszybciej zdobyć każdy ze skarbów, musisz obliczyć minimalny czas potrzebny na przemieszczenie się z Twojej pozycji do pozycji skarbu.

Wejście

Pierwsza linia wejścia zawiera trzy liczby całkowite $n, m, q$ ($1 \le n \le 10^5, 1 \le m, q \le 3 \times 10^5$).

Następnie $m$ linii, z których $i$-ta ($1 \le i \le m$) zawiera dwie liczby całkowite $x_i, y_i$ ($1 \le x_i, y_i \le n$), oznaczające współrzędne $i$-tej komórki ściany. Gwarantuje się, że wszystkie $(x_i, y_i)$ są parami różne.

Następnie $q$ linii, z których $i$-ta ($1 \le i \le q$) zawiera cztery liczby całkowite $sx_i, sy_i, tx_i, ty_i$ ($1 \le sx_i, sy_i, tx_i, ty_i \le n$), oznaczające Twoją pozycję oraz pozycję skarbu w momencie ogłoszenia $i$-tego skarbu. Gwarantuje się, że $(sx_i, sy_i)$ oraz $(tx_i, ty_i)$ nie są komórkami ścian.

Wyjście

Wypisz $q$ linii, każda zawierająca jedną liczbę całkowitą będącą odpowiedzią. W szczególności, jeśli nie możesz dotrzeć do pozycji skarbu, wypisz $-1$.

Przykład

Wejście 1

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

Wyjście 1

2
16
11
10
11

Uwagi

Dla drugiego skarbu możesz poruszać się wzdłuż następującej ścieżki: $(1, 1) \to (1, 2) \to (2, 3) \to (3, 4) \to (4, 3) \to (4, 2) \to (3, 1)$, całkowity czas wynosi $2 + 3 + 3 + 3 + 2 + 3 = 16$.