Fladdermusen (박쥐 우편배달)

Båtman은 다른 많은 박쥐들과 함께 큰 동굴에 산다. Båtman은 방금 공식 박쥐 우편배달부가 되었기 때문에, 동굴 안의 특정 지점들 사이에서 편지를 배달해야 한다.

동굴은 2차원 직사각형이며, 높이는 $H$ cm, 너비는 $W$ cm이다. 동굴에는 총 $N$개의 석순과 종유석이 있다. 석순은 동굴 바닥에서 위로 자라는 수직 돌기이고, 종유석은 동굴 천장에서 아래로 늘어진 수직 돌기이다. 둘 다 무한히 얇지만 비행을 막는다.

Båtman은 위, 아래, 왼쪽, 오른쪽으로만 날 수 있고, 이 네 방향은 언제든지 바꿀 수 있다. 여기서 관심 있는 거리는 맨해튼 거리이다. 예를 들어 Båtman은 오른쪽으로 0.4 cm 날아간 뒤 위쪽으로 4.3 cm 날 수 있다.

첫 번째 예제의 그림이다. 점선은 첫 번째 편지를 배달하는 길이 12의 최단 경로 중 하나를 보여준다.

Båtman에게는 배달할 편지 $Q$개의 목록이 있다. 각 편지는 동굴 안의 한 지점에서 받아 다른 지점으로 전달해야 한다. 각 편지마다 시작점에서 도착점까지 Båtman이 날아야 하는 최단 거리를 구하라.

첫 줄에 네 정수 $N$, $Q$, $H$, $W$가 주어진다.

• $1 \le N \le 200\,000$: 석순과 종유석의 총 개수이다.
• $1 \le Q \le 200\,000$: 배달할 편지의 수이다.
• $1 \le H, W \le 10^9$: 동굴의 높이와 너비이다.

다음 $N$개의 줄은 다음 중 하나의 형식이다.

• 1 x y: 점 $(x, 0)$에서 점 $(x, y)$까지 자라는 석순이 있다.
• 2 x y: 점 $(x, H)$에서 점 $(x, y)$까지 늘어진 종유석이 있다.

천장에서 바닥까지 닿는 석순이나 종유석은 없으며, 모두 동굴 안에 있다. 즉 $1 \le x_i < W$, $1 \le y_i < H$이다.

다음 $Q$개의 줄에는 네 정수 $x_1, y_1, x_2, y_2$ ($1 \le x_1, x_2 < W$, $1 \le y_1, y_2 < H$)가 주어지며, 점 $(x_1, y_1)$에서 점 $(x_2, y_2)$까지 편지를 배달한다는 뜻이다.

입력의 모든 $x$ 좌표는 서로 다르다고 보장된다.

$Q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 편지를 배달하기 위해 Båtman이 날아야 하는 최소 거리를 정수로 출력한다.