题目描述

平面直角坐标系上有 $n$ 个矩形，其中第 $i$ 个的左上角坐标为 $(x_{i,1},y_{i,1})$，右下角坐标为 $(x_{i,2},y_{i,2})$。

对于 $k \in[1,n]$，求解在 $n$ 个矩形中随机选取 $k$ 个不同的矩形，其所有覆盖部分的并集的面积的期望值，答案对 $998244353$ 取模。

输入格式

第一行包含 个正整数 $n$（$1\le n \le 2\times10^3$ ）。

之后 $n$ 行，每行给定四个参数 $x_{i,1},y_{i,1},x_{i,2},y_{i,2}$ ，保证有 $1\le x_{i,1}\lt x_{i,2}\le10^9,1\le y_{i,1} \lt y_{i,2} \le 10^9$。

输出格式

输出共 行，第 $i$ 行输出 $1$ 个整数，表示 $k=i$ 时的答案。

输入样例

3
1 1 2 2
3 3 4 4
1 1 4 4

输出样例

665496239
665496242
9