Phát kẹo

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 \leq i \leq 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 \leq L \leq R \leq 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 \leq i \leq R)\) sẽ được nhận \(2\times a_{i}\) cái kẹo nếu \(i\) chi 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 \(\sum_{i = L}^{R} b_{i}\), trong đó \(b_{i} = 2a_{i}\) nếu i chia hết cho \(k\) hoặ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.

Input

Vào từ thiết bị vào chuẩn có khuôn dạng:

• Dòng đầu chứa hai số nguyên \(n\), \(q\) \((n, q \leq 2 \times 10^5)\)

• Dòng thứ hai chứa \(n\) số nguyên không âm \(a_{1}, a_{2}, ..., a_{n}\).

• Tiếp theo là \(q\) dòng, mỗi dòng mô tả một thao tác. Cụ thể nếu là thao tác loại \(1\) thì dòng gồm ba số nguyên \(1\) \(i\) \(c\) \((1 \leq i \leq n; 0 \leq c \leq 10^9)\),còn nếu là thao tác loại \(2\) thì dòng gồm bốn số nguyên \(2, L, R, k\) \((1 \leq L \leq R \leq n; 1 \leq k \leq 9)\)

Output

Ghi ra thiết bị 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.

Example

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

21
75
95

Scoring

Subtask \(1\) (\(40\%\) số điểm) : \(n, q \leq 200\).

Subtask \(2\) (\(20\%\) số điểm): Không có thao tác loại \(1\);

Subtask \(3\) (\(20\%\) số điểm): Tất cả các thao tác loại \(2\) có \(k = 1\);

Subtask \(4\) (\(20\%\) số điểm): không có ràng buộc gì thêm.