Tổng của tổng các chữ số

Trong một buổi học toán, giáo viên của FullHouse Dev đã giới thiệu cho họ một bài toán thú vị về tổng các chữ số của một số. Với sự nhiệt tình và tò mò, FullHouse Dev đã quyết định thử nghiệm với khái niệm này.

Bài toán

Giáo viên định nghĩa "Giá trị chữ số" của một số là tổng các chữ số của nó, được tính đệ quy cho đến khi kết quả chỉ còn một chữ số. Sau đó, cô ấy đưa ra một mảng \(A\) gồm \(N\) số khác nhau và \(Q\) truy vấn. Mỗi truy vấn yêu cầu FullHouse Dev tạo một tập hợp \(K\) số từ mảng và tính tổng "Giá trị chữ số" của \(K\) số đó.

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\), lần lượt là số lượng phần tử trong mảng và số lượng truy vấn.
• Dòng thứ hai chứa \(N\) số nguyên, biểu diễn mảng \(A\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên: loại truy vấn (1 hoặc 2) và \(K\).

OUTPUT FORMAT:

• \(Q\) dòng, mỗi dòng chứa một số nguyên là kết quả của truy vấn tương ứng.

Ràng buộc:

• \(1 \leq N \leq 10^5\)
• \(1 \leq Q \leq 10^5\)
• \(1 \leq A[i] \leq 10^9\)
• \(1 \leq K \leq N\)

Ví dụ

INPUT

5 5
13 345 193 44444 100303
1 2
1 4
2 1
2 4
1 5

OUTPUT

11
18
2
13
20

Giải thích

• Truy vấn 1: Giá trị lớn nhất có thể đạt được với tập 2 số là 11 (từ 13 và 100303).
• Truy vấn 2: Giá trị lớn nhất có thể đạt được với tập 4 số là 18 (từ 13, 345, 193, 100303).
• Truy vấn 3: Giá trị nhỏ nhất có thể đạt được với tập 1 số là 2 (từ 44444).
• Truy vấn 4: Giá trị nhỏ nhất có thể đạt được với tập 4 số là 13.
• Truy vấn 5: Giá trị lớn nhất có thể đạt được với tất cả 5 số là 20.

FullHouse Dev đã rất hào hứng với bài toán này và quyết tâm giải quyết nó một cách hiệu quả.