첫째 줄에 실험실의 크기 , 바이러스의 종류 수 , 장애물의 수 이 공백으로 구분되어 주어집니다. (, , )

다음 개의 줄에 걸쳐 각 바이러스의 정보가 주어집니다. 번째 줄에는 번 바이러스의 초기 위치 행 , 열 와 세기 가 공백으로 구분되어 주어집니다. (, ) 는 부터 까지의 순열입니다.

다음 개의 줄에 걸쳐 장애물의 위치 , 가 공백으로 구분되어 주어집니다. ()

다음 줄에 벽 설치 명령의 수 가 주어집니다. ()

다음 개의 줄에 걸쳐 벽 설치 명령 정보가 주어집니다. 각 줄에는 네 개의 정보 , , , 가 공백으로 구분되어 주어집니다. 이는 번째 턴의 1단계에서 기준 칸 (, )의 방향 모서리에 벽이 설치됨을 의미합니다. 는 (상), (하), (좌), (우) 중 하나입니다. ()

명령은 턴 번호 를 기준으로 오름차순(비감소 순서)으로 주어지며, 같은 모서리에 벽이 중복 설치되는 경우는 없습니다.

모든 바이러스의 초기 위치와 장애물 위치는 서로 다르며, 격자 경계 밖을 향하는 벽 설치 명령은 주어지지 않습니다. 또한, 시작 시점에 모든 비-장애물 칸은 적어도 하나의 바이러스 시작 위치와 연결되어 있음이 보장됩니다.

#535. 바이러스 전쟁

Input

Output

Sample

Input 1

Output 1

Time Limit

Memory Limit

Source