The great mage Xiao L, a chunibyo patient, has created $n$ magic crystal balls, each possessing energy values for three attributes: water, fire, and earth. Xiao L arranges these $n$ crystal balls in a row on the ground from front to back and begins today's magic performance.

We denote $A_i$, $B_i$, and $C_i$ as the water, fire, and earth energy values of the $i$-th crystal ball (1-indexed) from front to back, respectively.

Xiao L plans to perform $m$ magic spells. Each time, he chooses an interval $[l, r]$ and performs one of 7 types of magic across three categories:

1. Magic Excitation: Causes a specific attribute of energy in each crystal ball within the interval to burst, thereby enhancing another specific attribute of energy. Specifically, there are three possible forms:

   • Fire element excites water element energy: $A_i = A_i + B_i$.
   • Earth element excites fire element energy: $B_i = B_i + C_i$.
   • Water element excites earth element energy: $C_i = C_i + A_i$.

   Note that enhancing one attribute's energy does not change the energy of another attribute; for example, $A_i = A_i + B_i$ does not increase or decrease $B_i$.

2. Magic Enhancement: Xiao L waves his staff, consuming $v$ points of his own mana to change the energy of a specific attribute for each crystal ball in the interval. Specifically, there are three possible forms:

   • Fire element constant enhancement: $A_i = A_i + v$.
   • Water element doubling enhancement: $B_i = B_i \cdot v$.
   • Earth element absorption fusion: $C_i = v$.

3. Magic Release: Xiao L gathers the energy of all crystal balls in the interval and fuses them into a new crystal ball, which is then given to the audience. The energy value of each attribute in the generated crystal ball is the algebraic sum of the corresponding energy values of all crystal balls in the interval. Note that the process of magic release does not actually change the energy of the crystal balls in the interval.

It is worth mentioning that the raw materials for the crystal balls manufactured and fused by Xiao L are custom-made OI factory crystals, so these crystal balls have an energy threshold of $998244353$. When the energy value of an attribute in a crystal ball is greater than or equal to this threshold, the energy value is automatically taken modulo the threshold to prevent the crystal ball from exploding.

Xiao W, as Xiao L's (only) audience, watched the entire performance and received every crystal ball fused by Xiao L during the show. Xiao W wants to know the energy values of the three attributes contained in these crystal balls.

Input

The 7 types of magic are defined as follows:

• 1: $A_i = A_i + B_i$
• 2: $B_i = B_i + C_i$
• 3: $C_i = C_i + A_i$
• 4: $A_i = A_i + v$
• 5: $B_i = B_i \times v$
• 6: $C_i = v$
• 7: Crystal ball fusion

The first line of input contains an integer $n$ $(1\le n\le 2.5 \times 10^{5})$, representing the number of crystal balls.

The next $n$ lines each contain 3 space-separated integers, where the three numbers in the $i$-th line represent $A_i, B_i, C_i$ respectively.

The next line contains an integer $m$ $(1\le m\le 2.5 \times 10^{5})$, representing the number of magic spells performed.

The next $m$ lines each contain 3 or 4 numbers in the format opt l r (v). Here, opt is the magic number, and $l, r$ represent the interval where the magic is performed (guaranteed $l \le r$). Specifically, if magic types 4 to 6 (Magic Enhancement) are performed, there is an additional integer $v$, representing the mana consumed by Xiao L.

Output

For each magic type 7 (Magic Release), output a single line containing 3 space-separated integers a b c, representing the water, fire, and earth energy values of the fused crystal ball, respectively.

Examples

Input 1

2
2 3 3
6 6 6
4
7 1 2
1 1 2
4 1 2 3
7 1 2

Output 1

8 9 9
23 9 9

Note

The following shows the energy in the two crystal balls after each magic spell:

(2, 3, 3) (6, 6, 6)
(5, 3, 3) (12, 6, 6)
(8, 3, 3) (15, 6, 6)
(8, 3, 3) (15, 6, 6)

Subtasks

For 100% of the data, $n, m \le 2.5 \times 10^{5}$, $0 \le A_i, B_i, C_i, v < 998,244,353$.

1. 10% of the data: $n \times m \le 10^7$.
2. Another 10% of the data: every magic interval is $[1, n]$.
3. Another 10% of the data: every non-query magic interval is $[1, n]$, and all modifications occur before any queries.
4. Another 10% of the data: $opt \in \{4, 5, 6, 7\}$.
5. Another 15% of the data: $opt \in \{1, 2, 7\}$.
6. Another 15% of the data: $opt \in \{1, 2, 3, 5, 7\}$.
7. Another 15% of the data: $n, m \le 10^5$.
8. Remaining data: no special conditions.

Note: Please pay attention to the memory limit of this problem and handle your program's memory consumption appropriately.