THTB Sơn Trà, Đà Nẵng 2025

Khôi có một cuốn sách cổ của người La Mã. Nó luôn luôn sử dụng các chữ số La Mã để đánh số trang. Và quyển sách của nó không bao giờ có hơn 3999 trang. Khi cần thiết, sách được chia thành các tập.

Bạn phải viết một chương trình, cho một số hệ thập phân, hiển thị tương đương của nó bằng chữ số La Mã.

Số La Mã gồm 7 kí tự tương ứng với các số thập phân sau:

Người ta quy định các chữ số I, X, C, M không được lặp lại quá ba lần liên tiếp và các kí tự V, L, D không được lặp lại quá một lần liên tiếp. Chính vì thế mà có 6 nhóm kí tự đặc biệt được nêu ra trong bảng sau:

Quy tắc viết: ký tự lớn viết trước, ký tự nhỏ viết sau tương tự như hàng ngàn, hàng trăm, hàng chục, hàng đơn vị trong số thập phân. Với các ký tự trên, số La Mã có thể biểu diễn được các số thập phân từ 1 đến 3999.

Ví dụ: III = 3, VIII = 8, XIX = 19, XXXII = 32, XLV = 45, MMM = 3000

Input

• Dòng 1 là một số nguyên dương \(T\) (\(1 \le T \le 10\)) là số bộ test.
• \(T\) dòng tiếp theo, dòng thứ \(i\) là số nguyên dương \(N\) (\(1 \le N < 4000\)) biểu thị cho quyển sách thứ \(i\) có \(N\) trang.

Output

• In ra trên \(T\) dòng, dòng thứ \(i\) là kết quả tương ứng test thứ \(i\) với số \(N\) được viết bằng chữ số La Mã trong một dòng đơn. Luôn luôn sử dụng chữ in hoa.

Example

2
666
83

DCLXVI
LXXXIII

Lưu ý rằng, trong bài này, quy ước rằng dấu phân cách giữa phần nguyên và phần thập phân của một số là dấu chấm (.).

Hiện tại là năm 2025, và quốc gia Alpha đang bước vào quá trình chuyển đổi số.

Có một vấn đề xảy ra: việc hiển thị những con số lớn, ví dụ như số tiền, theo cách bình thường có thể rất khó đọc. Ví dụ như số \(10^9+7\), khi viết ra theo phương pháp bình thường sẽ là \(1000000007\), có rất nhiều số 0 và dễ dẫn đến viết sai.

Do đó, thông thường khi hiển thị những số lớn, các chữ số trước dấu chấm thập phân thường được nhóm thành các nhóm gồm \(k\) chữ số (trong hầu hết trường hợp, \(k=3\)) theo thứ tự từ phải sang trái. Các nhóm thường được viết cách nhau bằng một dấu phẩy.

Ví dụ, số \(10^9+7\) với \(k=3\) có thể được viết thành \(1,000,000,007\). Số \(2402.2007\) có thể được viết thành \(2,402.2007\).

Vũ đang lập trình một ứng dụng thanh toán qua mạng cho một ngân hàng ở quốc gia Alpha. Hiện tại, anh ta đã lập trình xong các phần cốt lõi, chỉ còn một số vấn đề về mặt hiển thị số. Vũ nhờ bạn viết một chương trình xử lý số như sau:

• Loại bỏ các chữ số 0 vô nghĩa trong số.
• Phân tách các chữ số phía trước dấu thập phân thành các nhóm \(k\) chữ số theo yêu cầu như trên.

Các chữ số 0 vô nghĩa là các chữ số khi bỏ đi không làm thay đổi giá trị của số ban đầu. Ví dụ, số \(0123450.67890\) có 3 chữ số 0, trong đó, chữ số 0 đầu tiên và cuối cùng là vô nghĩa, nhưng chữ số 0 thứ hai không phải chữ số 0 vô nghĩa.

Các bạn hãy giúp Vũ viết chương trình theo đúng yêu cầu nhé.

Input

• Một dòng duy nhất gồm số cần xử lý là một số thập phân có không quá \(255\) chữ số, tiếp theo là số \(k\) (\(2\leq k\leq 10\)).

Output

• Một dòng duy nhất là số cuối cùng được hiển thị ra màn hình.

Example

002402.200700 3

2,402.2007

1000000007.00 4

10,0000,0007

123456789 3

123,456,789

12345.6789 6

12345.6789

Scoring

• 10% số điểm có \(k=3\) và số được nhập vào là một số nguyên, không có chữ số 0 vô nghĩa và không vượt quá 999.
• 30% số điểm khác có số được nhập vào là một số nguyên không có chữ số 0 vô nghĩa.
• 30% số điểm khác có số được nhập vào không có chữ số 0 vô nghĩa.
• 30% số điểm còn lại không có giới hạn gì thêm.

