K번째 최단 경로

문제

Bob와 Alice는 그래프에서 최단 경로를 찾는 게임을 즐겨한다.

동생 Bob은 아직 어려서 실수를 많이 하기 때문에 Alice는 Bob가 연습할 수 있도록 다음과 같은 문제를 제시했다.

먼저, 길이를 나타내는 정수 $L$ 을 정한 후, $0$ 부터 $10^L-1$ 까지의 총 $10^L$ 개의 양의 정수를 이용하여 아래 규칙에 따라 그래프를 만든다:

노드: $0$ 부터 $10^L-1$ 까지의 각 정수는 그래프의 고유한 노드를 나타낸다. 이 때, 각 정수는 선행하는 $0$ 을 붙여 반드시 길이가 $L$ 이 되도록 만든다. 예를 들어 $L = 2$ 라면 $00, 01, 02, \dots, 98, 99$ 로 총 $100$ 개의 노드를 만들게 된다.
간선: 두 정점 $(x, y)$ 사이에 간선이 있으려면 $x$ 와 $y$ 의 $1$ 의 자리, $10$ 의 자리, ..., $10^{L-1}$ 의 자리를 비교했을 때 딱 한 곳만 달라야 하고 그 차이가 정확히 $1$ 이 되어야 한다. 예를 들어 $L = 2$ 인 경우, $00$ 과 $01$ , $01$ 과 $11$ , $27$ 과 $37$ , $36$ 과 $46$ 사이에는 간선이 있고, $00$ 과 $02$ , $01$ 과 $10$ , $36$ 과 $47$ 혹은 $46$ 과 $57$ 사이에는 간선이 없다.

아래 그림은 $L = 2$ 인 경우 그래프의 일부를 보여준다.

위 규칙에 따라 그래프를 만든 뒤, Alice는 Bob에게 두 정점 $x$ 와 $y$ 사이의 최단 경로 중 사전 순으로 정렬했을 시 $K$ 번째에 해당하는 최단 경로를 찾아보라고 했다. 예를 들어 $L = 2$ , $x = 37$ , $y = 55$ 인 경우를 생각해보자. 이 경우 두 노드 사이의 최단 거리는 $4$ 이며, 아래와 같이 총 여섯 개의 최단 경로가 존재한다. 만약 $K = 3$ 이라면 정답은 $3$ 번째 최단 경로인 $37 - 36 - 46 - 56 - 55$ 가 된다.

$37 - 36 - 35 - 45 - 55$
$37 - 36 - 46 - 45 - 55$ 위의 경로와 비교하면 $3$ 번째 노드인 $35$ 가 $46$ 보다 사전 순으로 앞선다.
$37 - 36 - 46 - 56 - 55$ 위의 경로와 비교하면 $4$ 번째 노드인 $45$ 가 $56$ 보다 사전 순으로 앞선다.
$37 - 47 - 46 - 45 - 55$ 위의 경로와 비교하면 $2$ 번째 노드인 $36$ 이 $47$ 보다 사전 순으로 앞선다.
$37 - 47 - 46 - 56 - 55$ 위의 경로와 비교하면 $4$ 번째 노드인 $45$ 가 $56$ 보다 사전 순으로 앞선다.
$37 - 47 - 57 - 56 - 55$ 위의 경로와 비교하면 $3$ 번째 노드인 $46$ 이 $57$ 보다 사전순으로 앞선다.

입력으로 $L$ , $K$ , $x$ , $y$ 가 주어졌을 때 Bob을 도와 $x$ 와 $y$ 사이의 최단 경로 중 사전 순으로 $K$ 번째 최단 경로를 구해보자. 만약 $x$ 와 $y$ 사이의 최단 경로의 개수가 $K$ 보다 작다면 "NO"를 출력하도록 한다.

입력

첫 줄에 테스트 케이스의 수 $T$ 가 주어진다.

각 테스트 케이스의 입력은 한 줄에 $L$ , $K$ , $x$ , $y$ 가 공백으로 구분되어 주어진다.

출력

각 테스트 케이스의 정답을 각 줄에 출력한다.

$K$ 번째 최단 경로가 존재하는 경우 해당 최단 경로를 출력하고, 그렇지 않은 경우 "NO"를 출력한다 (따옴표 제외).

제한

$1 ≤ T ≤ 15$
$2 ≤ L ≤ 4$
$1 ≤ K ≤ 10^{18}$
$0 ≤ x, y < 10^L$
$x$ , $y$ 는 언제나 선행 $0$ 을 포함하여 길이가 $L$ 인 형태로 주어진다.