Trong một trò chơi của chương trình ngoại khóa có \(n\) bạn nhỏ tham gia, các bạn xếp thành một hàng ngang và được đánh số từ \(1\) đến \(n\) theo chiều từ trái sang phải để nhận kẹo. Bạn thứ \(i\) \((1 \le i \le n)\) dự định sẽ được nhận \(a_i\) cái kẹo. Alice được mời lên phát kẹo cho các bạn đứng từ vị trí \(L\) đến vị trí \(R\) \((1 \le L \le R \le n)\). Là một người yêu trẻ nhỏ và cũng say mê toán học, trước khi lên phát kẹo Alice đã chọn một chữ số \(k\) và chuẩn bị thêm một số kẹo để phát theo cách: Bạn có chỉ số \(i\) \((L \le i \le R)\) sẽ được nhận \(2 \times a_i\) cái kẹo nếu \(i\) chia hết cho \(k\) hoặc trong số \(i\) có chứa chữ số \(k\), ngược lại bạn \(i\) sẽ nhận \(a_i\) cái kẹo.

Theo ý tưởng trên, Alice đã đề xuất một bài toán thú vị dưới đây:

Cho dãy số nguyên không âm \(a_1, a_2, ..., a_n\) và \(q\) thao tác, mỗi thao tác thuộc một trong hai loại sau:

• Thao tác loại \(1\) được mô tả bằng ba số có dạng: "1 i c", có nghĩa là thay đổi giá trị phần tử \(i\) bằng \(c\).
• Thao tác loại \(2\) được mô tả bằng bốn số có dạng: "2 L R k", có nghĩa là cần tính tổng ∑ từ \(i=L\) đến \(i=R\) của \(b_i\) (\(\sum_{i=L}^{R} b_i\)), trong đó \(b_i = 2 \times a_i\) nếu \(i\) chia hết cho \(k\) hoặc \(i\) có chứa chữ số \(k\), ngược lại \(b_i = a_i\).

Yêu cầu: Cho dãy \(a_1, a_2, ..., a_n\) và \(q\) thao tác, hãy thực hiện lần lượt từng thao tác, với mỗi thao tác loại \(2\) đưa ra giá trị cần tính.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên dương \(n, q\) (với \(n, q \le 2 \times 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên không âm \(a_1, a_2, ..., a_n\) (với \(a_i \le 10^9\)).
• Tiếp theo là q dòng, mỗi dòng mô tả một thao tác.
• Nếu là thao tác loại \(1\) thì dòng gồm ba số nguyên "1 i c" (với \(1 \le i \le n; 0 \le c \le 10^9\)).
• Nếu là thao tác loại \(2\) thì dòng gồm bốn số nguyên "2 L R k" (với \(1 \le L \le R \le n; 1 \le k \le 9\)).

Dữ liệu ra

• Ghi ra chuẩn \(q\) dòng, mỗi dòng tương ứng với câu trả lời cho thao tác loại \(2\) trong dữ liệu vào.

Input 1

16 4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
2 1 5 2
2 14 16 4
1 14 24
2 14 16 4

Output 1

21
75
95