import sys from operator import add readline = sys.stdin.readline class Lazysegtree: #RUQ def __init__(self, A, intv, initialize = True, segf = add): #区間は 1-indexed で管理 self.N = len(A) self.N0 = 2**(self.N-1).bit_length() self.intv = intv self.segf = segf self.lazy = [None]*(2*self.N0) if initialize: self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N) for i in range(self.N0-1, -1, -1): self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) else: self.data = [intv]*(2*self.N0) def __repr__(self): return str([self.query(i, i+1) for i in range(self.N)]) def _ascend(self, k): k = k >> 1 c = k.bit_length() for j in range(c): idx = k >> j self.data[idx] = self.segf(self.data[2*idx], self.data[2*idx+1]) def _descend(self, k): k = k >> 1 idx = 1 c = k.bit_length() for j in range(1, c+1): idx = k >> (c - j) if self.lazy[idx] is None: continue self.data[2*idx] = self.data[2*idx+1] = self.lazy[2*idx] \ = self.lazy[2*idx+1] = self.lazy[idx] self.lazy[idx] = None def query(self, l, r): L = l+self.N0 R = r+self.N0 self._descend(L//(L & -L)) self._descend(R//(R & -R)-1) s = self.intv while L < R: if R & 1: R -= 1 s = self.segf(s, self.data[R]) if L & 1: s = self.segf(s, self.data[L]) L += 1 L >>= 1 R >>= 1 return s def update(self, l, r, x): L = l+self.N0 R = r+self.N0 Li = L//(L & -L) Ri = R//(R & -R) self._descend(Li) self._descend(Ri-1) while L < R : if R & 1: R -= 1 self.data[R] = x self.lazy[R] = x if L & 1: self.data[L] = x self.lazy[L] = x L += 1 L >>= 1 R >>= 1 self._ascend(Li) self._ascend(Ri-1) class Segtree: def __init__(self, A, intv, initialize = True, segf = max): self.N = len(A) self.N0 = 2**(self.N-1).bit_length() self.intv = intv self.segf = segf if initialize: self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N) for i in range(self.N0-1, 0, -1): self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) else: self.data = [intv]*(2*self.N0) def __repr__(self): return str([self.query(i, i+1) for i in range(self.N)]) def update(self, k, x): k += self.N0 self.data[k] = x while k > 0 : k = k >> 1 self.data[k] = self.segf(self.data[2*k], self.data[2*k+1]) def query(self, l, r): L, R = l+self.N0, r+self.N0 s = self.intv while L < R: if R & 1: R -= 1 s = self.segf(s, self.data[R]) if L & 1: s = self.segf(s, self.data[L]) L += 1 L >>= 1 R >>= 1 return s def binsearch(self, l, r, check, reverse = False): L, R = l+self.N0, r+self.N0 SL, SR = [], [] while L < R: if R & 1: R -= 1 SR.append(R) if L & 1: SL.append(L) L += 1 L >>= 1 R >>= 1 if reverse: for idx in (SR + SL[::-1]): if check(self.data[idx]): break else: return -1 while idx < self.N0: if check(self.data[2*idx+1]): idx = 2*idx + 1 else: idx = 2*idx return idx - self.N0 else: pre = self.data[l+self.N0] for idx in (SL + SR[::-1]): if not check(self.segf(pre, self.data[idx])): pre = self.segf(pre, self.data[idx]) else: break else: return -1 while idx < self.N0: if check(self.segf(pre, self.data[2*idx])): idx = 2*idx else: pre = self.segf(pre, self.data[2*idx]) idx = 2*idx + 1 return idx - self.N0 def compress(L): L2 = list(set(L)) L2.sort() C = {v : k for k, v in enumerate(L2)} return L2, C def calc(Ax, Ay): N = len(Ax) Lx, Cx = compress(Ax) Lx.append(0) table = Segtree([None]*(N+2), 0, initialize = False, segf = max) T = Lazysegtree([None]*(N+2), 0, initialize = False) N0 = T.N0 ans = [0]*N for i in range(N): x, y = Ax[i], Ay[i] xidx = Cx[x] mt = table.query(xidx, N0) if mt >= y: ans[i] = ans[i-1] continue pidx = table.binsearch(0, xidx, lambda x: x > y, reverse = True) table.update(xidx, y) midx = table.binsearch(xidx+1, N0, lambda x: x == mt) #print(table) #print(i, pidx, xidx, midx, mt) T.update(pidx+1, xidx+1, 0) T.update(xidx, xidx+1, (Lx[xidx] - Lx[pidx])*y) T.update(midx, midx+1, (Lx[midx] - Lx[xidx])*mt) #print('T', T) ans[i] = T.query(0, N) return ans N = int(readline()) XaYaXbYb = [tuple(map(int, readline().split())) for _ in range(N)] Xa, Ya, Xb, Yb = map(list, zip(*XaYaXbYb)) Xa = [-x for x in Xa] Ya = [-y for y in Ya] Ans = [0]*N ans1 = calc(Xb, Yb) ans2 = calc(Xb, Ya) ans3 = calc(Xa, Yb) ans4 = calc(Xa, Ya) for i in range(N): Ans[i] = ans1[i] + ans2[i] + ans3[i] + ans4[i] Ans = [0] + Ans Ans = [a2 - a1 for a1, a2 in zip(Ans, Ans[1:])] print('\n'.join(map(str, Ans))) #print(ans1, ans2, ans3, ans4)