Contest giao lưu lớp 10 các trường Chuyên (Lần 1)

Alice cần tạo một mật khẩu mạnh cho tài khoản mạng xã hội của cô. Cô muốn viết một chương trình tự động, chương trình này nhận vào một xâu ký tự chỉ gồm các số chữ cái trong bảng chữ cái tiếng Anh và trả ra một xâu ký tự là mật khẩu được tạo. Xâu được tạo từ xâu ban đầu theo quy tắc sau đây:

• Ký tự đầu tiên của xâu mới là ký tự cuối cùng của xâu ban đầu.
• Tiếp theo là tổng các ký tự số trong xâu ban đầu.
• Tiếp theo là các ký tự số trong xâu ban đầu được sắp xếp theo thứ tự tăng dần.
• Tiếp theo là các ký tự chữ trong xâu ban đầu theo đúng thứ tự xuất hiện. Nếu ký tự là chữ hoa, chuyển sang chữ thường tương ứng.
• Cuối cùng là số lượng ký tự là chữ hoa trong xâu ban đầu.

Bạn hãy giúp Alice viết chương trình để tạo mật khẩu như vậy nhé.

Thông tin tệp:

• Tên tệp chương trình: PASSWORD.*
• Tệp vào: PASSWORD.inp
• Tệp ra: PASSWORD.out

Input

• Một dòng duy nhất gồm xâu ban đầu có độ dài không quá \(10^5\) ký tự và chỉ gồm các ký tự chữ cái trong bảng chữ cái tiếng Anh và số.

Output

• In kết quả ra tệp văn bản PASSWORD.out: một dòng duy nhất gồm xâu được tạo ra.

Example

icpc2025HCMC

C90225icpchcmc4

Scoring

• \(30\%\) số điểm có xâu chỉ bao gồm các chữ cái in thường.
• \(30\%\) số điểm khác có xâu chỉ bao gồm các chữ cái.
• \(20\%\) số điểm khác có xâu có tối đa \(1\) ký tự số.
• \(20\%\) số điểm còn lại không có giới hạn gì thêm.

Hôm nay, để giúp cả lớp ôn lại khái niệm về ước chung và bội chung, thầy giáo dạy toán của G và H đưa ra một thử thách nho nhỏ.

Thầy viết lên bảng hai cột số nguyên, mỗi cột gồm \(x\) số – cột bên trái là các số nguyên dương tăng dần bắt đầu từ \(a\), nghĩa là \(a, a + 1, a + 2, \dots, a + x - 1\), cột bên phải là các số nguyên dương tăng dần bắt đầu từ \(b\), nghĩa là \(b, b + 1, b + 2, \dots, b + x - 1\). Các số này được viết thành \(x\) hàng, hàng thứ \(i\) gồm hai số nguyên dương \(a + i - 1\) và \(b + i - 1\).

Sau đó, thầy chia cả lớp thành các nhóm nhỏ, mỗi nhóm cần tìm ra hàng mà bội chung nhỏ nhất của hai số trên hàng đó là nhỏ nhất và tính ra giá trị bội chung nhỏ nhất đó. Nhóm của G và H muốn giành chiến thắng trong trò chơi nên nhờ bạn giúp giải bài toán của thầy giao. Các bạn hãy giúp G và H nhé.

Input

• Dữ liệu đọc từ tệp văn bản LCM.inp:
  • Dòng đầu tiên gồm một số nguyên dương \(T\) (\(1 \le T \le 200\)) là số bộ số cần xử lý.
  • \(T\) dòng tiếp theo, mỗi dòng gồm ba số nguyên \(a, b, x\) (\(1 \le a, b, x \le 10^{14}\)).

Output

• Ghi ra tệp văn bản LCM.out:
  • Với mỗi bộ dữ liệu, in ra giá trị bội chung nhỏ nhất tìm được. Vì kết quả có thể rất lớn nên chỉ cần in ra phần dư khi chia cho \(10^9 + 7\).

Example

2
14 9 7
24 2 7

30
24

Scoring

• \(36\%\) số điểm có \(x \le 5000\).
• \(28\%\) số điểm khác có \(a, b, x \le 10^6\).
• \(18\%\) số điểm khác có \(a, b, x \le 10^{11}\).
• \(18\%\) số điểm còn lại không có giới hạn gì thêm.

Hôm nay, để giúp cả lớp ôn lại khái niệm về ước chung và bội chung, thầy giáo dạy toán của G và H đưa ra một thử thách nho nhỏ.

Có \(V + 1\) số từ \(0\) đến \(V\) được cho vào một dãy \((a_0, a_1, \dots, a_V)\). Thực hiện liên tục các thao tác sau cho đến khi dãy không còn phần tử nào:

• Loại bỏ lần lượt các phần tử có thứ tự chia hết cho \(H\) (\(a_0, a_H, a_{2H}, a_{3H}, \dots\)).
• Đánh số lại các phần tử trong dãy.

Yêu cầu: Cho biết \(V\) được loại bỏ ở thao tác thứ bao nhiêu.

Input

• Dữ liệu đọc từ tệp văn bản REMOVE.inp:
  • Một dòng duy nhất gồm hai số nguyên dương \(V, H\) (\(1 \leq H \leq V \leq 10^{12}\)).

Output

• Ghi ra tệp văn bản REMOVE.out:
  • Một dòng duy nhất là thời điểm bị loại của \(V\). Hiển nhiên rằng sau một số hữu hạn thao tác \(V\) chắc chắn sẽ được loại bỏ.

Example

5 3

2

6 2

1

6 4

2

Scoring

• \(12\%\) số điểm có \(V \leq 1000\).
• \(12\%\) số điểm khác có \(V \leq 10^5\).
• \(24\%\) số điểm khác có \(V \leq 10^6\).
• \(24\%\) số điểm khác có \(H = 2\).
• \(28\%\) số điểm còn lại không có giới hạn gì thêm.