진주 자수

옛날부터 해안 마을의 자수공들은 같은 크기의 격자로 이루어진 직사각형 수건 위에 진주로 자수를 놓았다. 자수는 수건의 한 격자 중앙에 진주를 꿰매는 것에서 시작했다. 새 진주를 꿰매려면 자수공은 이미 진주가 있는 격자에서 가로 또는 세로로 인접한 빈 격자로 실을 꿰었다. 새 진주는 실의 끝 격자 중앙에 꿰매졌다. 이 과정은 진주가 다 떨어질 때까지 반복되었다.

이런 축제용 수건 하나가 박물관에 있다. 안타깝게도 무늬의 일부가 손실되었지만 수건에 대한 설명은 남아 있다. 박물관 측은 수건의 직사각형 조각 하나를 복원하려고 하지만 어떤 조각인지는 아직 정하지 않았다. 조각 복원 비용은 그 조각에 들어가는 무늬의 연결 부분 개수에 따라 달라진다. 무늬의 한 부분이 연결되었다는 것은, 그 부분의 어떤 진주에서든 조각 경계를 벗어나지 않고 실을 따라 그 부분의 다른 어떤 진주로도 갈 수 있다는 뜻이다. 박물관 측은 실을 따라 서로 오갈 수 있는 두 진주는 항상 같은 연결 부분에 속한다고 본다.

주어진 각 조각에 대해 무늬의 연결 부분 개수를 계산하는 프로그램을 작성해야 한다.

첫째 줄에는 수건의 가로, 세로 격자 크기 $a$, $b$가 주어진다.

둘째 줄에는 무늬에 있는 진주 개수 $n$과 조각 개수 $q$가 주어진다.

다음 $(n - 1)$개 줄에는 실에 대한 설명이 주어진다. 각 실은 다음 중 하나이다.

• h $x$ $y$: 좌표 $(x, y)$와 $(x + 1, y)$ 격자에 있는 진주가 가로 실로 연결되어 있다 ($1 \leq x \leq a - 1$; $1 \leq y \leq b$).
• 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$).

출력은 $q$개 줄로 이루어진다. $i$번째 줄에는 $i$번째 조각에 있는 무늬의 연결 부분 개수를 출력한다.

예제에 대한 설명.

$x_1 = 1$, $y_1 = 1$, $x_2 = 4$, $y_2 = 3$	$x_1 = 3$, $y_1 = 2$, $x_2 = 4$, $y_2 = 3$	$x_1 = 3$, $y_1 = 1$, $x_2 = 3$, $y_2 = 1$	$x_1 = 1$, $y_1 = 2$, $x_2 = 3$, $y_2 = 3$