This is the hard version of the problem. The difference between the versions is that in this version, the sum of the lengths of the articles over all queries must not exceed (2.5\cdot 10^4). You can hack only if you solved all versions of this problem. This is an interactive problem. The RiOI Team has recently developed a text editor named RiOI Editor . The editor works with exactly one integer parameter (W) — the width of each line. It is known that (1 \leq W \leq 10^5). As you cannot understand the RiOI Language, from your point of view, words differ from each other only by their length. Hence, an article of length (n) is defined as a sequence (a) consisting of (n) positive integers, where (a_i) is the length of the (i)-th word in the article . The RiOI Editor displays the article (a_1, a_2,\ldots, a_n) on screen as follows: If (\max(a_1, a_2, \ldots, a_n) > W), the editor is unable to display the article ; Otherwise, the editor is able to display the article by the following process: Initially, (l = 1), and (s = 0). During the whole process, (l) always denotes the current number of lines in the editor, and (s) always denotes the sum of lengths of words in the last line; Then, for each (1\le i\le n): If (s + a_i \leq W), the word is inserted at the end of the current line. Thus, (l) remains unchanged, and (s) gets increased by (a_i). Otherwise, the word is inserted into a new line. Thus, (l) becomes (l + 1), and (s) becomes (a_i). The number of lines needed to display the article is the final value of (l). Initially, (l = 1), and (s = 0). During the whole process, (l) always denotes the current number of lines in the editor, and (s) always denotes the sum of lengths of words in the last line; Then, for each (1\le i\le n): If (s + a_i \leq W), the word is inserted at the end of the current line. Thus, (l) remains unchanged, and $$$