Mô tả và yêu cầu

Số may mắn
Cho một dãy 𝐴 gồm 𝑁 số nguyên 𝐴1, 𝐴2, 𝐴3, … 𝐴𝑁 có giá trị từ 1 đến 9. Gọi 𝑆[𝐿 … 𝑅] là
số nguyên được ghép bởi các số từ vị trí 𝐿 đến vị trí 𝑅 trong dãy 𝐴, theo thứ tự từ trái sang phải.
Ví dụ, với dãy 𝐴 = [2,6, 5, 7,4] thì 𝑆[2… 5] là số 6574.
Một số nguyên không âm được gọi là may mắn nếu như trong biểu diễn thập phân của
số đó không chứa số “13”. Ví dụ, các số may mắn là 6, 12, 31, 103, .. ..; Các số không may
mắn là 13, 5713, 321321, …
Yêu cầu: Bạn cần thực hiện 𝑄 yêu cầu thuộc một trong hai loại sau:
 Loại 1: Đưa ra số lượng các số may mắn không vượt quá 𝑆[𝐿 … 𝑅];
 Loại 2: Thay giá trị phần tử thứ 𝑖 bằng giá trị 𝑋.
Dữ liệu vào từ tệp văn bản SMM.INP:
 Dòng đầu chứa hai số nguyên dương 𝑁, 𝑄 (𝑁, 𝑄 ≤ 2 × 105);
 Dòng thứ hai gồm 𝑁 số nguyên 𝐴1, 𝐴2, 𝐴3, … 𝐴𝑁 viết liền nhau (1 ≤ 𝐴𝑖 ≤ 9; 1 ≤ 𝑖≤
𝑁);
 𝑄 dòng tiếp theo, mỗi dòng chứa một yêu cầu thuộc một trong hai dạng sau:
o 1 𝐿 𝑅: Mô tả yêu cầu ghi ra số lượng số may mắn không vượt quá 𝑆[𝐿 …𝑅] (1 ≤
𝐿 ≤ 𝑅 ≤ 𝑁) sau khi chia dư cho 109 + 7;
o 2 𝑖 𝑋: Mô tả yêu cầu thay giá trị phần tử thứ 𝑖 bằng giá trị 𝑋 (1 ≤ 𝑖 ≤ 𝑁; 1 ≤
𝑋 ≤ 9).
Kết quả ghi ra tệp văn bản SMM.OUT: Với mỗi truy vấn loại 1, ghi ra kết quả của truy vấn đó
trên một dòng.

Ví dụ

SMM.INP                   SMM.OUT                                   Giải thích
 6 3                       84                         Với yêu cầu đầu tiên, các số may mắn không
 849613                    7                          vượt quá 84 là 0,    1,2, …  ,12, 14, 15,  … ,84;
 1 1 2                                                Với yêu cầu thứ hai, dãy A là 844613;
 2 3 4                                                Với   yêu cầu thứ    ba, các số    may mắn không
 1 4 4                                                vượt quá 6 là 0,   1, 2,…  ,5,6.
Ràng buộc:
       Có 20% số test ứng với 20% số điểm có 𝑁             ≤  6; 𝑄 =  1;
       20% số test khác ứng với 20% số điểm có 𝑁             ≤  6;
       20% số test khác ứng với 20% số điểm có 𝑁             ≤  100;
       20% số test khác ứng với 20% số điểm có 𝑄             ≤  2000;
       20% số test còn lại ứng với 20% số điểm không có ràng buộc gì thêm.