This is the hard version of the problem. The difference between the versions is that in this version, the constraint on (x) and time limit are higher. You can hack only if you solved all versions of this problem. The Beaver is training to jump long distances. The Beaver can already jump (x) meters. However, just jumping as far as possible is easy and boring. Therefore, the Beaver has created an unusual training track for jumping. The track consists of (n) platforms; each platform consists of (d_i) meter cells. If the Beaver stands on platform number (i), jumps, and lands back on the same platform, this results in (s_i) penalty points being awarded; otherwise, no penalty points are given. The Beaver can jump forward any integer number of cells less than or equal to (x). Note that the Beaver can skip one or more platforms in a single jump without landing on them at all. The Beaver has unlimited computational power in its mind and always jumps in such a way as to minimize the total penalty for passing the track. Moreover, the track is not constant, and sometimes the lengths and penalties of some platforms change. Learn to calculate what penalty the Beaver will get if it starts standing on the first cell of platform number (l) and finishes standing on the last cell of platform number (r). The first line contains three integers (n), (q), (x) — the number of sections of the track, the number of queries, and the maximum jump length, respectively ((1 \leq n \leq 10^6); (1 \leq q \leq 10^4); (1 \leq x \leq 10)). The second line contains (n) integers (d_i) — the lengths of the platforms ((1 \leq d_i \leq 10^7)). The third line contains (n) integers (s_i) — the penalties ((1 \leq s_i \leq 10^5)). The following (q) lines describe the queries in one of the following formats: " 1 (i) (v) " — set the length of the (i)-th platform to (v) ((1 \leq i \leq n); $$$1 \le