G2. Hard Formula (Hard Version)
math
This is the hard version of the problem. The difference between the versions is that in this version, the limit on \(n\) and the time limit are higher. You can hack only if you solved all versions of this problem. You are given an integer \(n\), and you need to compute \((\sum_{k=1}^n k\bmod\varphi(k))\bmod 2^{32}\), where \(\varphi(k)\) equals the number of positive integers no greater than \(k\) that are coprime with \(k\).
The only line contains a single integer \(n\) (\(1 \le n \le 10^{12}\)).
Print a single integer, representing \((\sum_{k=1}^n k\bmod\varphi(k))\bmod 2^{32}\).