Cho một dãy ~A~ gồm ~N~ số nguyên ~A_1, A_2, A_3, \dots, A_N~ (các phần tử có giá trị từ ~1~ đến ~9~). Gọi ~S[L \dots R]~ là số nguyên được ghép bởi các số từ vị trí ~L~ đến vị trí ~R~ trong dãy ~A~, theo thứ tự từ trái sang phải.

Ví dụ: Với dãy ~A = [2, 6, 5, 7, 4]~ thì ~S[2 \dots 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, \dots~;
• Các số không may mắn là ~13, 5713, 321321, \dots~

Yêu cầu: Bạn cần thực hiện ~Q~ 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á ~S[L \dots R]~;
• Loại ~2~: Thay giá trị phần tử thứ ~i~ bằng giá trị ~X~.

Input Specification: Data taken from SMM.INP

• Dòng đầu chứa hai số nguyên dương ~N, Q~ ~(N, Q \le 2 \times 10^5)~;
• Dòng thứ ~2~ gồm ~N~ số nguyên ~A_1, A_2, A_3, \dots, A_N~ viết liền nhau ~(1 \le A_i \le 9; 1 \le i \le N)~;
• ~Q~ 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:
  • 1 L R: Mô tả yêu cầu ghi ra số lượng số may mắn không vượt quá ~S[L \dots R]~ ~(1 \le L \le R \le N)~ sau khi chia dư cho ~10^9 + 7~;
  • 2 i X: Mô tả yêu cầu thay giá trị phần tử thư ~i~ bằng giá trị ~X~ ~(1 \le i \le N; 1 \le X \le 9)~.

Output Specification: Data written in SMM.OUT

• Với mỗi yêu cầu loại ~1~, ghi ra kết quả trên một dòng.

Limitations

• Có ~20\%~ số Cases ứng với ~20\%~ số điểm thỏa mãn: ~N \le 6; Q = 1~;
• Có ~20\%~ số Cases ứng với ~20\%~ số điểm thỏa mãn: ~N \le 6~;
• Có ~20\%~ số Cases ứng với ~20\%~ số điểm thỏa mãn: ~N \le 100~;
• Có ~20\%~ số Cases ứng với ~20\%~ số điểm thỏa mãn: ~Q \le 2000~;
• ~20\%~ số Cases còn lại ứng với ~20\%~ số điểm không có ràng buộc gì thêm.

Sample Case(s)

Input #1:

6 3
849613
1 1 2
2 3 4
1 4 4

Output #1:

84
7

Explanation:

• Với yêu cầu đầu tiên, các số may mắn không vượt quá ~84~ là:
  • ~0, 1, 2, \dots, 12, 14, 15, \dots, 83, 84~;
• Với yêu cầu thứ ~2~, dãy ~A~ là ~844613~;
• Với yêu cầu thứ ~3~, các số may mắn không vượt quá ~6~ là:
  • ~0, 1, 2, 3, 4, 5, 6~.