This is the hard version of the problem. The difference between the versions is that in this version, the limits on (t) and (n) are bigger. You can hack only if you solved all versions of this problem. A bracket sequence is called balanced if it can be constructed by the following formal grammar. The empty sequence (\varnothing) is balanced. If the bracket sequence (A) is balanced, then (\mathtt{(}A\mathtt{)}) is also balanced. If the bracket sequences (A) and (B) are balanced, then the concatenated sequence (A B) is also balanced. For example, the sequences " (())() ", " () ", " (()(())) ", and the empty sequence are balanced, while " (() " and " (()))( " are not. Given a balanced bracket sequence (s), a pair of indices ((i,j)) ((i<j)) is called a good pair if (s_i) is ' ( ', (s_j) is ' ) ', and the two brackets are added simultaneously with respect to Rule 2 while constructing the sequence (s). For example, the sequence " (())() " has three different good pairs, which are ((1,4)), ((2,3)), and ((5,6)). One can show that any balanced bracket sequence of (2n) brackets contains exactly (n) different good pairs, and using any order of rules to construct the same bracket sequence will yield the same set of good pairs. Emily will play a bracket guessing game with John. The game is played as follows. Initially, John has a balanced bracket sequence (s) containing (n) different good pairs, which is not known to Emily. John tells Emily the value of (n) and asks Emily to guess the sequence. Throughout (n) turns, John gives Emily the following kind of clue on each turn. (l\;r): The sequence (s) contains a good pair ((l,r)). The clues that John gives Emily are pairwise distinct and do not contradict each other. At a certain point, Emily can be certain that the balanced bracket sequence satisfying the clues given so far is unique. For example, assume Emily knows tha