494A.md (1797B)
1 Source: https://codeforces.com/problemset/problem/494/A 2 3 A. Treasure 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 Malek has recently found a treasure map. While he was looking for a treasure he found a locked door. There was a string *s* written on the door consisting of characters '(', ')' and '#'. Below there was a manual on how to open the door. After spending a long time Malek managed to decode the manual and found out that the goal is to replace each '#' with one or more ')' characters so that the final string becomes beautiful. 22 23 Below there was also written that a string is called beautiful if for each *i* (1 ≤ *i* ≤ |*s*|) there are no more ')' characters than '(' characters among the first *i* characters of *s* and also the total number of '(' characters is equal to the total number of ')' characters. 24 25 Help Malek open the door by telling him for each '#' character how many ')' characters he must replace it with. 26 27 Input 28 29 The first line of the input contains a string *s* (1 ≤ |*s*| ≤ 105). Each character of this string is one of the characters '(', ')' or '#'. It is guaranteed that *s* contains at least one '#' character. 30 31 Output 32 33 If there is no way of replacing '#' characters which leads to a beautiful string print - 1. Otherwise for each character '#' print a separate line containing a positive integer, the number of ')' characters this character must be replaced with. 34 35 If there are several possible answers, you may output any of them. 36 37 Examples 38 39 Input 40 41 ``` 42 (((#)((#) 43 ``` 44 45 Output 46 47 ``` 48 1 49 2 50 ``` 51 52 Input 53 54 ``` 55 ()((#((#(#() 56 ``` 57 58 Output 59 60 ``` 61 2 62 2 63 1 64 ``` 65 66 Input 67 68 ``` 69 # 70 ``` 71 72 Output 73 74 ``` 75 -1 76 ``` 77 78 Input 79 80 ``` 81 (#) 82 ``` 83 84 Output 85 86 ``` 87 -1 88 ``` 89 90 Note 91 92 |*s*| denotes the length of the string *s*.