Paulliant is a linguist. Recently he received an article written in language A and he was told to translate it into language B. The two languages only differ in word order, so, Paulliant decided to tr
Paulliant is a linguist. Recently he received an article written in language A and he was told to translate it into language B. The two languages only differ in word order, so, Paulliant decided to translate by redefining the reading order of the articles, and came up with the following method. Suppose that the article consists of nnn words, numbered as 1,2,3⋯n1,2,3cdots n1,2,3⋯n. Paulliant generated a string strstrstr consisting of only '(', ')' and '-', whose length is also nnn. The string must satisfy the rule of bracket matching. Formally speaking, define s(is_{(i}s(i and s)is_{)i}s)i , representing the number of character '(' or ')' within the first iii characters of the string, respectively, there is s(i≥s)is_{(i} geq s_{)i}s(i≥s)i for every 1≤i≤n1leq ileq n1≤i≤n and s(n=s)ns_{(n}=s_{)n}s(n=s)n. The process to read the article obeys the following rules. The process starts from the first word. For the iii-th word, if stristr_istri is '-' or ')', then read the iii-th word directly, and jump to the (i+1)(i+1)(i+1)-th word. For the iii-th word, if stristr_istri is '(', then find the matching right bracket of it. Supposing it to be strjstr_jstrj, read the (i+1)(i+1)(i+1)-th to jjj-th word, then read the iii-th word, and finally jump to the (j+1)(j+1)(j+1)-th word. If we are to read the (n+1)(n+1)(n+1)-th word (obviously it doesn't exist), the process ends. Note that the process is recursive, meaning that when reading the (i+1)(i+1)(i+1)-th to jjj-th word in rule (2), it still follows the four rules. For example, If n=4n=4n=4, strstrstr is "(-)-", the reading order will be 2, 3, 1, 4. If n=7n=7n=7, strstrstr is "-((-)-)", the reading order will be 1, 4, 5, 3, 6, 7, 2. Now, give you the number of words nnn, and the string strstrstr Paulliant generated. Your task is to print the reading order following the four rules. It can be proved that the reading order should be a permutation of numbers from 111 to nnn.
