박쥐

박쥐 보트만은 많은 다른 박쥐와 함께 커다란 동굴에 산다. 보트만은 최근 공식 박쥐 우편배달부라는 새 직업을 얻었다. 이는 보트만이 동굴 안의 특정 지점들 사이에서 편지를 배달해야 한다는 뜻이다.

동굴은 높이가 $H$cm이고 너비가 $W$cm인 이차원 직사각형이다. 또한 동굴 안에는 총 $N$개의 석순과 종유석이 있다. 석순은 동굴 바닥에서 위로 자라는 수직 동굴 생성물이고, 종유석은 동굴 천장에서 아래로 자라는 수직 동굴 생성물이다. 동굴의 석순과 종유석은 모두 무한히 얇지만, 이를 통과해 날아갈 수는 없다.

보트만은 배달해야 하는 편지 $Q$개의 목록을 받았다. 각 편지는 동굴 안의 한 지점에서 수거하여 다른 지점으로 배달해야 한다. 이제 보트만은 각 편지를 출발점에서 도착점까지 배달하려면 얼마나 멀리 날아야 하는지 궁금해하며, 이를 계산하는 데 도움을 요청한다.

박쥐는 보트만을 포함하여 수직 위쪽, 수직 아래쪽, 수평 왼쪽, 수평 오른쪽으로만 날 수 있지만, 언제든지 이 네 방향 사이에서 방향을 바꿀 수 있다. (독자는 이 문제에서 Manhattan 거리를 다룬다는 것을 눈치챘을 수도 있다.) 따라서 보트만은 예를 들어 오른쪽으로 $0.4$cm 날아간 다음, 방향을 바꾸어 위쪽으로 $4.3$cm 날아갈 수 있다.

첫 번째 예제 테스트 케이스의 그림이다. 점선은 첫 번째 편지를 배달하기 위한 길이 12의 가능한 최단 비행 경로 하나를 나타낸다.

점수

여러 테스트 케이스 그룹으로 여러분의 풀이를 평가한다. 한 그룹에서 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

$1$ |$15$| $N,Q\le 100$ 및 $H,W\le 500$

$2$ |$20$| $N,Q \le 2000$ 및 $H,W\le 2\cdot 10^6$

$3$ |$25$| 종유석은 최대 15개이다

$4$ |$40$| 추가 제한이 없다

첫째 줄에 네 정수 $N,Q,H,W$ ($1 \leq N, Q \leq 2 \cdot 10^5, 1 \leq H,W \leq 10^9$)가 주어진다. 그다음 $N$개의 줄이 이어지며, 각 줄은 다음 형식 중 하나이다.

• $1\enspace x\enspace y$, 이는 석순이 점 $(x,0)$에서 점 $(x,y)$까지 위로 자란다는 뜻이다.

• $2\enspace x\enspace y$, 이는 종유석이 점 $(x,H)$에서 점 $(x,y)$까지 아래로 자란다는 뜻이다.

어떤 석순이나 종유석도 천장에서 바닥까지 완전히 이어지지 않으며, 모든 석순과 종유석은 동굴 내부에 완전히 들어 있다. 즉, $1\le x_{i} < W$ 및 $1\le y_{i} < H$이다.

그다음 네 정수 $x_{1},y_{1},x_{2},y_{2}$ ($1\le x_{1},x_{2} < W$, $1\le y_{1},y_{2}< H$)가 주어지는 $Q$개의 줄이 이어지며, 이는 편지 하나를 점 $(x_{1},y_{1})$에서 점 $(x_{2},y_{2})$까지 배달해야 함을 나타낸다.

입력의 모든 $x$-좌표가 서로 다름이 보장된다.

프로그램은 각 편지마다 한 줄씩, 총 $Q$개의 줄을 출력해야 한다. $i$번째 줄에는 보트만이 $i$번째 편지를 배달하기 위해 날아야 하는 최소 거리를 나타내는 정수 하나를 출력한다.