#P18742. [正睿NOI2021训练] 第四题

[正睿NOI2021训练] 第四题

第四题

平面上有 nn 个点,第 ii 个点为 (xi,yi)(x_i,y_i)。

对于每个点,求它到其余所有点的欧几里得距离之积的平方,对 998244353998244353 取模。即输出

$$\prod_{j\ne i}\bigl((x_i-x_j)^2+(y_i-y_j)^2\bigr)\pmod{998244353}.$$

这里的距离是通常实数平面上的欧几里得距离;先将距离之积平方后得到整数,再取模。允许给定点重合。

输入格式

第一行一个正整数 nn;接下来 nn 行,每行两个整数 xi,yix_i,y_i。

输出格式

输出 nn 行,每行一个整数,表示对应点的答案。

数据范围

2≤n≤1000002\le n\le100000,0≤xi,yi<9982443530\le x_i,y_i<998244353。

样例 1

输入

2
0 0
3 4

输出

25

25