Bedao và Bemai đã vận hành cửa hàng kem Bedao được ít lâu, và hai bạn trẻ bắt đầu lập kế hoạch dài hạn cho cửa hàng, cũng như cần xếp thời gian đồng đều để các bạn vừa có thể vừa tham gia công việc, lại vừa có thể tiếp tục học hành và tham gia các hoạt động khác.

Hiện tại hai bạn đã lập được kế hoạch bán kem cho ~n~ ngày. Ngày thứ ~i~ cửa hàng cần bán được ~a_i~ chiếc kem. Để giảm nhẹ khối lượng công việc, các bạn đã tính toán để không có hai ngày nào bán ra cùng số lượng kem. Mỗi ngày hoặc Bedao hoặc Bemai sẽ hoàn toàn phụ trách công việc bán hàng, và bạn còn lại sẽ không làm việc trong ngày đó.

Để xem khối lượng công việc có được cân bằng hay không, hai bạn trẻ đã nghĩ ra một chỉ số gọi là chỉ số đỉnh (peak index). Chỉ số đỉnh của một người được định nghĩa là số lượng ngày làm việc mà không có ngày làm việc trước đó bán được nhiều kem hơn ngày đang xét. Nói cách khác, nếu như bạn làm việc vào các ngày ~d_1, d_2, \ldots, d_k~ (~d_1 < d_2 < \ldots < d_k~) thì chỉ số đỉnh của bạn là số lượng số ~i~ thỏa mãn ~a_{d_i} > \max_{j < i} a_{d_j}~ (lưu ý ~i = 1~ cũng tính là một chỉ số thỏa mãn).

Cho danh sách số lượng kem cần bán trong mỗi ngày. Hãy tìm cách phân công công việc cho Bedao và Bemai để chỉ số đỉnh của hai bạn là bằng nhau.

Input

Dòng đầu tiên gồm số nguyên ~t~ (~1 \le t \le 10^6~)  – số lượng test case trong input. Tiếp theo đó là mô tả của ~t~ test case.

Dòng đầu tiên của test case gồm số nguyên ~n~ (~1 \le n \le 10^6~)  – số lượng ngày làm việc mà hai bạn đã lập kế hoạch trước.

Dòng tiếp theo của test case chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^9~, ~a_i \ne a_j~ với mọi ~i \ne j~)  – số lượng kem cần bán trong các ngày.

Dữ liệu đảm bảo tổng ~n~ qua các test case không vượt quá ~10^6~.

Output

Nếu như không có cách để chia công việc cho Bedao và Bemai mà chỉ số đỉnh của hai bạn là bằng nhau, hãy in ra "NO".

Ngược lại, dòng đầu tiên hãy in ra "YES", và dòng thứ hai in ra một xâu ~s~ có độ dài ~n~. Khi ~s_i=~ 'D' thì Bedao sẽ được phân công bán hàng vào ngày thứ ~i~, và khi ~s_i=~ 'M' thì Bemai sẽ được phân công bán hàng vào ngày thứ ~i~.

Nếu có nhiều đáp án, hãy in ra đáp án bất kì.

Scoring

• Subtask 1: (~300~ điểm): ~1 \le t \le 200~, ~1 \le n \le 15~.

• Subtask 2: (~700~ điểm): Tổng ~n~ trong tất cả các test case không quá ~200~.

• Subtask 3: (~1400~ điểm): Không có ràng buộc gì thêm.

Tổng cộng bài toán có ~2400~ điểm.

Sample Input

3
5
1 3 4 2 5
8
3 5 4 8 2 1 7 6
3
1 2 3

Sample Output

YES
DDMMM
YES
DMDMMMMM
NO