并

Problem Description

平面直角坐标系上有 $n$ 个矩形，其中第 $i$ 个的左上角坐标为 $(x_{i,1},y_{i,1})$，右下角坐标为 $(x_{i,2},y_{i,2})$。 对于 $k \in [1,n]$，求解在 $n$ 个矩形中随机选取 $k$ 个不同的矩形，其所有覆盖部分的并集的面积的期望值，答案对 $998244353$ 取模。

Input

第一行包含 $1$ 个正整数 $n$ （$1 \leq n \leq 2 \times 10^3$）。 之后 $n$ 行，每行给定四个参数 $x_{i,1},y_{i,1},x_{i,2},y_{i,2}$，保证有 $1 \leq x_{i,1} < x_{i,2} \leq 10^9,1 \leq y_{i,1} < y_{i,2 }\leq 10^9$。

Output

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

Sample Input

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

Sample Output

665496239
665496242
9

Source

2024“钉耙编程”中国大学生算法设计超级联赛（1）