Xét một dãy số nguyên dương \(a_1, a_2, \ldots, a_n\), ban đầu \(a_i = i\) với \(1 \leq i \leq n\). Cho trước một chữ số \(s\) (với \(1 \leq s \leq 9\)) và \(q\) thao tác trên dãy, mỗi thao tác thuộc một trong hai loại sau:

1. Thao tác loại 1: đó là dạng 1 i c, có nghĩa là cập nhật phần tử \(a_i\) thành \(c\), với \(1 \leq c \leq 10^9\).

2. Thao tác loại 2: đó là dạng 2 L R, yêu cầu tính giá trị \(w = \sum_{i=L}^{R} f(i) \cdot a_i\), trong đó:

   • \(f(i) = 2\) nếu \(i\) chia hết cho \(s\) hoặc trong biểu diễn số \(i\) có xuất hiện chữ số \(s\),
   • ngược lại \(f(i) = 1\).

Yêu cầu: Với mỗi thao tác loại 2, hãy in ra giá trị \(w\).

Dữ liệu vào

• Dòng đầu chứa ba số nguyên dương \(n, s, q\) (với \(n \leq 10^9; 1 \leq s \leq 9; q \leq 10^5\)).
• Dòng sau gồm \(q\) dòng, mỗi dòng mô tả thao tác thứ \(k\).

Dữ liệu ra

• Với mỗi thao tác loại 2, in ra giá trị \(w\) tương ứng, mỗi giá trị trên một dòng.

Input

13 3 3
2 11 13
1 13 10
2 13 13

Output

61
20

Giải thích

• Thao tác thứ nhất: \[ w = 11 + 2 \times 12 + 2 \times 13 = 61 \]
• Dãy số sau thao tác thứ hai: \[ (1,2,3,4,5,6,7,8,9,10,11,12,10) \]
• Thao tác thứ ba: \[ w = 2 \times 10 = 20 \]

Subtasks

• Subtask 1 (30%): \(n,q \le 10^3\)
• Subtask 2 (30%): \(n,q \le 10^5\)
• Subtask 3 (20%): Không có thao tác loại 1.
• Subtask 4 (20%): Không có ràng buộc nào thêm.