Problem Statement
For integers l, r, and x (lleqr), let us define dist(l,r,x) as follows.
- If x<l: dist(l,r,x)=l−x
- If lleqxleqr: dist(l,r,x)=0
- If r<x: dist(l,r,x)=x−r
You are given N pairs of integers, the i-th of which is (Li,Ri). For each k=1,2,cdots,N, solve the following problem.
- Let us choose an integer x freely and compute max(dist(L1,R1,x),dist(L2,R2,x),cdots,dist(Lk,Rk,x)). Find the minimum possible value of this.
Constraints
- 1leqNleq2times105
- 1leqLileqRileq109
- All values in input are integers.
Input is given from Standard Input in the following format:
N
L1 R1
L2 R2
vdots
LN RN
Output
Print the answers for k=1,2,cdots,N in this order.
Sample Output 1
- For k=1, an optimal choice is x=1.
- For k=2, an optimal choice is x=3.
- For k=3, an optimal choice is x=4.
Sample Output 2