제비뽑기로 쓰는 방법 중에는 사다리타기가 있다. 사다리의 중간 부분을 가리고 , 각 자 윗 부분을 선택한 뒤 사다리를 따라 내려가면 사다리의 윗 부분과 아랫부분은 일대일로 만나게 된다.

예를 들어, 왼쪽과 같은 사다리가 있어 윗 부분에 1,2,3,4 라고 쓰고, 아랫 부분에 A,B,C,D 라 쓰고 1 에서 부터 사다리를 따라 내려가면 오른쪽 그림과 같이 D 와 만나게 된다.

사다리의 세로선의 개수 N 과 사다리의 모양이 주어질 때 윗쪽 어느부분이 아랫쪽 어느 부분과 만나지는 결정하는 프로그램을 작성하시오.

입력 형식

출력 형식

사다리의 왼쪽부분에는 차례대로 1 부터 N 까지 번호가 붙고, 사다리의 아랫쪽 부분에는 A 부터 영문자 대문자의 이름이 붙는다고 할 때, 각각의 번호가 어느 문자와 대응하는지를 차례로 한 줄에 한 쌍식 출력한다.

입출력 예

입력

4 5
1 
2
3
1
2

출력

1 D
2 C
3 A
4 B