P.S. I feel really guilty that I've made an awful mistake on the checker.
We read the pseudo code carefully. If we ignore "break", tot will be up to .
Consider whether we can make such inequality d ≤ p[j].x - p[i].x is always false. The obvious way is to make all points' x coordinates the same. And we can just choose n distinct numbers to be all points' y coordinate.
Thus the problem is solved.
Consider a number x. If we apply an assignment x = x 3, x becomes x 3. If we apply such assignment once more, we will get (x 3)3 = x 32. If we apply such assignment k times, we will get x 3 k.
Thus, we can get such a sequence a 0 = x, a 1 = x 3, a 2 = x 32, ..., a k = x 3 k, ....
Consider a prime p. From Fermat's Little Theorem, we can get x p - 1 = 1(mod p). Further more, we can get x y = x ymod(p - 1)(mod p), here a mod b means the remainder of a divided by b.
Fortunately, 348 = 1(mod (95542721 - 1)), thus, x 3 k = x 3 kmod48(mod p). In other words, a k = a k + 48, which means the cycle of the sequence is T = 48.
Let's come back to the topic. Each time we run a 1-type query, for every i in the range [l, r], we apply such an assignment a i = a i 3. At any moment some i has been applied 48 times such assignments, we can consider this i hasn't been applied any assignments before.
We can use segment tree to solve this problem. Every node of the segment tree maintains some information: the times that we applied assignments in the node's whole range(it's a lazy tag), current sum of the node's corresponding range and the sum of the node's range after we applied assignments k(1 ≤ k < 48) times.
In such a way, we can solve the problem in O(n·T + q·T·logn) time.
If you do not realize how to maintain the segment tree clearly, you can view the code 3782263.