나무 개미 군집

정수 숲에는 큰 나무 개미 군집이 있다. 정수 숲은 정수 좌표를 가진 모든 점마다 나무가 한 그루씩 있는 무한히 넓은 2차원 평면이다. 군집은 정수 좌표의 점들로 이루어지고, 인접한 일부 점 쌍이 통로로 연결되어 있다. 두 점 $(x_1, y_1)$과 $(x_2, y_2)$는 $|x_1-x_2|+|y_1-y_2| = 1$이면 인접한다. 따라서 군집은 그래프를 이룬다. 나무 개미의 특징은 나무에 살 뿐 아니라, 군집 자체가 트리라는 점이다. 즉 군집은 연결되어 있고 통로는 정확히 $N-1$개이며, 여기서 $N$은 군집을 이루는 점의 개수다.

개미 연구자 안토니는 이 군집으로 실험을 하려고 한다. 직사각형 영역을 나머지 군집과 떼어 놓았을 때 무슨 일이 일어나는지 알고 싶어 한다. 그의 가설은 그래프의 서로 다른 연결 요소에 속한 개미들이 각자 자기 군집을 이루고 다른 군집과 전쟁을 시작한다는 것이다. 직사각형은 $x_1 \leq x \leq x_2$이고 $y_1 \leq y \leq y_2$를 만족하는 모든 정수 점 $(x, y)$의 집합이며, $x_1, y_1, x_2, y_2$는 주어진 정수다.

안토니는 아직 어떤 직사각형을 쓸지 정하지 않았지만 여러 아이디어가 있다. 각 직사각형에 대해, 영역을 떼어 놓았을 때 직사각형 안에 연결 요소가 몇 개 생기는지 구하라. 두 점은 직사각형 밖의 점을 거치지 않고 통로를 따라 이동할 수 있으면 같은 연결 요소에 속한다. 안토니는 떼어 낸 직사각형 안의 요소 개수에만 관심이 있고, 나머지 군집은 신경 쓰지 않는다.

첫 줄에는 군집이 있는 영역의 크기를 나타내는 정수 $A$와 $B$($1 \leq A, B \leq 150\,000$)가 주어진다.

둘째 줄에는 군집을 이루는 점의 개수 $N$과 직사각형의 개수 $Q$($2 \leq N \leq 150\,000$, $1 \leq Q \leq 150\,000$)가 주어진다.

다음 $N-1$개 줄은 통로 정보다. 통로는 두 종류가 있다.

1. h $x$ $y$: 점 $(x, y)$와 $(x+1, y)$가 통로로 연결되어 있다 ($1 \leq x \leq A-1$, $1 \leq y \leq B$).
2. v $x$ $y$: 점 $(x, y)$와 $(x, y+1)$이 통로로 연결되어 있다 ($1 \leq x \leq A$, $1 \leq y \leq B-1$).

다음 $Q$개 줄은 직사각형을 나타낸다. 각 줄에는 정수 $x_1$, $y_1$, $x_2$, $y_2$($1 \leq x_1 \leq x_2 \leq A$, $1 \leq y_1 \leq y_2 \leq B$)가 있다. 직사각형은 $x_1 \leq x \leq x_2$이고 $y_1 \leq y \leq y_2$를 만족하는 모든 점 $(x, y)$다.

군집의 모든 좌표 $(x, y)$는 $1 \leq x \leq A$, $1 \leq y \leq B$를 만족한다. 점과 통로가 이루는 그래프가 트리임이 보장된다.

$Q$개의 줄을 출력한다. 각 줄은 직사각형 하나에 대응하며, 그 직사각형을 떼어 놓았을 때 내부에 생기는 연결 요소의 개수를 적는다.

• $1 \leq A, B \leq 150\,000$
• $2 \leq N \leq 150\,000$
• $1 \leq Q \leq 150\,000$