34859번 - KHU와 DKU 스페셜 저지

문제

2ドルN$개의 문자들로 이루어진 중복집합 $A$가 있다. $A$의 모든 문자는 'D', 'H', 'K', 'U'중 하나이다.

$A$의 모든 문자들을 임의의 순서로 나열하여 만든 문자열을 $B$라 하고, $B$의 1ドル$번째부터 $N$번째 문자까지 추출한 부분 문자열을 $B_1,ドル $N+1$번째부터 2ドルN$번째 문자까지 추출한 부분 문자열을 $B_2$라 하자.

문자열 $S$에 대하여 함수 $\text{khu}$와 $\text{dku}$를 다음과 같이 정의한다.

• $\text{khu}(S)$: $S$에서 부분 수열로 등장하는 "KHU"의 개수
• $\text{dku}(S)$: $S$에서 부분 수열로 등장하는 "DKU"의 개수

쿠옹이와 단웅이는 $B$의 부분 문자열 $B_1$과 $B_2$에 대하여 다음과 같은 작업을 진행한다.

쿠옹이는 $B_1$의 문자들의 순서를 적절히 바꾸어 새로운 문자열 $S_1$을 만든다. 쿠옹이는 $\text{khu}(S_1)$의 값이 최대가 되는 순서를 선택한다.

단웅이는 $B_2$의 문자들의 순서를 적절히 바꾸어 새로운 문자열 $S_2$를 만든다. 단웅이는 $\text{dku}(S_2)$의 값이 최대가 되는 순서를 선택한다.

쿠옹이와 단웅이의 작업이 끝났을 때 $\text{khu}(S_1) = \text{dku}(S_2)$를 만족시키는 문자열 $B$를 아무거나 하나 찾아보자.

입력

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

각 테스트 케이스의 첫째 줄에 $N$이 주어진다. (1ドル \leq N \leq 10^6$)

각 테스트 케이스의 둘째 줄에 음이 아닌 정수 $d,ドル $h,ドル $k,ドル $u$가 공백으로 구분되어 주어진다. $d,ドル $h,ドル $k,ドル $u$는 각각 $A$에 들어있는 문자 'D', 'H', 'K', 'U'의 개수를 의미한다. ($d+h+k+u = 2N$)

모든 테스트 케이스에 대한 $N$의 합은 10ドル^6$을 넘지 않는다.

출력

각 테스트 케이스마다 $\text{khu}(S_1) = \text{dku}(S_2)$를 만족시키는 문자열 $B$가 존재한다면 첫째 줄에 "YES"를 출력하고, 둘째 줄에 $B$를 출력한다. 가능한 답이 여러 가지라면 아무거나 출력한다.

만약 가능한 문자열 $B$가 존재하지 않는다면 첫째 줄에 "NO"를 대신 출력한다.

제한

노트

문자열의 부분 수열이란 주어진 문자열에서 원래 순서를 유지하며 0ドル$개 이상의 문자를 제거하여 얻을 수 있는 문자열이다.

예를 들어, 문자열 "KHUDKU"에는 다음과 같이 부분 수열로 "KHU"가 2ドル$번, "DKU"가 1ドル$번 등장한다.

• "KHUDKU"
• "KHUDKU"
• "KHUDKU"