A string is a valid parentheses string (denoted VPS) if and only if it consists of "( " and ") " characters only, and: It is the empty string, or It can be written as AB (A concatenated with B), where A and B are VPS's, or It can be written as (A), where A is a VPS. We can similarly define the nesting depth depth(S) of any VPS S as follows: depth( " ") = 0 depth(A + B) = max(depth(A), depth(B)), where A and B are VPS's depth( "( " + A + ") ") = 1 + depth(A), where A is a VPS. For example, " ", "()() ", and "()(()()) " are VPS's (with nesting depths 0, 1, and 2), and ")( " and "(() " are not VPS's. Given a VPS seq, split it into two disjoint subsequences A and B, such that A and B are VPS's (and A.length + B.length = seq.length).