write a go solution for 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<=t<=min(n,10^4) and the total number of queries is limited to 6*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*10^4 requests totally of the following type:

- ? l r — find out the sum of all elements in positions from l to r (1<=l<=r<=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].. Output only the code with no comments, explanation, or additional text.