DotA Practice Simulation

In this problem, ZhenZhen is practicing a game called DotA (Defense of the Algorithm) where he controls a hero named Faceless with two skills:

• Lock: He chooses an enemy unit with index \(id\). If that enemy is alive (its health is at least 1), then with probability \(p\) the enemy suffers 1 damage (i.e. its health reduces by 1). If the enemy is already dead, the skill has no effect.
• Barrier: He chooses \(k\) enemy units (by indices). Due to his poor skill with this ability, he will hit exactly one enemy among those that are still alive. The probability to hit each alive enemy in the chosen set is equal. (If all the chosen enemies are already dead, the barrier skill does nothing.)

An enemy dies once its health becomes 0 or less. Initially, there are \(n\) enemy units, and the \(i\)th enemy has \(h_i\) health.

ZhenZhen will cast \(Q\) skills in sequence. Some skills are Lock skills and some are Barrier skills. GreenGreen, who is watching the practice, wants to know:

1. For each Barrier skill cast, what is the probability that each enemy unit is hit by that particular skill? (For enemy units that are not targeted by that skill, the probability is 0.)
2. After all \(Q\) skills have been cast, what is the expected remaining health for each enemy unit?

All probabilities and expected values should be output as integers modulo \(998244353\). In particular, if you have a rational number \(\frac{a}{b}\) as the answer, you should output \(a \cdot b^{-1}\) modulo \(998244353\), where \(b^{-1}\) is the modular inverse of \(b\) modulo \(998244353\).

Input Format:

The first line contains two integers \(n\) and \(Q\) (\(1 \le n, Q \le 10\)).

The second line contains \(n\) integers \(h_1, h_2, \ldots, h_n\) \( (1 \le h_i \le 10)\), the initial healths of the enemies.

Then \(Q\) lines follow, each describing a skill in the order cast. Each line begins with an integer t indicating the type of the skill.

• If \(t = 1\) (Lock skill), the line contains three integers: 1 id p where \(id\) (1-indexed) is the enemy to target and \(p\) (\(0 \le p \lt 998244353\)) is the probability (given modulo \(998244353\)) that the lock skill deals damage.
• If \(t = 2\) (Barrier skill), the line begins with 2 k indicating that \(k\) enemies are to be targeted, followed by \(k\) distinct integers (1-indexed) identifying the enemies.

Output Format:

For each Barrier skill (in the order they appear), output a line with \(n\) space‐separated integers. For an enemy that is not among the \(k\) targeted by that skill, output 0. For a targeted enemy, output the probability that it is hit by that Barrier skill (in modulo \(998244353\) arithmetic).

Then, output one more line with \(n\) space‐separated integers, where the \(i\)th number is the expected remaining health of enemy \(i\) (modulo \(998244353\)) after all skills have been cast.

Note on the Barrier Skill: Suppose a Barrier skill targets a set \(S\) and at the time of casting there are \(r\) enemies in \(S\) that are alive. Then the skill will hit exactly one enemy, and each alive enemy in \(S\) will be hit with probability \(\frac{1}{r}\) (if \(r > 0\)).

Modular Inverse Reminder: For any integer \(b\) with \(\gcd(b,998244353)=1\), its modular inverse \(b^{-1}\) satisfies \(b \cdot b^{-1} \equiv 1 \pmod{998244353}\).

inputFormat

The input begins with two integers \(n\) and \(Q\). The next line contains \(n\) integers \(h_1, h_2, \ldots, h_n\). Then, there are \(Q\) lines each describing a skill cast. For a lock skill, the line is formatted as 1 id p. For a barrier skill, the line is formatted as 2 k id_1 id_2 ... id_k.

outputFormat

For each barrier skill (in the order they appear in the input), print a line with \(n\) space‐separated integers denoting the probabilities that enemy \(i\) is hit by that barrier skill (0 for enemies not targeted). Then, print one more line with \(n\) space‐separated integers, where the \(i\)th integer is the expected remaining health (modulo \(998244353\)) of enemy \(i\) after all skills have been cast.

sample

2 2
2 1
1 1 499122177
2 2 1 2

499122177 499122177
1 499122177

</p>