폴더 정리 (large)

문제

이름이 main 폴더 안에 여러가지 파일과 폴더가 존재한다.

main
 ├─ FolderA
 │    ├─ File1
 │    └─ File2
 └─ FolderB
       ├─ FolderC
       │   ├─ File4
       │   └─ File5
       ├─ File1
       └─ File3

위 구조는 main 폴더의 하위 구조를 계층적으로 표시한 것이다. FolderA, FolderB, FolderC는 폴더이고 File1, File2, File3은 파일이다. 파일 이름이 같은 경우는 내용이 완전 동일한 파일이다.

한 폴더 안에 같은 이름을 가진 파일이 두 개 이상 존재할 수 없다.

main 폴더의 하위 디렉토리에 같은 이름의 폴더가 두 개 이상 존재할 수 없다.

폴더 또는 파일을 옮겨 main 폴더를 정리하려고 한다.

예를 들어, FolderB 폴더 하위에 있는 두 개의 파일 File1, File3과 하나의 폴더 FolderC를 FolderA 폴더 하위에 옮기려고 한다.

File1 파일은 FolderA 폴더 안에 동일한 파일이 이미 존재하므로 덮어쓴다. File3은 동일한 파일이 없으므로 그대로 옮긴다. FolderC 폴더도 동일한 폴더가 없으므로 FolderA 폴더 하위에 옮긴다. FolderB 폴더 하위에 있는 폴더와 파일을 다 옮겼으므로 FolderB는 삭제한다.

아래는 FolderB 폴더를 FolderA 폴더 안에 옮긴 후 main 폴더의 하위 구조를 계층적으로 표시한 것이다.

main
 └─ FolderA
      ├─ FolderC
      │ ├─ File4
      │ └─ File5
      ├─ File1
      ├─ File2
      └─ File3

이러한 과정을 통해 폴더를 정리하려고 한다. 폴더 정리 후 쿼리를 통하여 파일의 정보를 확인하려고 한다.

입력

첫 번째 줄에는 main 폴더 안에 있는 폴더의 총 개수 $N$ 과 파일의 총 개수 $M$ 이 공백으로 구분되어 주어진다.

두 번째 줄부터 $N + M + 1$ 번째까지 상위 폴더의 이름 $P$ , 폴더 또는 파일의 이름 $F$ , 폴더인지 아닌지 알려주는 $C$ 가 공백으로 구분되어 주어진다.

$C$ 의 값은 $F$ 가 폴더라면 1, 파일이라면 0으로 주어진다.

$N + M + 2$ 번째 줄에는 옮기는 횟수 $K$ 가 주어진다.

그 다음 줄부터 총 $K$ 줄에 걸쳐 폴더 경로 $A$ 와 폴더 경로 $B$ 가 공백으로 구분되어 주어진다.

옮기는 행위는 입력 순서대로 수행이 되어야 한다.

$A$ 하위에 있는 파일과 폴더들을 $B$ 하위에 옮기는 것이다. 이때, $A$ 는 $B$ 의 상위 폴더가 아님을 보장한다.

그 다음 줄에는 쿼리의 개수 $Q$ 가 주어진다.

그 다음 줄부터 $Q$ 개의 쿼리가 주어진다. 쿼리마다 main으로부터 폴더의 경로 정보가 들어온다. 예를 들어 main 폴더 안에 FolderB에 대한 쿼리가 들어온다면, FolderB의 경로인 main/FolderB로 주어진다. 반드시 폴더가 존재하는 경로로 주어짐을 보장한다.

출력

쿼리 순서대로 한 줄씩 폴더 하위에 있는 파일의 종류의 개수와 파일의 총 개수를 출력한다.

파일의 종류의 개수는 같은 파일이 여러개 있을 경우 하나로 계산한다. 파일의 총 개수는 같은 파일이 있더라도 하나로 계산하지 않는다.

예를 들어 이름이 File1 파일이 5개가 있을 경우 파일의 종류는 1 가지이고 파일의 총 개수는 5개이다.

제한

$1 \le N \le 1,000$
$1 \le M \le 1,000$
$0 \le K \le 1,000$
$1 \le |P| \le 10$
$1 \le |F| \le 10$
$0 \le C \le 1$
$1 \le Q \le 1,000$
$P$ 와 $F$ 는 영어 알파벳 대소문자, 숫자로만 이루어져 있다.