use std::io::{self, Read}; const MOD: i64 = 998244353; #[derive(Copy, Clone, Debug, PartialEq, Eq)] struct Mint(i64); impl Mint { fn new>(v: T) -> Self { let mut x = v.into() % (MOD as i128); if x < 0 { x += MOD as i128; } Mint(x as i64) } fn zero() -> Self { Mint(0) } fn one() -> Self { Mint(1) } fn val(self) -> i64 { self.0 } fn pow(self, mut e: i64) -> Self { let mut base = self.0 as i128; let mut ex = e as i128; let mut res: i128 = 1; while ex > 0 { if (ex & 1) == 1 { res = (res * base) % (MOD as i128); } base = (base * base) % (MOD as i128); ex >>= 1; } Mint::new(res) } fn inv(self) -> Self { self.pow(MOD - 2) } } use std::ops::{Add, Sub, Mul, Div, AddAssign, MulAssign, SubAssign}; impl Add for Mint { type Output = Self; fn add(self, rhs: Self) -> Self::Output { let mut x = self.0 + rhs.0; if x >= MOD { x -= MOD; } Mint(x) } } impl Sub for Mint { type Output = Self; fn sub(self, rhs: Self) -> Self::Output { let mut x = self.0 - rhs.0; if x < 0 { x += MOD; } Mint(x) } } impl Mul for Mint { type Output = Self; fn mul(self, rhs: Self) -> Self::Output { Mint::new((self.0 as i128) * (rhs.0 as i128)) } } impl Div for Mint { type Output = Self; fn div(self, rhs: Self) -> Self::Output { self * rhs.inv() } } impl AddAssign for Mint { fn add_assign(&mut self, rhs: Self) { *self = *self + rhs; } } impl SubAssign for Mint { fn sub_assign(&mut self, rhs: Self) { *self = *self - rhs; } } impl MulAssign for Mint { fn mul_assign(&mut self, rhs: Self) { *self = *self * rhs; } } #[derive(Copy, Clone, Debug)] struct S { first: Mint, second: Mint, } fn op(a: S, b: S) -> S { let one = Mint::one(); let term_a = a.first * (one - a.second); let term_b = b.first * (one - b.second); S { first: term_a + term_b, second: Mint::zero() } } fn e() -> S { S { first: Mint::one(), second: Mint::one() } } fn mapping(f: Mint, mut x: S) -> S { x.first *= f; x } fn composition(f: Mint, g: Mint) -> Mint { f * g } fn id() -> Mint { Mint::one() } struct LazySegTree { n: usize, size: usize, data: Vec, lazy: Vec, // lazy[0] unused, indices 1..size-1 used } impl LazySegTree { fn new(v: &Vec) -> Self { let n = v.len(); let mut size = 1usize; while size < n { size <<= 1; } let mut data = vec![e(); 2 * size]; for i in 0..n { data[size + i] = v[i]; } for i in (1..size).rev() { data[i] = op(data[i << 1], data[i << 1 | 1]); } let lazy = vec![id(); size]; // indices 0..size-1 LazySegTree { n, size, data, lazy } } fn apply_node(&mut self, idx: usize, f: Mint) { self.data[idx] = mapping(f, self.data[idx]); if idx < self.size { self.lazy[idx] = composition(f, self.lazy[idx]); } } fn push(&mut self, idx: usize) { let f = self.lazy[idx]; if f != id() { self.apply_node(idx << 1, f); self.apply_node(idx << 1 | 1, f); self.lazy[idx] = id(); } } fn update_upward(&mut self, mut idx: usize) { while idx > 1 { idx >>= 1; self.data[idx] = op(self.data[idx << 1], self.data[idx << 1 | 1]); } } fn apply_range_rec(&mut self, idx: usize, l: usize, r: usize, ql: usize, qr: usize, f: Mint) { if ql >= r || qr <= l { return; } if ql <= l && r <= qr { self.apply_node(idx, f); return; } self.push(idx); let mid = (l + r) >> 1; self.apply_range_rec(idx << 1, l, mid, ql, qr, f); self.apply_range_rec(idx << 1 | 1, mid, r, ql, qr, f); self.data[idx] = op(self.data[idx << 1], self.data[idx << 1 | 1]); } fn apply_range(&mut self, l: usize, r: usize, f: Mint) { if l >= r { return; } self.apply_range_rec(1, 0, self.size, l, r, f); } fn set(&mut self, pos: usize, val: S) { let idx = self.size + pos; // push lazies from top to leaf let mut path = Vec::new(); let mut i = idx; while i > 1 { i >>= 1; path.push(i); } for &p in path.iter().rev() { self.push(p); } self.data[idx] = val; self.update_upward(idx); } fn get(&mut self, pos: usize) -> S { let idx = self.size + pos; let mut path = Vec::new(); let mut i = idx; while i > 1 { i >>= 1; path.push(i); } for &p in path.iter().rev() { self.push(p); } self.data[idx] } fn all_prod(&self) -> S { self.data[1] } } fn parse_input() -> Vec { let mut s = String::new(); io::stdin().read_to_string(&mut s).unwrap(); s.split_whitespace().map(|x| x.parse::().unwrap()).collect() } fn main() { let inp = parse_input(); let mut idx = 0usize; let n = inp[idx] as usize; idx += 1; let mut X = vec![0i64; n]; let mut Y = vec![0i64; n]; // IMPORTANT: read pairs (X[i], Y[i]) in sequence, same as original C++ for i in 0..n { X[i] = inp[idx]; idx += 1; Y[i] = inp[idx]; idx += 1; } if n == 0 { println!("0"); return; } let f34 = Mint::new(3) / Mint::new(4); let f43 = Mint::one() / f34; let mut zX = X.clone(); let mut zY = Y.clone(); zX.sort_unstable(); zY.sort_unstable(); // do NOT dedup — keep same semantics as original C++ implementation let mut rX = vec![0usize; n]; let mut rY = vec![0usize; n]; for i in 0..n { rX[i] = zX.binary_search(&X[i]).unwrap(); rY[i] = zY.binary_search(&Y[i]).unwrap(); } if zX.len() == 1 || zY.len() == 1 { println!("0"); return; } let mut ans = Mint::zero(); for _rep in 0..2 { let mut G: Vec> = vec![Vec::new(); zX.len()]; for i in 0..n { G[rX[i]].push(rY[i]); } let m = zY.len(); let mut V = vec![e(); m]; for i in 0..n { if rY[i] + 1 < m { V[rY[i] + 1].first *= f34; } } for i in 1..m { let prev = V[i - 1].first; V[i].first *= prev; } let mut seg = LazySegTree::new(&V); let mut fs = Mint::one(); for i in 0..(zX.len() - 1) { for &y in &G[i] { let mut cur = seg.get(y); cur.second *= f34; seg.set(y, cur); seg.apply_range(0, y, f34); seg.apply_range(y + 1, m, f43); fs *= f34; } let all_prd = seg.all_prod(); let one = Mint::one(); let term = one - all_prd.first * (one - all_prd.second) - fs; let diff = (zX[i + 1] - zX[i]) as i64; ans += term * Mint::new(diff); } std::mem::swap(&mut rX, &mut rY); std::mem::swap(&mut zX, &mut zY); } for _ in 0..n { ans *= Mint::new(4); } let out = (ans * Mint::new(2)).val(); println!("{}", out); }