Description

有一天建國中學的中餅在大掃除時意外發現了「中卷遊戲」的入場券,於是他與國中同學中明一同前往中巨蛋觀看比賽。
中餅和中明從主持人口中得知總共有 $n$ 個參賽者,編號為 $1\sim n$,編號 $i$($1\leq i\leq n$) 的參賽者養了 $m_i$ 隻中卷,這些中卷因為有中二病,所以會魔法,第 $j$($1\leq j\leq m_i$)隻中卷的魔力值為 $a_{i,j}$。

在整個「中卷遊戲」中會有 $q$ 次決鬥,每次決鬥會由編號 $x$ 與編號 $y$ 的參賽者對戰($x\neq y$)。
編號 $x$ 的參賽者會從 $m_x$ 隻中卷裡挑出一隻中卷,每隻被挑到的機率都是 $\frac{1}{m_x}$;編號 $y$ 的參賽者則會從 $m_y$ 隻中卷裡挑出一隻,每隻被挑到的機率是 $\frac{1}{m_y}$。

若參賽者 $x,y$ 分別挑出了魔力值為 $A,B$ 的中卷,那這兩隻中卷會進行魔力的比拼,如果 $A>B$,代表參賽者 $x$ 的中卷比較會魔法,那這輪參賽者 $x$ 獲勝,否則為平手或參賽者 $x$ 落敗。
所謂贏了有獎金,沒贏沒獎金,若此次決鬥參賽者 $x$ 獲勝了,那他能獲得 $\frac{B}{A}$ 元的獎金,否則獲得 $0$ 元。

中餅因為覺得比賽太無聊了,所以想計算每次決鬥參賽者 $x$ 能拿到獎金的期望值 $E$ 是多少,請在每次的決鬥,輸出 $E\text{ mod }998244353$。

若 $E$ 化成最簡分數為 $\frac{P}{Q}$,那麼輸出 $E\text{ mod }998244353$ 代表要輸出 $PQ^ {-1}\text{ mod }998244353$($Q^ {-1}$ 為 $Q$ 的模逆元,滿足 $QQ^ {-1}≡1\ (\text{mod }998244353)$)。
保證 $E$ 為有理數,且不會出現 $Q≡0\ (\text{mod }998244353)$ 的情況。

Input Format

第一行有兩個正整數 $n,q$,代表參賽者數量與有幾次決鬥。
接下來 $n$ 行,第 $i$ 行的第一個正整數為 $m_i$,代表編號 $i$ 的參賽者養了幾隻中卷,同一行接著會有 $m_i$ 個正整數 $a_{i,1}\sim a_{i,m_i}$,代表每隻中卷的魔力值。
接下來 $q$ 行,每行有兩個正整數 $x,y$,代表此次決鬥的參賽者編號。

對於所有測試資料:

  • $2\leq n\leq 10^ 5$
  • $1\leq q\leq 10^ 5$
  • $1\leq m_i\leq 10^ 5$
  • $\sum\limits_{i=1}^ n m_i\leq 2\times 10^ 5$
  • $1\leq a_{i,j}< 998244353$
  • $1\leq x,y\leq n,x\neq y$

Output Format

每次決鬥,輸出參賽者 $x$ 能拿到獎金的期望值 $E\text{ mod }998244353$。

Sample Input 1

2 2
2 3 1
3 2 2 1
1 2
2 1

Sample Output 1

610038216
166374059

Sample Input 2

4 12
5 15 6 9 5 12
5 13 15 10 9 16
6 1 14 5 14 3 8
4 7 13 15 2
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

Sample Output 2

471836831
677881860
641371997
736862175
89482937
679206098
201431450
979230175
731996343
845070522
174820742
2513894

Hints

在範例測資一中,第一次決鬥 $x=1,y=2$,參賽者 $1$ 可以拿到獎金的期望值 $E$ 為 $\frac{5}{18}$,$5\times 18^ {-1}\equiv 5\times 720954255\equiv 610038216\ (\text{mod }998244353)$,故輸出 $610038216$。

第二次決鬥 $x=2,y=1$,參賽者 $2$ 可以拿到獎金的期望值 $E$ 為 $\frac{1}{6}$,
$6^ {-1}\equiv 166374059\ (\text{mod }998244353)$,故輸出 $166374059$。

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~6 $m_i\leq 10$ 21
3 0, 2, 7~9 $q\leq 10$ 28
4 0~50 無其他限制 51

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 524288 65536 1 2 3 4
1 3000 524288 65536 1 2 4
2 3000 524288 65536 2 3 4
3 3000 524288 65536 2 4
4 3000 524288 65536 2 4
5 3000 524288 65536 2 4
6 3000 524288 65536 2 4
7 3000 524288 65536 3 4
8 3000 524288 65536 3 4
9 3000 524288 65536 3 4
10 3000 524288 65536 4
11 3000 524288 65536 4
12 3000 524288 65536 4
13 3000 524288 65536 4
14 3000 524288 65536 4
15 3000 524288 65536 4
16 3000 524288 65536 4
17 3000 524288 65536 4
18 3000 524288 65536 4
19 3000 524288 65536 4
20 3000 524288 65536 4
21 3000 524288 65536 4
22 3000 524288 65536 4
23 3000 524288 65536 4
24 3000 524288 65536 4
25 3000 524288 65536 4
26 3000 524288 65536 4
27 3000 524288 65536 4
28 3000 524288 65536 4
29 3000 524288 65536 4
30 3000 524288 65536 4
31 3000 524288 65536 4
32 3000 524288 65536 4
33 3000 524288 65536 4
34 3000 524288 65536 4
35 3000 524288 65536 4
36 3000 524288 65536 4
37 3000 524288 65536 4
38 3000 524288 65536 4
39 3000 524288 65536 4
40 3000 524288 65536 4
41 3000 524288 65536 4
42 3000 524288 65536 4
43 3000 524288 65536 4
44 3000 524288 65536 4
45 3000 524288 65536 4
46 3000 524288 65536 4
47 3000 524288 65536 4
48 3000 524288 65536 4
49 3000 524288 65536 4
50 3000 524288 65536 4