import sys from math import ceil, log2 MOD = 998244353 def modinv(x): return pow(x, MOD-2, MOD) # lazy segment tree specialized to the problem class LazySegTree: # op : combine two S = (a,b) # mapping : apply factor f to S (only multiplies a) # composition : multiply factors def __init__(self, init): # init: list of pairs (a,b) modulo MOD n = len(init) if n == 0: self.n0 = 1 else: self.n0 = 1 << (n-1).bit_length() self.size = n self.d = [(1,1)] * (2 * self.n0) self.lz = [1] * self.n0 # lazy stored at internal nodes 1..n0-1 # build leaves for i in range(n): self.d[self.n0 + i] = init[i] for i in range(self.n0 - 1, 0, -1): self._update(i) self.h = (self.n0).bit_length() - 1 def _op(self, L, R): # L, R are tuples (a,b) aL, bL = L aR, bR = R # (aL * (1 - bL) + aR * (1 - bR), 0) t = (aL * ((1 - bL) % MOD) + aR * ((1 - bR) % MOD)) % MOD return (t, 0) def _mapping(self, f, x): a, b = x return (a * f % MOD, b) def _all_apply(self, k, f): self.d[k] = self._mapping(f, self.d[k]) if k < self.n0: self.lz[k] = f * self.lz[k] % MOD def _push(self, k): f = self.lz[k] if f != 1: self._all_apply(2*k, f) self._all_apply(2*k+1, f) self.lz[k] = 1 def _update(self, k): self.d[k] = self._op(self.d[2*k], self.d[2*k+1]) def apply(self, l, r, f): # apply f to range [l, r) if l >= r: return l += self.n0 r += self.n0 l0, r0 = l, r for i in range(self.h, 0, -1): self._push(l >> i) self._push((r-1) >> i) while l < r: if l & 1: self._all_apply(l, f) l += 1 if r & 1: r -= 1 self._all_apply(r, f) l >>= 1 r >>= 1 # rebuild for i in range(1, self.h + 1): self._update(l0 >> i) self._update((r0 - 1) >> i) def set(self, p, val): # push path, set leaf, rebuild p += self.n0 for i in range(self.h, 0, -1): self._push(p >> i) self.d[p] = val p >>= 1 while p: self._update(p) p >>= 1 def get(self, p): p += self.n0 for i in range(self.h, 0, -1): self._push(p >> i) return self.d[p] def all_prod(self): return self.d[1] # read input fast data = list(map(int, sys.stdin.buffer.read().split())) it = iter(data) N = next(it) X = [0]*N Y = [0]*N for i in range(N): X[i] = next(it) Y[i] = next(it) # coordinate compress zX = sorted(set(X)) zY = sorted(set(Y)) if len(zX) == 1 or len(zY) == 1: print(0) sys.exit(0) rX = [zX.index(x) for x in X] rY = [zY.index(y) for y in Y] # fractions in mod inv4 = modinv(4) f34 = 3 * inv4 % MOD # 3/4 mod f43 = modinv(f34) # inverse of f34 ans = 0 # two passes (swap axes) for _ in range(2): # build G: for each x-index, list of y-indices m = len(zY) G = [[] for _ in range(len(zX))] for i in range(N): G[rX[i]].append(rY[i]) # initialize V V = [(1,1) for _ in range(m)] # for each point, if rY+1 < m, multiply V[rY+1].a by f34 for i in range(N): ry = rY[i] if ry + 1 < m: a, b = V[ry+1] V[ry+1] = (a * f34 % MOD, b) # prefix multiply for i in range(1, m): a_prev, _ = V[i-1] a, b = V[i] V[i] = (a * a_prev % MOD, b) seg = LazySegTree(V) fs = 1 for i in range(len(zX)-1): for y in G[i]: cur = seg.get(y) # set second component multiplied by f34 seg.set(y, (cur[0], cur[1] * f34 % MOD)) # apply multipliers if 0 < y: seg.apply(0, y, f34) seg.apply(y+1, m, f43) fs = fs * f34 % MOD all_prd = seg.all_prod() a_all, b_all = all_prd term = (1 - (a_all * ((1 - b_all) % MOD) % MOD) - fs) % MOD width = zX[i+1] - zX[i] ans = (ans + term * (width % MOD)) % MOD # swap axes rX, rY = rY, rX zX, zY = zY, zX # multiply ans by 4^N then by 2 ans = ans * pow(4, N, MOD) % MOD ans = ans * 2 % MOD print(ans)