{"raw_statement":[{"iden":"statement","content":"Andréh and his friend Andréas are board-game aficionados. They know many of their friends would love to go on a trip to Phuket, Thailand, and so they want to challenge them at Kem Kradãn, a traditional Thai board game.\n\nKem Kradãn (เกมกระดาน) has been played since the 2nd century AD. The game is played with N pieces where each piece has two faces, one of which is golden and the other is white. The game starts with all pieces arranged in a line on the board and they are numbered from 1 to N from left to right. When a piece numbered i has its golden face up, it can be removed from the board. When this is done, the pieces numbered i - 1 and i + 1 are flipped, if they're still there. The goal is to remove all game pieces.\n\nBefore challenging their friends, Andréh and Andréas want to make sure their initial configurations have a solution. To help them, given an initial configuration, you must determine if it is possible to remove all game pieces and, if so, you must show how to do it.\n\nThe first line has a single integer T, the number of test cases.\n\nEach test case is formed by a line containing an integer N, the number of pieces, followed by line containing a string of length N containing only the letters _B_ (white face up) and _D_ (golden face up), representing the initial state of the game.\n\n*Limits* \n\nFor each test case, print a line containing _Y_ if it is possible to remove every piece from the board, or _N_ otherwise. In case it is possible to remove all the pieces, you should also print on the next line a sequence of N integers each representing a piece number, indicating the order in which the pieces must be removed. If there is more than one possible sequence, you can print any of them.\n\n"},{"iden":"input","content":"The first line has a single integer T, the number of test cases.Each test case is formed by a line containing an integer N, the number of pieces, followed by line containing a string of length N containing only the letters _B_ (white face up) and _D_ (golden face up), representing the initial state of the game.*Limits*   1 ≤ T ≤ 100  1 ≤ N ≤ 105  The sum of N over all test cases will not exceed 5·105 "},{"iden":"output","content":"For each test case, print a line containing _Y_ if it is possible to remove every piece from the board, or _N_ otherwise. In case it is possible to remove all the pieces, you should also print on the next line a sequence of N integers each representing a piece number, indicating the order in which the pieces must be removed. If there is more than one possible sequence, you can print any of them."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ denote the number of pieces.  \n- Let $ s_k \\in \\{B, D\\}^{n_k} $ denote the initial configuration, where $ s_{k,i} = D $ means piece $ i $ has golden face up, and $ s_{k,i} = B $ means white face up.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 1000 $  \n2. For each $ k $, $ 1 \\le n_k \\le 100 $  \n\n**Objective**  \nFor each test case $ k $:  \n- Determine if there exists a sequence $ \\sigma = (\\sigma_1, \\sigma_2, \\dots, \\sigma_{n_k}) $, a permutation of $ \\{1, 2, \\dots, n_k\\} $, such that removing pieces in order $ \\sigma_1, \\sigma_2, \\dots, \\sigma_{n_k} $ results in all pieces being removed.  \n- A piece $ i $ can be removed only if its current face is golden (i.e., $ D $).  \n- Upon removal of piece $ i $:  \n  - Piece $ i-1 $ (if exists and still on board) is flipped.  \n  - Piece $ i+1 $ (if exists and still on board) is flipped.  \n- Output \"Y\" and the sequence $ \\sigma $ if possible; otherwise output \"N\".","simple_statement":"You are given a row of N pieces, each showing either 'B' (white) or 'D' (golden).  \nYou can remove a piece only if it shows 'D'.  \nWhen you remove piece i, flip pieces i-1 and i+1 (if they exist).  \nGoal: Remove all pieces.  \n\nFor each test case:  \n- Print \"Y\" if possible, \"N\" otherwise.  \n- If \"Y\", print any valid order of removal (piece numbers 1 to N).","has_page_source":false}