Description: This is an interactive problem. This is a hard version of the problem. The difference from the easy version is that in the hard version $$$1 \le t \le \min(n, 10^4)$$$ and the total number of queries is limited to $$$6 \cdot 10^4$$$. Polycarp is playing a computer game. In this game, an array consisting of zeros and ones is hidden. Polycarp wins if he guesses the position of the $$$k$$$-th zero from the left $$$t$$$ times. Polycarp can make no more than $$$6 \cdot 10^4$$$ requests totally of the following type: - ? $$$l$$$ $$$r$$$ — find out the sum of all elements in positions from $$$l$$$ to $$$r$$$ ($$$1 \le l \le r \le n$$$) inclusive. To make the game more interesting, each guessed zero turns into one and the game continues on the changed array. More formally, if the position of the $$$k$$$-th zero was $$$x$$$, then after Polycarp guesses this position, the $$$x$$$-th element of the array will be replaced from $$$0$$$ to $$$1$$$. Help Polycarp win the game. Input Format: None Output Format: None Note: In the first test, the array $$$[1, 0, 1, 1, 0, 1]$$$ is hidden. After answering the query $$$k=2$$$, the array changed to $$$[1, 0, 1, 1, 1, 1]$$$.