{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"Let us define a regular brackets sequence in the following way:\r\u003cbr\u003e\r\u003cbr\u003e1. Empty sequence is a regular sequence.\r\u003cbr\u003e2. If S is a regular sequence, then (S) and [S] are both regular sequences.\r\u003cbr\u003e3. If A and B are regular sequences, then AB is a regular sequence.\r\u003cbr\u003e\r\u003cbr\u003eFor example, all of the following sequences of characters are regular brackets sequences:\r\u003cbr\u003e\r\u003cbr\u003e(), [], (()), ([]), ()[], ()[()]\r\u003cbr\u003e\r\u003cbr\u003eAnd all of the following character sequences are not:\r\u003cbr\u003e\r\u003cbr\u003e(, [, ), )(, ([)], ([(]\r\u003cbr\u003e\r\u003cbr\u003eSome sequence of characters \u0027(\u0027, \u0027)\u0027, \u0027[\u0027, and \u0027]\u0027 is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string a1 a2 ... an is called a subsequence of the string b1 b2 ... bm, if there exist such indices 1 \u003d i1 \u0026lt; i2 \u0026lt; ... \u0026lt; in \u003d m, that aj \u003d bij for all 1 \u003d j \u003d n."}},{"title":"Input","value":{"format":"HTML","content":"The input file contains at most 100 brackets (characters \u0027(\u0027, \u0027)\u0027, \u0027[\u0027 and \u0027]\u0027) that are situated on a single line without any other characters among them."}},{"title":"Output","value":{"format":"HTML","content":"Write to the output file a single line that contains some regular brackets sequence that has the minimal possible length and contains the given sequence as a subsequence."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e([(]\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e()[()]\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}