31290번 - LR

문제

영어 소문자로 이루어진 길이 $N$의 문자열 $A$가 주어진다.

희원이는 다음 두 가지 연산을 이용해 길이 $N$의 문자열 $B$를 만들고자 한다. $B$는 처음에 빈 문자열이다.

• $L$: $A$의 첫 번째 문자를 $B$의 맨 뒤에 추가한다. 그리고 $A$의 첫 번째 문자를 삭제한다.
• $R$: $A$의 맨 마지막 문자를 $B$의 맨 뒤에 추가한다. 그리고 $A$의 마지막 문자를 삭제한다.

연산을 적용하는 서로 다른 방법의 수는 총 2ドル^N$가지다. 연산의 결과로 만들 수 있는 모든 문자열 중, 사전순으로 $K$번째에 위치하는 문자열을 출력하라.

결과로 나온 두 문자열이 같더라도, 두 문자열을 만드는 데 사용한 연산 과정이 다르다면 다른 문자열로 세야 한다.

입력

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1 \le T \le 10\ 000)$

다음 줄부터 각 테스트 케이스의 정보가 주어진다. 하나의 테스트 케이스는 두 개의 줄로 이루어져 있으며, 첫째 줄에는 $N$과 $K$가 공백으로 구분되어 주어진다. $(1 \le N \le 1\ 000$; 1ドル \le K \le \min(2^N, 10^{18}))$

둘째 줄에는 영어 소문자로 이루어진 길이 $N$의 문자열 $A$가 주어진다.

주어지는 모든 $N^2$의 합은 10ドル^6$ 이하이다.

출력

각 테스트 케이스마다 연산을 적용해서 만들 수 있는 문자열 $B$ 중 사전순으로 $K$번째에 위치하는 문자열을 한 줄에 하나씩 출력한다.

제한

힌트