#### 311A — The Closest Pair

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.

#### 311D — Interval Cubing

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*^{3k}.

Thus, we can get such a sequence *a*_{0} = *x*, *a*_{1} = *x*^{3}, *a*_{2} = *x*^{32}, ..., *a*_{k} = *x*^{3k}, ....

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, 3^{48} = 1(*mod* (95542721 - 1)), thus, *x*^{3k} = *x*^{3kmod48}(*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.