PreQueL

PreQueL이라는 아주 단순한 DBMS가 있다. 이 DBMS에서 유일하게 허용되는 열(column) 타입은 CHAR(1), 즉 문자 하나이며, 그 값은 영어 대문자 'A'-'Z'로만 제한된다. 하나의 테이블은 1개에서 9개까지의 열을 가질 수 있고, 열은 1번부터 9번까지 번호로 구분한다. 테이블의 이름은 영어 소문자 'a'-'z'이며, 입력에서 첫 번째 테이블이 'a', 두 번째가 'b', … 순서로 이름이 붙는다.

질의(query)는 먼저 모든 테이블을 조인(join, 카테시안 곱)한 뒤, 주어진 모든 조건을 만족하는 행만 남긴다. 각 조건은 다음 두 형태 중 하나이다.

• <열>=<값> 형태. 예: a2=A — 해당 열의 값이 주어진 대문자와 같다.
• <열1>=<열2> 형태. 예: b1=c4 — 두 열의 값이 서로 같다.

열 참조는 테이블 문자 뒤에 열 번호를 붙여 나타낸다. 예를 들어 a2는 테이블 a의 2번 열을 뜻한다. 모든 조건은 AND로 연결된 것처럼 동시에 성립해야 한다.

주어진 테이블과 조건에 대해, 조인 결과 중 모든 조건을 만족하는 행을 출력하는 PreQueL 처리기를 작성하라. 출력하는 각 행은 테이블 순서(a, 그다음 b, …)대로 각 테이블에서 고른 행 하나씩을 이어 붙인 문자열이다. 중복되는 행도 그대로 남긴다. 결과 행은 사전순(오름차순)으로 정렬하여 출력한다.

첫째 줄에 두 정수 $T$와 $D$가 주어진다. 각각 테이블의 수와 조건의 수이다.

이어서 $T$개의 테이블이 주어진다. 각 테이블은 먼저 두 정수 $RN$과 $CN$(행의 수와 열의 수)이 적힌 줄로 시작하고, 그다음 정확히 $CN$개의 대문자로 이루어진 $RN$개의 줄이 이어진다. 테이블에는 주어진 순서대로 a, b, … 이름이 붙는다.

모든 테이블 다음에는 $D$개의 줄에 조건이 한 줄에 하나씩, 위에서 설명한 두 형태 중 하나로 주어진다.

모든 조건을 만족하는 결과 행을 한 줄에 하나씩, 사전순(오름차순)으로 정렬하여 출력한다. 어떤 질의도 1000개를 넘는 행을 만들지 않는다. 조건을 만족하는 행이 하나도 없으면 아무것도 출력하지 않는다.

• $1 \le T \le 26$
• $1 \le D \le 50$
• $1 \le CN \le 9$
• $1 \le RN \le 1000$