import sys input = lambda: sys.stdin.readline().rstrip() class Segtree(): def __init__(self, nn, A = []): self.inf = 10 ** 9 self.size = 1 << nn n = self.size * 2 self.S = [0] * n self.ma = [0] * n self.mi = [0] * n self.mac = [1] * n self.mic = [1] * n self.sma = [-self.inf] * n self.smi = [self.inf] * n self.lazy = [0] * n for i, a in enumerate(A): self.node_set(i, a) for i in range(len(A), self.size): self.node_set(i, 0) self.update_all() def node_chmax(self, i, x): self.S[i] += (x - self.ma[i]) * self.mac[i] if self.ma[i] == self.mi[i]: self.ma[i] = x self.mi[i] = x elif self.ma[i] == self.smi[i]: self.ma[i] = x self.smi[i] = x else: self.ma[i] = x def node_chmin(self, i, x): self.S[i] += (x - self.mi[i]) * self.mic[i] if self.ma[i] == self.mi[i]: self.ma[i] = x self.mi[i] = x elif self.sma[i] == self.mi[i]: self.sma[i] = x self.mi[i] = x else: self.mi[i] = x def node_set(self, i, x): i += self.size self.ma[i] = x self.mi[i] = x self.S[i] = x def update_all(self): for i in range(self.size - 1, 0, -1): self.update(i) def update(self, i): c1 = i * 2 c2 = c1 | 1 self.S[i] = self.S[c1] + self.S[c2] if self.ma[c1] < self.ma[c2]: self.ma[i] = self.ma[c2] self.mac[i] = self.mac[c2] self.sma[i] = max(self.ma[c1], self.sma[c2]) elif self.ma[c1] > self.ma[c2]: self.ma[i] = self.ma[c1] self.mac[i] = self.mac[c1] self.sma[i] = max(self.sma[c1], self.ma[c2]) else: self.ma[i] = self.ma[c1] self.mac[i] = self.mac[c1] + self.mac[c2] self.sma[i] = max(self.sma[c1], self.sma[c2]) if self.mi[c1] < self.mi[c2]: self.mi[i] = self.mi[c1] self.mic[i] = self.mic[c1] self.smi[i] = min(self.smi[c1], self.mi[c2]) elif self.mi[c1] > self.mi[c2]: self.mi[i] = self.mi[c2] self.mic[i] = self.mic[c2] self.smi[i] = min(self.mi[c1], self.smi[c2]) else: self.mi[i] = self.mi[c1] self.mic[i] = self.mic[c1] + self.mic[c2] self.smi[i] = min(self.smi[c1], self.smi[c2]) def range_sum(self, a, b, i=1, l=0, r=-1): if r == -1: r = self.size if r <= a or b <= l: return 0 if a <=l and r <= b: return self.S[i] self.push(i, r - l) return self.range_sum(a, b, i * 2, l, (l + r) // 2) + self.range_sum(a, b, i * 2 | 1, (l + r) // 2, r) def push(self, i, le): if i >= self.size: return c1 = i * 2 c2 = c1 | 1 if self.lazy[i] != 0: self.node_add(c1, le // 2, self.lazy[i]) self.node_add(c2, le // 2, self.lazy[i]) self.lazy[i] = 0 if self.ma[c1] > self.ma[i]: self.node_chmax(c1, self.ma[i]) if self.ma[c2] > self.ma[i]: self.node_chmax(c2, self.ma[i]) if self.mi[c1] < self.mi[i]: self.node_chmin(c1, self.mi[i]) if self.mi[c2] < self.mi[i]: self.node_chmin(c2, self.mi[i]) def node_add(self, i, le, x): self.ma[i] += x if self.sma[i] != - self.inf: self.sma[i] += x self.mi[i] += x if self.smi[i] != self.inf: self.smi[i] += x self.S[i] += x * le self.lazy[i] += x def range_chmax(self, a, b, x, i=1, l=0, r=-1): if r == -1: r = self.size if r <= a or b <= l or self.mi[i] >= x: return if a <= l and r <= b and self.smi[i] > x: self.node_chmin(i, x) return self.push(i, r - l) self.range_chmax(a, b, x, i * 2, l, (l + r) // 2) self.range_chmax(a, b, x, i * 2 | 1, (l + r) // 2, r) self.update(i) def range_chmin(self, a, b, x, i=1, l=0, r=-1): if r == -1: r = self.size if r <= a or b <= l or self.ma[i] <= x: return if a <= l and r <= b and self.sma[i] < x: self.node_chmax(i, x) return self.push(i, r - l) self.range_chmin(a, b, x, i * 2, l, (l + r) // 2) self.range_chmin(a, b, x, i * 2 | 1, (l + r) // 2, r) self.update(i) def range_add(self, a, b, x, i=1, l=0, r=-1): if r == -1: r = self.size if r <= a or b <= l: return if a <= l and r <= b: self.node_add(i, r - l, x) return self.push(i, r - l) self.range_add(a, b, x, 2 * i, l, (l + r) // 2) self.range_add(a, b, x, 2 * i | 1, (l + r) // 2, r) self.update(i) N = int(input()) st = Segtree(17) pre = 0 ANS = [] for _ in range(N): xa, ya, xb, yb = map(int, input().split()) st.range_chmax(xa + 20000, xb + 20000, yb) st.range_chmax(xa + 70000, xb + 70000, -ya) s = st.range_sum(0, 1 << 17) ANS.append(s - pre) pre = s print("\n".join(map(str, ANS)))