注意

この問題の実行時間制限は $6$ 秒です。

問題文

$X=10^{10^{100}}$ とします。以下の条件を全て満たす根付き木が一意に存在することが証明できます。この木を $T$ とします。

• 各頂点には $1$ 以上 $X$ 以下の整数値が $1$ つずつ書き込まれており、根に書き込まれた値は $1$ (複数の頂点に同じ値が書き込まれていてもよい)
• 任意の頂点 $u$ について、 $u$ を根とする根付き部分木( $u$ 自身も含む)に含まれる $1$ つ以上の頂点に書き込まれた整数全体の集合を $S$ とし、 $u$ に書き込まれた整数を $x$ とすると、$S=\{mx|1\le m\le \lfloor \frac{X}{x}\rfloor\}$ が成り立つ。 すなわち、 $x$ が書き込まれた頂点を根とする根付き部分木には、$1$ 以上 $X$ 以下の全ての $x$ の倍数が一度以上現れ、他の値は一度も現れない。
• 上の $2$ つの条件を全て満たす木の中で、頂点数が最小である。

$2$ 頂点の組 $(u,v)$ に対して、$u$ と $v$ を結ぶ $T$ 上の唯一の単純パスに含まれる頂点全て($u,v$ 自身を含む)にわたる、 書き込まれた整数の最小値を $\operatorname{score}(u,v)$ と表します。

整数 $A,B$ があります。ここで $A,B$ は素因数分解した形で与えられ、 $A=\prod\limits_{i=1}^N p_i^{\alpha _i},B=\prod\limits_{j=1}^M q_j^{\beta _j}$ ($p_i,q_j$ は素数)です。 整数 $A$ が書き込まれた $T$ の頂点全体の集合を $U$ 、整数 $B$ が書き込まれた $T$ の頂点全体の集合を $V$ とするとき、 $\sum\limits_{u\in U}\sum\limits_{v\in V} \operatorname{score}(u,v)$ を $998244353$ で割ったあまりを求めてください。

制約

• $1 \le N,M \le 10^5$
• $1 \le p_i,q_j\le 10^9 (1\le i\le N, 1\le j\le M)$
• $p_i,q_j$ は素数 $(1\le i\le N, 1\le j\le M)$
• $p_{i_1}\ne p_{i_2} (1\le i_1 < i_2\le N)$
• $q_{j_1}\ne q_{j_2} (1\le j_1 < j_2\le M)$
• $1 \le \alpha_i,\beta_j (1\le i\le N, 1\le j\le M)$
• $\sum\limits_{i=1}^N \alpha_i, \sum\limits_{j=1}^M \beta_j \le 10^5$
• 入力は全て整数

入力

入力は次の形式で与えられます。

$N\ M$
$p_1\ \alpha_1$
$\vdots$
$p_N\ \alpha_N$
$q_1\ \beta_1$
$\vdots$
$q_M\ \beta_M$

出力

答えを $1$ 行に出力してください。最後に改行してください。

サンプル

サンプル1

入力

2 1
2 1
3 1
2 3

出力

3

$A=2^1\cdot 3^1=6,B=2^3=8$ です。$T$ のうち $8$ 以下の値が書かれた頂点を含む部分を抜き出すと図のようになります。 図のように $6$ が書かれた頂点に $u_1,u_2$ 、$8$ が書かれた頂点に $v_1$ と名前をつけると、 $\operatorname{score}(u_1,v_1)=2,\operatorname{score}(u_2,v_1)=1$ であるので、答えは $3$ です。

2 2
2 3
3 1
3 2
2 2

77

3 4
611951 20000
350377 30000
882377 40000
104729 10000
287117 60000
415087 10000
746773 10000

923860980