젖은 바닥 타일

앨리스는 비가 거의 오지 않기로 유명한 마을 노레이니아에서 건설 회사를 운영한다. 이 마을에는 1년에 며칠만 비가 내려서, 주민 상당수는 물이 새어 바닥을 망가뜨릴 때까지 지붕 수리를 미룬다. 노레이니아의 바닥 타일은 보기에는 훌륭하지만 물에 약하다. 한 번 젖은 타일은 못 쓰게 되어 교체해야 한다. 비 오는 날마다 앨리스에게 전화가 쏟아지고, 앨리스는 집마다 작업팀이 교체용 타일을 몇 장 들고 가야 하는지 알아야 한다.

집의 바닥은 가로 $X$장, 세로 $Y$장인 정사각형 타일 격자다. 물은 특정 타일 위에 있는 누수 지점에서 떨어진다. 1분이 지나면 각 누수 지점 바로 아래 타일이 젖는다. 그 뒤로 1분이 지날 때마다, 이미 젖은 타일과 변을 맞대고 있는 마른 타일이 모두 젖는다.

벽은 물을 막는다. 집 전체를 둘러싸는 바깥벽 네 개가 항상 있어서 물은 격자 밖으로 나가지 않는다. 집 안에는 내부 벽이 있을 수도 있다. 내부 벽 하나는 서로 이어진 직선 구간의 타일을 차지하며, 축에 평행하거나 두 축과 45도를 이룬다. 대각선 벽은 모서리끼리만 맞닿는 타일의 나열이다. 물은 벽이 놓인 타일에 들어가지 못하고, 변을 맞댄 타일 사이로만 퍼진다. 벽끼리 교차할 수 있고, 누수 지점이 벽 위에 있는 경우는 없다.

그림 1은 흰색 글자 L로 표시한 누수 지점 세 곳에서 처음 5분 동안 번진 피해를 회색으로 보여 준다. 숫자 2가 적힌 타일은 2분째에 젖고, 3이 적힌 타일은 3분째에 젖는다. 나머지 숫자도 마찬가지다. 검은 타일은 물을 막는 내부 벽이다. 5분이 지나면 타일 75장이 젖는다.

그림 1. 젖은 타일 75장

격자의 크기, 누수 지점, 내부 벽, 그리고 작업팀이 누수를 막기까지 지나는 시간 $T$분이 주어질 때 젖은 타일이 몇 장인지 세어라.

그림 2부터 그림 4까지는 첫 번째 예제의 두 번째, 세 번째, 네 번째 집을 보여 준다.

그림 2. 젖은 타일 17장

그림 3. 젖은 타일 4장

그림 4. 젖은 타일 94장

입력은 집 하나 이상을 설명한다.

각 집은 정수 다섯 개 $X$, $Y$, $T$, $L$, $W$가 적힌 줄로 시작한다. $X$와 $Y$는 격자의 크기이고, $1 \le X \le 1000$, $1 \le Y \le 1000$이다. 좌표는 1부터 시작하므로 타일은 $1 \le x \le X$, $1 \le y \le Y$인 순서쌍 $(x, y)$로 나타낸다. $T$는 작업팀이 도착해 누수를 막기까지 지나는 시간(분)이고, $1 \le T \le 200000$이다. $L$은 누수 지점의 개수이고, $1 \le L \le 100$이다. $W$는 내부 벽의 개수이고, $0 \le W \le 100$이다.

이어지는 정수 $2L$개는 한 줄 또는 여러 줄에 걸쳐 주어지며, 서로 다른 누수 지점 $L$개의 좌표 $(x, y)$다.

$W > 0$이면 그다음 정수 $4W$개가 한 줄 또는 여러 줄에 걸쳐 내부 벽을 설명한다. 벽 하나는 정수 네 개 $x_1$, $y_1$, $x_2$, $y_2$로 주어지고, 이는 벽 양 끝의 좌표다. 벽은 $(x_1, y_1)$에서 $(x_2, y_2)$까지 이어지는 직선 구간의 타일을 모두 차지한다. 이 구간은 축에 평행하거나 45도 방향이다. 두 끝점이 같으면 벽은 그 타일 한 장만 차지한다.

정수 -1 하나만 적힌 줄이 나오면 입력이 끝난다.

집마다 $T$분이 지난 뒤 젖은 타일이 몇 장인지, 입력에 나온 순서대로 한 줄에 하나씩 출력한다.