Nhật có \(n\) lá bài, lá bài thứ \(i\) ghi một số nguyên dương \(a_i\). Anh trải các lá bài này thành một hàng ngang (lá bài thứ \(i\) nằm ở vị trí thứ \(i\) từ trái sang) và bắt đầu một thử thách nhỏ với chúng.

Nhật định nghĩa một đoạn các lá bài là một tập hợp các lá bài ở các vị trí liên tiếp nhau, có thể được mô tả bằng một cặp số \((l, r)\) với \(1 \le l \le r \le n\), với \(l\) là lá bài đầu tiên và \(r\) là lá bài cuối cùng của đoạn (hay nói cách khác, đoạn \((l, r)\) sẽ gồm các lá bài \(l, l+1, \ldots, r\)). Nhật còn định nghĩa hai khái niệm liên quan đến đoạn các lá bài sau:

• Một đoạn được gọi là đẹp nếu tồn tại cách chia đoạn thành hai phần gồm các lá bài liên tiếp (nửa trái và nửa phải) sao cho mỗi phần sau khi chia có tổng các số ghi trên các lá bài không vượt quá \(k\) (nếu một phần không có lá bài nào thì tổng các số của phần đó là 0).
• Một đoạn được gọi là hoàn hảo nếu tồn tại cách chia đoạn thành hai phần gồm các lá bài liên tiếp (nửa trái và nửa phải) có số lá bài bằng nhau sao cho mỗi phần sau khi chia có tổng các số ghi trên các lá bài không vượt quá \(k\) (nếu một phần không có lá bài nào thì tổng các số của phần đó là 0).

Ví dụ, trong dãy các lá bài \(a = (1, 2, 3, 3, 2, 1)\) và \(k = 5\) ta có thể các trường hợp ví dụ sau:

• \((1, 2, 2, 1)\) không phải là một đoạn của dãy (vì đây không phải là đoạn gồm các lá bài liên tiếp).
• \((1, 2, 3)\) là một đoạn đẹp vì có thể chia đoạn này thành hai phần \((1, 2)\) và \((3)\) cùng có tổng các số bằng 3. Đây không phải là một đoạn hoàn hảo vì không thể được chia thành hai phần có số lá bài bằng nhau.
• \((2, 3, 3, 2)\) là một đoạn hoàn hảo vì có thể chia đoạn này thành hai phần \((2, 3)\) và \((3, 2)\) cùng có hai lá bài và có tổng các số ghi trên các lá bài bằng 5. Tương tự, \((3, 3)\) cũng là một đoạn hoàn hảo. Các đoạn \((2, 3, 3, 2)\) và \((3, 3)\) đồng thời cũng là các đoạn đẹp.
• \((1, 2, 3, 3, 2, 1)\) không phải là một đoạn đẹp vì không tồn tại cách chia nào thỏa mãn.

Thử thách mà Nhật đặt ra cho chính mình như sau: Với mỗi vị trí \(i\) mà \(1 \le i \le n\), anh phải tìm ra đoạn đẹp dài nhất và đoạn hoàn hảo dài nhất bắt đầu từ vị trí này. Độ dài của một đoạn là số lá bài nằm trong đoạn đó.

Nhật đã hoàn thành thử thách nhưng cần phải kiểm tra xem đáp án của mình có đúng hay không. Các bạn hãy viết một chương trình để giúp Nhật kiểm tra kết quả của mình nhé.

Input

• Dòng đầu tiên gồm ba số nguyên dương \(n, k, \theta\) (\(1 \le n \le 10^6\), \(1 \le k \le 10^{15}\), \(1 \le \theta \le 2\)).
  • Nếu \(\theta = 1\), bạn cần phải xác định đoạn đẹp dài nhất bắt đầu từ mỗi vị trí \(i\) với \(1 \le i \le n\).
  • Nếu \(\theta = 2\), bạn cần phải xác định đoạn hoàn hảo dài nhất bắt đầu từ mỗi vị trí \(i\) với \(1 \le i \le n\).
• Dòng tiếp theo gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)).

Output

• Một dòng duy nhất gồm \(n\) số nguyên không âm:
  • Nếu \(\theta = 1\), số nguyên thứ \(i\) là độ dài đoạn đẹp dài nhất bắt đầu từ vị trí thứ \(i\), hoặc bằng 0 nếu không thể tìm được đoạn đẹp nào.
  • Nếu \(\theta = 2\), số nguyên thứ \(i\) là độ dài đoạn hoàn hảo dài nhất bắt đầu từ vị trí thứ \(i\), hoặc bằng 0 nếu không thể tìm được đoạn hoàn hảo nào.

Example

5 20 1
3 5 7 9 20

4 3 3 2 1

5 20 2
3 5 7 9 20

4 2 2 2 0

Scoring

