1367번 - 타브 악보

Tablature (타브 악보)는 프렛이 있는 현악기를 연주할 때, 많이 쓰는 악보이다. 각 줄은 줄을 의미하고, 줄에 쓰여 있는 숫자는 그 줄을 연주 하기 위해서 눌러야 하는 프렛의 번호를 의미한다.

------------
-3----------
-------0----
---2--------
-------0----
------------

가장 윗 줄은 첫 번째 줄이다. 그 밑은 둘째 줄이고, 그런 식으로 계속 된다.  타브 악보는 왼쪽부터 오른쪽으로 읽는다. i번째 열은 시간 i에 연주하는 음이다. 위의 예제에서 0번 열은 아무 숫자가 안 쓰여 있다. 따라서 아무 음도 연주하지 않는다. 시간 1에는 2번 줄의 3번 프렛을 잡고 그 줄을 연주한다. 시간 3에는 4번 줄의 2번 프렛을 잡고 그 줄을 연주하며, 마지막으로 시간 7에 두 개의 음표를 코드로 동시에 연주해야 한다. 숫자 0은 프렛을 누르지 않고 연주하는 것을 의미한다. 이것을 열린 줄이라고 말하며, 위의 예에서 셋째 줄, 다섯째 줄을 동시에 연주하면 된다.

모든 열린 줄은 다른 음정을 가지고 있다. 예를 들어, 보통 기타 튜닝에선 첫 번째 줄의 음정이 두 번째 줄보다 5 반음 높다. 그리고, N번 프렛을 잡고 연주했을 때, 그 줄의 열린 음의 음정보다 N반음 높은 음이 연주된다.

악기 A (예를 들어 기타)로 연주 하는 타브 악보가 주어진다. 하지만, 이것을 악기 B (예를 들어 만돌린)로 연주하려고 한다. 그리고 지금 현재 악기 A와 악기 B의 열린 음의 음정을 모두 알고 있다.

모든 악기는 35프렛을 가지고 있다. 따라서 타브 악보에 쓰여 있는 숫자는 0~9 그리고, A~Z이다. A~Z는 10~35에 해당한다.

이 문제는 원래 타브 악보를 악기 B를 위한 타브 악보로 바꾸는 프로그램을 작성하는 것이다. 다른 악기는 서로 다른 음역대를 가지고 있기 때문에, 원래 노래를 조옮김해서 악보로 작성해야 한다. 따라서 이것 때문에 D가 주어진다. 따라서, 악보 B를 위한 타브 악보를 만들 때, 모든 음을 D만큼 반음을 올려서 작성해야 한다. D가 음수일 때는 D만큼 반음을 내리는 것이다.

가끔 악보를 바꾸는데 여러 가지 방법이 있을 수도 있다. 이때는 가장 높은 열린 음으로 연주할 수 있는 줄을 선택해야 한다. 만약 그런 줄이 여러 개 있을 때는, 가장 아래에 있는 줄을 선택한다. (줄은 위에서부터 아래까지 적혀있다.)

코드는 위와 같이 한 음 한 음에 대한 규칙과 같은 규칙을 적용하면 된다. 하지만, 반드시 가장 높은음, 그 다음으로 높은음, 이와 같이 순서를 정해서 악보에 적어야 한다. 각각의 줄은 단 하나의 음만 낼 수 있다. 따라서 코드에 있는 음을 악보에 적을 때는, 사용 안 한 줄만 고려하면 된다. 만약 그 코드를 칠 수 없을 때는, 그 열 전체를 x로 표시한다.

첫째 줄에 타브 악보의 줄의 개수 N과 열의 개수 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 M개의 문자가 주어진다. 타브 악보가 N개의 줄이 있기 때문에, 악기 A는 줄이 A개이다. 따라서 그 다음 줄에는 1번 줄부터 그 줄의 음정이 주어진다. 음정은 절댓값이 50보다 작거나 같은 정수이다. 그 다음 줄에는 악기 B의 줄의 개수 K가 주어진다. 그 다음 줄에는 악기 B의 1번 줄부터 그 줄의 음정이 주어진다. 마지막 줄에는 D가 주어진다. D는 절댓값이 50보다 작거나 같은 정수이다.

K개의 줄에 정답을 출력한다.