Дзеркальна схема

Вхідні дані

Перший рядок містить два цілі числа $n$ і $q$ (1 \le n \le 10^5, 1 \le q \le 8 \cdot 10^4).

Кожен із наступних $n$ рядків містить три цілі числа d_i, w_{i,0} та w_{i,1} (0 \le d_i \le 9, -10^9 \le w_{i,0},w_{i,1} \le 10^9).

Кожен із наступних $q$ рядків описує операції:

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

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

Вихідні дані

Для кожної операції типу $2$ виведіть одне ціле число — максимальну можливу сумарну винагороду.

Приклади

Примітка

Спочатку,

Для першого запиту виберіть відрізок $[4,4]$. Тоді d_4 тимчасово змінюється з $6$ на $3$.

Винагороди, отримані з елементів від $1$ до $5$, дорівнюють

тому сумарна винагорода дорівнює $20$.

Потім оновлення змінює d_2 з $7$ на $1$.

Для другого запиту знову виберіть відрізок $[4,4]$. Отримані винагороди дорівнюють

тому максимальна сумарна винагорода дорівнює $19$.

Оцінювання

1. Підзадача $1$ ($15$ балів): n \le 20 і q \le 20.

2. Підзадача $2$ ($25$ балів): кожна цифра в початковому масиві та в кожному оновленні задовольняє d \bmod 4 \in \{2,3\}.

3. Підзадача $3$ ($35$ балів): немає операцій типу $1$.

4. Підзадача $4$ ($35$ балів): кожна операція типу $2$ має l=1 і r=n.

5. Підзадача $5$ ($60$ балів): n \le 5000 і q \le 5000.

6. Підзадача $6$ ($80$ балів): кожна цифра в початковому масиві та в кожному оновленні задовольняє d \bmod 4 \in \{0,1\}.

7. Підзадача $7$ ($200$ балів): Без додаткових обмежень.