problem.txt (2083B)
1 B. Did Not Go to Print 2 time limit per test2 seconds 3 memory limit per test256 megabytes 4 Recently, K1o0n bought himself a new expensive printer, which is distinguished by its memory, that is, it may not print immediately. Yesterday, while he was away from his new purchase, his friends used the printer. 5 6 There are n 7 documents numbered from 1 8 to n 9 . Initially, the printer memory is empty. The friends sequentially performed n 10 commands on the printer, where the i 11 -th command can be one of: 12 13 '1' — scanning. Document i 14 is sent to the device memory and is placed on top of everything already there. 15 '2' — printing from memory. If the memory is not empty, the device prints the topmost document in memory and removes it from there. Otherwise, the device prints document i 16 . 17 '3' — quick print. The device prints document i 18 . 19 Today, the friends came to K1o0n with a complaint — not all documents were printed. Help K1o0n find the indices of all documents that were not printed. 20 21 Input 22 The first line contains an integer t 23 (1≤t≤104 24 ) — the number of testcases. 25 26 The first line of each testcase contains an integer n 27 (1≤n≤2⋅105 28 ) — the number of documents. 29 30 The second line of each testcase contains a string s 31 of length n 32 , consisting of the characters '1', '2' and '3' — the friends' commands. 33 34 It is guaranteed that the sum of n 35 over all testcases does not exceed 2⋅105 36 . 37 38 Output 39 For each testcase, output two lines. 40 41 In the first line — the number k 42 of documents that were not printed. 43 44 In the second line — their numbers in increasing order, separated by spaces. If k=0 45 , the second line is empty. 46 47 --- 48 49 - documents 1 to n 50 - n commands where we do the following for each instruction 51 1. scan - place document i on top of memory 52 2. print - iff memory not empty, print topmost and pop, else print i 53 3. quick print - prints document i 54 55 --- 56 57 examples 58 59 60 61 2 62 12 63 64 65 n = 2 66 s = 12 (n commands) 67 68 place 1 on top 69 print 1 70 71 not printed 2 72 73 --- 74 75 2 76 13 77 78 n = 2 79 s = 13 80 81 push 1 onto stack 82 print 2 83 84 return 1 and 1 85 86 --- 87 88 2 89 23 90 91 92 93 --- 94 95 6 96 112332 97 3 98 112 99 6 100 211213