Mirror Circuit

Input

The first line contains two integers $n$ and $q$ (1 \le n \le 10^5, 1 \le q \le 8 \cdot 10^4).

The next $n$ lines each contain three integers d_i, w_{i,0}, and w_{i,1} (0 \le d_i \le 9, -10^9 \le w_{i,0},w_{i,1} \le 10^9).

The next $q$ lines describe the operations:

• 1 i d (1 \le i \le n, 0 \le d \le 9);

• 2 l r (1 \le l \le r \le n).

Output

For every operation of type $2$, print one integer — the maximum possible total reward.

Examples

Note

Initially,

For the first query, choose the segment $[4,4]$. Then d_4 temporarily changes from $6$ to $3$.

The rewards obtained from gates $1$ through $5$ are

so the total reward is $20$.

Then the update changes d_2 from $7$ to $1$.

For the second query, again choose the segment $[4,4]$. The obtained rewards are

so the maximum total reward is $19$.

Scoring

1. Subtask $1$ ($15$ points): n \le 20 and q \le 20.

2. Subtask $2$ ($25$ points): every digit in the initial array and in every update satisfies d \bmod 4 \in \{2,3\}.

3. Subtask $3$ ($35$ points): there are no operations of type $1$.

4. Subtask $4$ ($35$ points): every operation of type $2$ has l=1 and r=n.

5. Subtask $5$ ($60$ points): n \le 5000 and q \le 5000.

6. Subtask $6$ ($80$ points): every digit in the initial array and in every update satisfies d \bmod 4 \in \{0,1\}.

7. Subtask $7$ ($200$ points): No additional constraints.