Problem Background

Zhenzhen is a good friend of Lvlv.

Problem Description

Zhenzhen enjoys playing a game called DotA (Defense of the Algorithm), where he controls his hero alongside teammates to battle against another team. Zhenzhen's favorite hero in DotA is called Faceless, who has two skills:

• Lock: Used on a specified enemy unit, with a probability \( p \) of inflicting 1 point of damage (reducing the unit's health by 1).
• Barrier: Casts a barrier in an area, immobilizing all other units within it.

In the game, a unit dies if its health drops to 0 or below.

Zhenzhen, being average at controlling Faceless, decides to practice diligently. There are \( n \) enemy units (numbered from 1 to \( n \)), with unit \( i \) having \( h_i \) health points.

Zhenzhen has planned a sequence of \( Q \) skills to practice:

• For the Lock skill: Zhenzhen will target a specific enemy unit \( id \) and cast it. Due to various factors determining the probability coefficient \( p \), \( p \) may vary each time. Specifically, if the targeted unit is already dead, the skill will have no effect.
• For the Barrier skill: Zhenzhen aims to cast it on \( k \) specified enemy units, but due to his inexperience, he can only hit exactly one unit. The probability of hitting each living enemy unit is equal (dead units have no effect). Specifically, if all \( k \) units are already dead, the skill will not hit any unit.

Now, Lvlv, who is watching Zhenzhen practice, wants to know:

1. For each Barrier skill Zhenzhen casts, what are the probabilities of it hitting each enemy?
2. After all skills are cast, what are the expected remaining health values for all enemy units?

To avoid precision errors, for all numerical outputs, please provide the values modulo \( 998244353 \).

Since Barrier is Faceless' ultimate skill, Zhenzhen won't cast it too frequently. See "Subtasks" for details.

Input Format

The first line contains a positive integer \( n \), the number of enemy units.
The second line contains \( n \) positive integers \( m_1, \cdots, m_n \), indicating the initial health values of each enemy unit.
The third line contains a non-negative integer \( Q \), the number of skills Zhenzhen will cast.
Lines 4 to \( Q + 3 \) describe each skill, with line \( i + 3 \) describing the \( i \)-th skill.

Each line starts with an integer \( op \), indicating the skill type.
If \( op = 0 \), it represents the Lock skill, followed by 3 positive integers \( id, u, v \), meaning the target is \( id \) and the hit probability is \( p = \frac{u}{v} \) (guaranteed \( 1 \le id \le n, 0 < u \le v < 998244353 \)).
If \( op = 1 \), it represents the Barrier skill, followed by a positive integer \( k \) indicating the number of targets, and then \( k \) numbers \( id_1, \cdots, id_k \) specifying all targets (guaranteed all \( 1 \le id_i \le n \) are distinct). Numbers within a line are separated by a single space.

Output Format

Output consists of \( C + 1 \) lines (where \( C \) is the number of Barrier skills):

The first \( C \) lines correspond to each Barrier skill:

• Output \( k \) numbers, the \( i \)-th number being the probability of the Barrier hitting enemy unit \( id_i \).

The \( C + 1 \)-th line outputs \( n \) numbers, the \( i \)-th number being the expected remaining health of enemy unit \( i \) after all skills are cast.

For each line, if it contains multiple numbers, separate them with a single space.

For all numerical values, output their modulo \( 998244353 \) result: if the answer in simplest fractional form is \( \frac{a}{b} \) where \( a \) and \( b \) are coprime, output integer \( x \) such that \( bx \equiv a \mod 998244353 \) and \( 0 \le x < 998244353 \). (It can be proven that such an integer \( x \) is unique.)

Sample Input and Output

Input Sample #1

3
1 2 3
6
0 2 1 1
1 1 2
0 2 1 1
0 3 1 1
1 1 2
1 3 1 2 3

Output Sample #1

1
0
499122177 0 499122177
1 0 2

Input Sample #2

3
1 1 1
4
0 2 1 2
1 2 1 2
0 3 2 3
1 3 1 2 3

Output Sample #2

249561089 748683265
804141285 887328314 305019108
1 499122177 332748118

Notes

Sample Explanation 1

Zhenzhen casts the following skills in order:

1. Lock on enemy unit 2: Hits with probability 1, reducing its health to 1.
2. Barrier on enemy unit 2: (Since unit 2 is still alive,) it must hit unit 2.
3. Lock on enemy unit 2: Hits with probability 1, reducing its health to 0.
4. Lock on enemy unit 3: Hits with probability 1, reducing its health to 2.
5. Barrier on enemy unit 2: (Since unit 2 is dead,) it hits no unit.
6. Barrier on enemy units 1, 2, 3: Hits units 1 and 3 with equal probability, each \( \frac{1}{2} \).

Ultimately, the remaining health values of the three enemy units are guaranteed to be 1, 0, 2.

Sample Explanation 2

For each Barrier skill analysis:

1. First Barrier (targets enemy units 1, 2):
   - Unit 2 survives with probability \( \frac{1}{2} \), unit 1 is guaranteed to survive.
   - If unit 2 survives, the Barrier hits 1 or 2 with equal probability \( \frac{1}{2} \); if unit 2 dies, it must hit unit 1.
   - Thus: Probability of hitting unit 1 is \( \frac{1}{2} \times 1 + \frac{1}{2} \times \frac{1}{2} = \frac{3}{4} \); hitting unit 2 is \( \frac{1}{2} \times 0 + \frac{1}{2} \times \frac{1}{2} = \frac{1}{4} \).

2. Second Barrier (targets enemy units 1, 2, 3):
   - Survival probabilities for units 1, 2, 3 are \( 1, \frac{1}{2}, \frac{1}{3} \).
   - Probabilities of simultaneous survival: \( \frac{1}{6} \) for all three; \( \frac{1}{3} \) for only 1 and 2; \( \frac{1}{6} \) for only 1 and 3; \( \frac{1}{3} \) for only 1.
   - Thus: Probability of hitting unit 1 is \( \frac{1}{6} \times \frac{1}{3} + (\frac{1}{3} + \frac{1}{6}) \times \frac{1}{2} + \frac{1}{3} \times 1 = \frac{23}{36} \); hitting unit 2 is \( \frac{1}{6} \times \frac{1}{3} + \frac{1}{3} \times \frac{1}{2} = \frac{2}{9} \); hitting unit 3 is \( \frac{1}{6} \times \frac{1}{3} + \frac{1}{6} \times \frac{1}{2} = \frac{5}{36} \).

Ultimately, the expected remaining health values for the three enemy units are \( 1, \frac{1}{2}, \frac{1}{3} \).

Data Range

We denote \( C \) as the number of Barrier skills.

For all test cases, \( n \le 200, Q \le 200000, C \le 1000, m_i \le 100 \).

Hints

The last digit of \( Q \) can help you quickly identify the test case number.
The order of test cases may not reflect their difficulty.

Thanks to @Izumi Shizuka for providing the problem statement.

见题面 Input 部分

见题面 Output 部分