Güzgü Dövrəsi#13046
Sizə bir xətt üzrə düzülmüş qapı verilir. İkili siqnal qapılardan soldan sağa keçir və və ya vəziyyətində ola bilər.
-ci qapının d_i rəqəmi və iki mükafatı w_{i,0} və w_{i,1} var. Onun siqnala təsiri d_i \bmod 4-dən asılıdır:
Əgər d_i \bmod 4 = 0 olarsa, vəziyyət -dan -ə və -dən -a dəyişir.
Əgər d_i \bmod 4 = 1 olarsa, vəziyyət dəyişmir.
Əgər d_i \bmod 4 = 2 olarsa, vəziyyət olur.
Əgər d_i \bmod 4 = 3 olarsa, vəziyyət olur.
-ci qapı emal edildikdən sonra, əgər alınan vəziyyət olarsa, siz w_{i,s} mükafatını alırsınız.
Siz ədəd iki növ əməliyyatı emal etməlisiniz:
1 i d — d_i=d təyin edin.
2 l r — yalnız -dən -yə qədər olan qapıları nəzərə alın. qapısından əvvəl siqnal vəziyyətindədir.
Bu sorğu üçün siz ya bütün qapıları dəyişməz saxlaya, ya da elə bir boş olmayan seqmenti seçə bilərsiniz ki,
olsun və hər bir üçün -dan -yə qədər
əvəzləməsini tətbiq edin.
-dən -yə qədər qapıları emal edərkən əldə edilə bilən maksimum ümumi mükafatı tapın.
d_i \leftarrow 9-d_i əvəzləməsi müvəqqətidir və yalnız cari sorğuya təsir edir. Bu, w_{i,0} və w_{i,1} mükafatlarını dəyişmir.
Birinci sətirdə iki tam ədəd və verilir (1 \le n \le 10^5, 1 \le q \le 8 \cdot 10^4).
Növbəti sətirin hər birində üç tam ədəd d_i, w_{i,0} və w_{i,1} verilir (0 \le d_i \le 9, -10^9 \le w_{i,0},w_{i,1} \le 10^9).
Növbəti sətir əməliyyatları təsvir edir:
1 i d (1 \le i \le n, 0 \le d \le 9);
2 l r (1 \le l \le r \le n).
Hər 2 tipli əməliyyat üçün bir tam ədəd çap edin — maksimum mümkün ümumi mükafat.
Nümunə 1
Başlanğıcda,
Birinci sorğu üçün seqmentini seçin. Onda d_4 müvəqqəti olaraq -dan -ə dəyişir.
-dən -ə qədər qapılardan alınan mükafatlar
olur, buna görə ümumi mükafat -dir.
Sonra yeniləmə d_2-ni -dən -ə dəyişir.
İkinci sorğu üçün yenə seqmentini seçin. Alınan mükafatlar
olur, buna görə maksimum ümumi mükafat -dur.
Alt tapşırıq ( bal): n \le 20 və q \le 20.
Alt tapşırıq ( bal): ilkin massivdə və hər yeniləmədə hər rəqəm üçün d \bmod 4 \in \{2,3\}.
Alt tapşırıq ( bal): 1 tipli əməliyyatlar yoxdur.
Alt tapşırıq ( bal): 2 tipli bütün əməliyyatlar üçün l=1 və r=n.
Alt tapşırıq ( bal): n \le 5000 və q \le 5000.
Alt tapşırıq ( bal): ilkin massivdə və hər yeniləmədə hər rəqəm üçün d \bmod 4 \in \{0,1\}.
Alt tapşırıq ( bal): Əlavə məhdudiyyət yoxdur.