At the Misty Lake, where the cold wind howls, Cirno is chasing a frog.

The frog will perform $n$ operations in sequence: jumping over a line, where the starting point and landing point are symmetric with respect to the line; or rotating around a point by a certain angle.

Cirno will cast $q$ spells:

A. "Perfect Freeze" spell: Queries the final position of a frog after it starts at a point and jumps through a sequence of lines and points in a given range.

B. "Great Crusher" spell: Reflects all lines and points in a given range across a specified line.

C. "Hailstorm" spell: Rotates all lines and points in a given range around a specified point by a certain angle.

Cirno's math is so good that she cannot describe these operations clearly. Therefore, she asked Yakumo Ran to provide a formal description below.

In short, please predict the final position of the frog for each type A spell. Since Cirno cannot understand numbers greater than 9, you should output the result modulo $998244353$ to confuse her.

There are some symmetry and rotation operations in analytic geometry.

To describe these two transformations clearly, we define a function $f(A, B)$. Here, $A$ is a tuple representing the coordinates of a point $(x, y)$, and $B$ is either a triple or a quintuple.

If $B$ is a triple $(a, b, c)$, then $f(A, B)$ returns the point symmetric to $(x, y)$ with respect to the line $ax + by + c = 0$.

If $B$ is a quintuple $(x_0, y_0, a, b, c)$, then $f(A, B)$ returns the coordinates of $(x, y)$ after a counter-clockwise rotation by $\theta$ around the point $(x_0, y_0)$, where $\sin\theta = \frac{a}{c}$ and $\cos\theta = \frac{b}{c}$, with the guarantee that $a^2 + b^2 = c^2$.

Analytic geometry also involves operations such as reflecting a line across another line. To describe this, we define $g(A, B)$:

If $A$ is a quintuple $(x_0, y_0, a, b, c)$, we calculate $(x_0', y_0') = f((x_0, y_0), B)$ and return the new quintuple $(x_0', y_0', a, b, c)$.

If $A$ is a triple $(a, b, c)$, we return a triple $(a', b', c')$ such that $\{(x, y) \mid a'x + b'y + c' = 0\} = \{f((x, y), B) \mid ax + by + c = 0\}$. It can be proven that such $a', b', c'$ always exist.

Now, there is a sequence $A_i$ of length $n$, where each element is either a triple or a quintuple. There are three types of operations:

Given $x, y, l, r$, query $f(f(\dots f((x, y), A_l) \dots, A_{r-1}), A_r)$.

Given $a, b, c, l, r$, update $A_i$ to $g(A_i, (a, b, c))$ for all $l \le i \le r$.

Given $x_0, y_0, a, b, c, l, r$, update $A_i$ to $g(A_i, (x_0, y_0, a, b, c))$ for all $l \le i \le r$.

Since analytic geometry always requires exact solutions but computers have precision limits, you only need to output the result modulo $998244353$ for verification.

It can be proven that the answer is always a rational number.

Input

The first line contains two integers $n, q$.

The next $n$ lines each start with an integer $op$.

If $op = 1$, a triple $(a, b, c)$ follows. If $op = 2$, a quintuple $(x_0, y_0, a, b, c)$ follows.

The next $q$ lines each start with an integer $op$.

If $op = 1$, four integers $x, y, l, r$ follow. If $op = 2$, a triple $(a, b, c)$ and two integers $l, r$ follow. If $op = 3$, a quintuple $(x_0, y_0, a, b, c)$ and two integers $l, r$ follow.

Output

For each operation of type 1, output the final coordinates of the point modulo $998244353$.

Examples

Input 1

2 8
1 1 -1 0
2 1 1 3 4 5
1 1 6 1 1
1 1 6 2 2
2 1 0 0 1 2
1 -1 6 1 1
1 -1 6 2 2
3 0 0 1 0 1 1 2
1 -1 4 1 1
1 -1 4 2 2

Output 1

6 1
998244351 5
998244347 1
998244349 5
4 998244352
998244349 3

Constraints

For $100\%$ of the data, $1 \le n, q \le 10^5$.

Any triple $(a, b, c)$ satisfies $-10^9 \le a, b, c \le 10^9$ and $a^2 + b^2 \not\equiv 0 \pmod{998244353}$.

Any quintuple $(x_0, y_0, a, b, c)$ satisfies $-10^9 \le x_0, y_0, a, b, c \le 10^9$, $c \not\equiv 0 \pmod{998244353}$, and $a^2 + b^2 = c^2$.