제한효소 지도

문제

어떤 연구자가 유전 물질로 계산하는 장치를 만들고 있다. 장치 안의 DNA가 변이로 망가진 것 같아서, 어느 부분이 상했는지 찾으려고 제한효소 지도를 만들기로 했다.

제한효소는 특정한 짧은 염기 서열이 나타나는 자리에서 DNA를 자르는 효소다. 예를 들어 SmaI은 CCCGGG를 인식해 그 한가운데를 자르므로, ACACAGGGCCCTCAGGTGC를 ACACAGGG과 CCCTCAGGTGC 두 조각으로 나눈다. 제한효소는 종류가 수천 가지이고, 저마다 인식하는 서열이 다르다.

제한효소 지도는 어떤 효소가 DNA의 어느 자리를 자르는지 적어 놓은 지도다. 아래 그림이 그 예다. 그림의 DNA는 원형이다. 즉 서열의 왼쪽 끝과 오른쪽 끝이 이어져 있다.

제한효소 지도

그림 1: 제한효소 지도

지도를 눈으로 읽을 수는 없지만, 조각의 길이를 정확히 재는 장치는 있다. 실험은 이렇게 한다. 먼저 DNA 사본 수천 개를 효소 A로 자르고 생긴 조각의 길이를 잰다. 다음으로 다른 사본 수천 개를 효소 B로 자르고 같은 방식으로 길이를 잰다. 마지막으로 A와 B를 함께 넣어 자른 조각의 길이도 잰다. 조각의 길이가 지도를 바로 알려주지는 않지만, 세 실험의 결과를 모으면 지도를 복원할 수 있는 경우가 많다.

A가 SmaI이고 B가 EcoRI인 경우를 보자.

A로, B로, A와 B로 함께 자른 결과

그림 2: A로, B로, 그리고 A와 B로 함께 자른 결과

DNA가 원형이라는 점을 기억하자. 길이가 20인 이 DNA를 A로만 자르면 12와 8을 얻는다. B로만 자르면 EcoRI 자리가 하나뿐이라 조각도 하나여서 20을 얻는다. A와 B를 함께 쓰면 길이가 8, 6, 6인 조각 세 개가 생긴다. 그런데 장치는 어떤 길이의 조각이 들어 있는지만 알려주고, 그 길이의 조각이 몇 개인지는 알려주지 않는다. 길이가 같은 조각이 여럿이면 값 하나만 보고되므로, 마지막 실험에서는 8, 6, 6이 아니라 8과 6 두 값만 얻는다.

정리하면 이렇다. DNA는 길이가 $L$ 인 원이고, 자리에는 $0$ 부터 $L-1$ 까지 번호가 붙어 있다. 어떤 효소로 잘랐을 때 생기는 조각의 길이는 원을 따라 이웃한 두 자르는 자리 사이의 거리다. 자르는 자리가 하나뿐이면 조각도 하나이고 길이는 $L$ 이다. 효소마다 자르는 자리가 적어도 하나 있고, 효소 농도가 충분히 높아 인식 자리는 빠짐없이 잘린다.

효소 A로 자른 조각의 길이, 효소 B로 자른 조각의 길이, 효소 A와 B로 함께 자른 조각의 길이가 주어질 때 제한효소 지도를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 케이스는 네 줄이다.

첫 줄에는 DNA의 길이 $L$ 이 주어진다. ( $2 \le L \le 20$ )

둘째 줄에는 효소 A로 잘라 얻은 조각의 길이가 주어진다. 줄의 첫 정수는 뒤에 나오는 값의 개수이고, 나머지 정수가 각 값이다. 값은 공백 하나로 구분하며 정렬되어 있지 않다. 길이가 같은 조각이 여럿이어도 그 값은 한 번만 나온다.

셋째 줄과 넷째 줄에는 효소 B로 자른 결과와 효소 A와 B로 함께 자른 결과가 같은 형식으로 주어진다.

효소 A와 B가 인식하는 서열은 서로 달라서 한 자리를 두 효소가 같이 자르는 일은 없다. 한 효소가 잘라서 다른 효소의 인식 서열이 깨지는 일도 없다. 모든 케이스에는 주어진 조건을 만족하는 지도가 적어도 하나 있다.

마지막 케이스 다음 줄에는 0 하나만 주어진다.

출력

각 케이스마다 제한효소 지도를 출력한다.

첫 줄에는 자르는 자리의 개수 $n$ 을 출력한다. 이어지는 $n$ 개의 줄에는 자르는 자리를 하나씩 출력한다. 각 줄에는 자리의 위치와 그 자리를 자르는 효소의 이름을 공백 하나로 구분해 쓰고, 다른 문자는 쓰지 않는다. 위치는 $0$ 이상 $L-1$ 이하의 정수이고, 자리는 위치의 오름차순으로 출력한다.

조건을 만족하는 지도가 여럿이면 자르는 자리의 개수가 가장 적은 것을 고른다. 그러고도 여럿이면 사전순으로 가장 앞서는 지도 하나만 출력한다. 두 지도는 (위치, 효소) 쌍의 나열을 앞에서부터 견주어 비교한다. 위치가 작은 쪽이 앞서고, 위치가 같으면 A가 B보다 앞선다. DNA가 원형이라 지도를 통째로 돌려도 조건을 그대로 만족하므로, 이 규칙으로 고른 지도에서는 언제나 위치 0을 A가 자른다.

케이스와 케이스 사이에는 빈 줄을 하나 넣는다.