1907B.md (2254B)
1 Source: https://codeforces.com/problemset/problem/1907/B 2 3 B. YetnotherrokenKeoard 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Polycarp has a problem — his laptop keyboard is broken. 22 23 Now, when he presses the 'b' key, it acts like an unusual backspace: it deletes the last (rightmost) lowercase letter in the typed string. If there are no lowercase letters in the typed string, then the press is completely ignored. 24 25 Similarly, when he presses the 'B' key, it deletes the last (rightmost) uppercase letter in the typed string. If there are no uppercase letters in the typed string, then the press is completely ignored. 26 27 In both cases, the letters 'b' and 'B' are not added to the typed string when these keys are pressed. 28 29 Consider an example where the sequence of key presses was "ARaBbbitBaby". In this case, the typed string will change as follows: "" $\xrightarrow{\texttt{A}}$ "A" $\xrightarrow{\texttt{R}}$ "AR" $\xrightarrow{\texttt{a}}$ "ARa" $\xrightarrow{\texttt{B}}$ "Aa" $\xrightarrow{\texttt{b}}$ "A" $\xrightarrow{\texttt{b}}$ "A" $\xrightarrow{\texttt{i}}$ "Ai" $\xrightarrow{\texttt{t}}$ "Ait" $\xrightarrow{\texttt{B}}$ "it" $\xrightarrow{\texttt{a}}$ "ita" $\xrightarrow{\texttt{b}}$ "it" $\xrightarrow{\texttt{y}}$ "ity". 30 31 Given a sequence of pressed keys, output the typed string after processing all key presses. 32 33 Input 34 35 The first line of the input data contains an integer $t$ ($1 \le t \le 1000$), the number of test cases in the test. 36 37 The following contains $t$ non-empty lines, which consist of lowercase and uppercase letters of the Latin alphabet. 38 39 It is guaranteed that each line contains at least one letter and the sum of the lengths of the lines does not exceed $10^6$. 40 41 Output 42 43 For each test case, output the result of processing the key presses on a separate line. If the typed string is empty, then output an empty line. 44 45 Example 46 47 Input 48 49 ``` 50 12 51 52 ARaBbbitBaby 53 54 YetAnotherBrokenKeyboard 55 56 Bubble 57 58 Improbable 59 60 abbreviable 61 62 BbBB 63 64 BusyasaBeeinaBedofBloomingBlossoms 65 66 CoDEBARbIES 67 68 codeforces 69 70 bobebobbes 71 72 b 73 74 TheBBlackbboard 75 ``` 76 77 Output 78 79 ``` 80 ity 81 YetnotherrokenKeoard 82 le 83 Imprle 84 revile 85 86 usyasaeeinaedofloominglossoms 87 CDARIES 88 codeforces 89 es 90 91 helaoard 92 ```