Zhenzhen is a good friend of Lvlv.

Description

Zhenzhen likes to play a game called DotA (Defense of the Algorithm), in which Zhenzhen controls his hero to fight against another team with his teammates.

In DotA, Zhenzhen's favorite hero is Faceless, who has two skills: Lock: Used on a specified enemy unit, it deals 1 point of damage to that unit with probability $p$ (reducing its health by 1). Chronosphere: Casts a field in an area, rendering all other units within that area unable to move.

In the game, if a unit's health drops to 0 or below, that unit dies.

Zhenzhen's skill in controlling Faceless is average, so he decides to practice diligently. There are $n$ enemy units (numbered from 1 to $n$), and the enemy unit numbered $i$ has $h_i$ health points. Zhenzhen has already arranged a practice plan, and he will cast $Q$ skills in sequence: For the Lock skill: Zhenzhen specifies an enemy unit $id$ and casts the skill on it. Since there are many factors determining the probability coefficient $p$, the value of $p$ may be different each time. Specifically, if the enemy unit is already dead, this skill will have no effect. For the Chronosphere skill: Zhenzhen wishes to cast it on $k$ specified enemy units, but because he is not proficient in casting this skill, he can only hit exactly 1 enemy unit. The probability of hitting each alive enemy unit is equal (which means already dead enemy units have no effect). Specifically, if all $k$ enemy units are already dead, this skill will not hit any enemy unit.

Now, Lvlv, who is watching Zhenzhen practice, wants to know: 1. For each Chronosphere skill cast by Zhenzhen, what are the probabilities of it hitting each enemy? 2. After all of Zhenzhen's skills have been cast, what is the expected remaining health of each enemy unit?

Since Lvlv still needs to watch Zhenzhen's training, please help him solve these two problems.

To avoid precision errors, for all values that need to be output, please output their values modulo $998,244,353$.

Since Chronosphere is Faceless's ultimate skill, the number of times Zhenzhen casts this skill will not be too large. Please refer to the [Subtasks] section for details.

Input

• The first line contains a positive integer $n$, representing the number of enemy units.
• The second line contains $n$ positive integers $m_1, \dots, m_n$, representing the initial health of each enemy unit.
• The third line contains a non-negative integer $Q$, representing the number of skills Zhenzhen casts.
• From the 4th line to the $Q+3$-th line, each line describes a skill, with the $i+3$-th line describing the $i$-th skill.
  • The beginning of each line is an integer $op$, representing the type of the skill.
  • If $op = 0$, it represents the Lock skill. It is followed by 3 positive integers $id, u, v$, representing the target of the skill as $id$, and the probability of the skill hitting as $p = \frac{u}{v}$. (Guaranteed $1 \le id \le n$, $0 < u \le v < 998,244,353$)
  • If $op = 1$, it represents the Chronosphere skill. It is followed by a positive integer $k$ representing the number of targets, followed by $k$ additional numbers $id_1, \dots, id_k$ describing all targets of the skill. (Guaranteed all $1 \le id_i \le n$ are distinct)

For each line, if it contains multiple numbers, they are separated by single spaces.

Output

Output $C + 1$ lines (where $C$ is the number of Chronosphere skills): The first $C$ lines correspond to each Chronosphere skill in order. For each line: Output $k$ numbers, where the $i$-th number represents the probability that the Chronosphere hits enemy unit $id_i$. * The $(C+1)$-th line outputs $n$ numbers, where the $i$-th number represents the expected remaining health of enemy unit $i$ after all skills have been cast.

For each line, if it contains multiple numbers, they are separated by single spaces.

For all values, please output their results modulo $998,244,353$: that is, if the answer is in the form of an irreducible fraction $\frac{a}{b}$, where $a$ and $b$ are coprime, output an integer $x$ such that $bx \equiv a \pmod{998244353}$ and $0 \le x < 998244353$. (It can be proven that such an integer $x$ is unique.)

Examples

Input 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 1

1
0
499122177 0 499122177
1 0 2

Note 1

Zhenzhen casts the following skills in order: 1. Cast Lock on enemy unit 2: deals 1 damage with probability 1. At this point, enemy unit 2 must have 1 health remaining. 2. Cast Chronosphere on enemy unit 2: (Since enemy unit 2 is still alive,) it must hit unit 2. 3. Cast Lock on enemy unit 2: deals 1 damage with probability 1. 4. Cast Lock on enemy unit 3: deals 1 damage with probability 1. At this point, the health of the three enemy units must be 1, 0, 2 respectively, and enemy unit 2 must be dead. 5. Cast Chronosphere on enemy unit 2: (Since enemy unit 2 is already dead,) it must not hit any unit. 6. Cast Chronosphere on enemy units 1, 2, 3: the probability of hitting enemy units 1 and 3 is equal, i.e., $\frac{1}{2}$ each. Finally, the remaining health of the three enemy units is 1, 0, 2.

Input 2

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

Output 2

249561089 748683265
804141285 887328314 305019108
1 499122177 332748118

Note 2

Analysis of each Chronosphere skill: 1. The 1st Chronosphere (targets are enemy units 1, 2): The probability that unit 2 is alive is $\frac{1}{2}$, and unit 1 is definitely alive. If unit 2 is alive, the probability of the Chronosphere hitting 1 or 2 is equal, both $\frac{1}{2}$; if unit 2 is dead, the Chronosphere must hit unit 1. Therefore: the probability of hitting unit 1 is $\frac{1}{2} \times 1 + \frac{1}{2} \times \frac{1}{2} = \frac{3}{4}$; the probability of hitting unit 2 is $\frac{1}{2} \times 0 + \frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$. 2. The 2nd Chronosphere (targets are enemy units 1, 2, 3): The probabilities of the three enemy units being alive are $1, \frac{1}{2}, \frac{1}{3}$. The probability that 1, 2, 3 are all alive is $\frac{1}{6}$; the probability that only 1, 2 are alive is $\frac{1}{3}$; the probability that only 1, 3 are alive is $\frac{1}{6}$; the probability that only 1 is alive is $\frac{1}{3}$. Therefore: the 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}$; the probability of hitting unit 2 is $\frac{1}{6} \times \frac{1}{3} + \frac{1}{3} \times \frac{1}{2} = \frac{2}{9}$; the probability of hitting unit 3 is $\frac{1}{6} \times \frac{1}{3} + \frac{1}{6} \times \frac{1}{2} = \frac{5}{36}$. Finally, the expected remaining health of the three enemy units is $1, \frac{1}{2}, \frac{1}{3}$.

Subtasks

We denote $C$ as the number of Chronosphere skills.

For all test cases, it is guaranteed that $n \le 200$, $Q \le 200,000$, $C \le 1000$, $m_i \le 100$.

Note

1. The 3rd example satisfies the data scale constraints of test case 1.
2. The 4th example satisfies the constraint "All $p$ are equal".
3. The last digit of $Q$ can help you quickly determine the test case ID.
4. The order of test cases may not be related to difficulty.