• \(30\%\) số điểm có \(n \le 80\) và \(\theta = 1\).
• \(20\%\) số điểm có \(n \le 200\) và \(\theta = 2\).
• \(20\%\) số điểm khác có \(n \le 200\) và \(\theta = 1\).
• \(10\%\) số điểm khác có \(n \le 5000\) và \(\theta = 2\).
• \(10\%\) số điểm khác có \(n \le 5000\) và \(\theta = 1\).
• \(5\%\) số điểm khác có \(\theta = 1\).
• \(5\%\) số điểm còn lại có \(\theta = 2\).

Công ty V và công ty H là hai công ty có truyền thống kình địch với nhau. Mỗi công ty đều có những tình báo của mình ở công ty đối phương nhằm thu thập thông tin cũng như đánh cắp những dữ liệu quan trọng cho công ty của mình.

Một điệp viên của công ty V đã tìm cách xâm nhập được vào hệ thống máy chủ của công ty H. Anh nhận ra rằng dữ liệu bí mật của công ty H thực chất là một dãy số nguyên dương \(A_1, A_2, \ldots, A_N\). Anh ta đã ghi lại được dãy số tại thời điểm xâm nhập hệ thống và đã cài đặt được một phần mềm có khả năng báo cáo toàn bộ các hoạt động của các thành viên của công ty H trên hệ thống dữ liệu.

Sau một thời gian, các thành viên của công ty V đã nhận được dãy số \(A\) và báo cáo về các thao tác trên cơ sở dữ liệu của công ty H. Công ty V sẽ tiến hành phân tích các thao tác này. Biết rằng, từ thời điểm hệ thống bị xâm nhập đến khi công ty V bắt đầu tiến hành phân tích, các thành viên của công ty H đã tiến hành \(Q\) thao tác trên hệ thống dữ liệu. Các thao tác này có thể được chia thành ba loại sau (quy ước thao tác thứ nhất là thao tác đầu tiên của công ty H trên cơ sở dữ liệu sau khi bị xâm nhập):

• Loại 1: thay đổi giá trị một phần tử \(A_V = H\).
• Loại 2: tính tổng \(A_L + A_{L+D} + A_{L+2D} + \cdots + A_{L+PD}\).
• Loại 3: khôi phục dãy \(A\) về trạng thái trước thao tác thứ \(T\).

Các thao tác được thực hiện tuần tự và được sắp xếp trong bản báo cáo theo thứ tự thời gian.

Yêu cầu: Từ dữ liệu về dãy \(A\) và bản báo cáo các thao tác, bạn hãy giúp công ty V khôi phục lại kết quả trả về của các thao tác loại 2.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(N, Q\) \((1 \leq N, Q \leq 10^5)\).
• Dòng tiếp theo gồm \(N\) số nguyên dương \(A_1, A_2, \ldots, A_N\) \((1 \leq A_i \leq 10000)\).
• \(Q\) dòng tiếp theo là các thao tác trong bản báo cáo, mỗi dòng thuộc một trong ba dạng sau:
  • 1 V H: thao tác loại 1, với \(V, H\) là các số nguyên dương, yêu cầu thay đổi \(A_V = H\) \((1 \leq V \leq N,\ 1 \leq H \leq 10000)\).
  • 2 L P D: thao tác loại 2, với \(L, P, D\) là các số nguyên không âm, yêu cầu tính tổng \(A_L + A_{L+D} + A_{L+2D} + \cdots + A_{L+PD}\) \((1 \leq L \leq L + PD \leq N,\ 1 \leq D \leq N)\).
  • 3 T: thao tác loại 3, với \(T\) là một số nguyên dương, yêu cầu khôi phục dãy \(A\) về trạng thái trước thao tác thứ \(T\). Dữ liệu đầu vào đảm bảo thứ tự của thao tác hiện tại không nhỏ hơn \(T\).

Output

• Với mỗi thao tác loại 2, in ra kết quả trên một dòng.

Example

5 5
1 2 3 4 5
1 1 4
2 1 1 2
3 1
1 2 5
2 2 3 1

7
17

5 3
4 2 5 3 1
1 3 2
1 4 4
2 1 2 2

7

Scoring

• \(15\%\) số điểm không có thao tác loại 3 và \(P = 0\) với mọi thao tác loại 2.
• \(20\%\) số điểm khác có \(N, Q \leq 5000\).
• \(15\%\) số điểm khác không có thao tác loại 1 và \(D = 1\) với mọi thao tác loại 2.
• \(15\%\) số điểm khác không có thao tác loại 3 và \(D = 1\) với mọi thao tác loại 2.
• \(10\%\) số điểm khác không có thao tác loại 1.
• \(10\%\) số điểm khác có \(P = 0\) với mọi thao tác loại 2.
• \(5\%\) số điểm khác có \(D = 1\) với mọi thao tác loại 2.
• \(5\%\) số điểm khác không có thao tác loại 3.
• \(5\%\) số điểm còn lại không có giới hạn gì thêm.