Tactics

Ray is a player of the character collection game 'Blue Storage'. Today Ray is again practicing boss time attacks to get a high ranking. To defeat a boss faster than other players, one has to pull many strong characters, but Ray is a broke college student and could not pull many. Instead, Ray tries to set a good record by combining tactics, various strategies that can attack a boss efficiently.

Ray searched the game community overnight and found $N$ tactics in total. The $i$-th tactic succeeds with probability $\dfrac{p_i}{q_i}$ and fails with probability $1-\dfrac{p_i}{q_i}$. Tactics are executed in order. Ray's boss time attack score increases by $G_i$ if the $i$-th tactic succeeds and decreases by $L_i$ if it fails.

Let $X$ be Ray's score after all tactics are executed. If $X$ is positive, Ray gains $X^{2}$ units of inner peace and plays the game harder. If $X$ is negative, Ray takes $X^{2}$ units of stress and becomes more likely to quit the game. Compute the inner peace and stress information Ray gets.

The first line contains the number of tactics $N$. ($1 \leq N \leq 40$)

From the second line onward, the next $N$ lines each contain four integers $p_i$, $q_i$, $G_i$, and $L_i$, separated by spaces. $p_i$ and $q_i$ give the success probability of the $i$-th tactic, $G_i$ is the points gained on success, and $L_i$ is the points lost on failure. ($1 \leq p_i < q_i \leq 10^{7}$, $1 \leq G_i, L_i \leq 10^{7}$)

All given numbers are integers. The tactics are given in the order in which they are executed.

On the first line, print the probability $P_1 \bmod 998244353$ that Ray gets inner peace after all tactics are executed, followed by the average $E_1 \bmod 998244353$ of the inner peace value when Ray gets it.

On the second line, print the probability $P_2 \bmod 998244353$ that Ray gets stress after all tactics are executed, followed by the average $E_2 \bmod 998244353$ of the stress value when Ray gets it.

Only inputs where $P_1 \bmod 998244353$ and $P_2 \bmod 998244353$ are not $0$ are given.

For a fraction $\dfrac{p}{q}$, $\dfrac{p}{q} \bmod 998244353$ is the integer $u$ with $0 \le u < 998244353$ that satisfies $qu \equiv p \pmod{998244353}$. The integer $u$ is guaranteed to exist and be unique for every value to print.