Trong giờ hình học, An được thầy giáo dạy về công thức tính diện tích của hình chữ nhật và hình vuông. An thấy hình vuông rất đẹp nên cậu định nghĩa một hình chữ nhật “đẹp” là hình chữ nhật có các đặc điểm sau:

• Độ dài hai cạnh là các số nguyên dương.
• Diện tích bằng diện tích của một hình vuông có độ dài cạnh là một số nguyên dương.

An đã phát biểu định nghĩa này trước lớp và thách đố bài toán như sau:
Cho số nguyên dương \(𝑥\). Tìm số nguyên dương \(𝑦\) nhỏ nhất để \(𝑥\) và \(𝑦\) là độ dài hai cạnh của một hình chữ nhật “đẹp”.

Yêu cầu: Giúp cả lớp tìm số nguyên dương \(𝑦\) thỏa mãn bài toán của An.
Dữ liệu: Nhập từ tệp văn bản B1.INP, gồm một dòng duy nhất chứa số nguyên dương \(𝑥\).
Kết quả: Ghi ra tệp văn bản B1.OUT, gồm một dòng duy nhất chứa số nguyên dương \(𝑦\).

Scoring

• 90% số test tương ứng với 90% số điểm thỏa mãn \(1≤𝑥≤10^6\);
• 10% số test tương ứng với 10% số điểm thỏa mãn \(10^6<𝑥≤10^{12}\).

Example

4

1

6

6

8

2

Nhân dịp năm mới Giáp Thìn, An tham gia lễ hội đầu năm thường niên của làng. Lễ hội có nhiều trò chơi thú vị thu hút sự chú ý của An, cậu chơi trò chơi đầu tiên là “Bốc số”.
Luật chơi của trò chơi rất đơn giản: ở mỗi lượt chơi, An bốc từ thùng một lá thăm, mỗi lá thăm gồm 2 phần:

• Phần đầu lá thăm là một dãy có độ dài \(𝑁\) kí tự gồm các chữ số từ 1 đến 9.
• Phần sau lá thăm ghi số 0 hoặc 1, cách phần đầu một khoảng trống.

Công việc của An là xóa đi một hoặc một vài kí tự của phần đầu lá thăm sau đó viết các kí tự còn lại theo đúng thứ tự ban đầu (từ trái qua phải) để thu được một số nguyên dương lớn nhất thỏa mãn:

• Chia hết cho 5 nếu phần sau lá thăm là 0.
• Chia hết cho 3 nếu phần sau lá thăm là 1.

Yêu cầu: Hãy giúp An hoàn thành trò chơi.
Dữ liệu: Nhập từ tệp B2.INP có cấu trúc như sau:

• Dòng 1: Ghi số nguyên dương \(𝑡\) là số lần bốc thăm của An (\(1≤𝑡≤100\)).
• \(𝑡\) dòng tiếp theo, dòng thứ \(𝑖\) ghi một dãy có độ dài \(𝑁\ (1≤𝑁≤100)\) kí tự gồm các chữ số từ 1 đến 9 và một số \(𝑘\) (phân biệt bằng dấu cách trống) đại diện cho lá thăm thứ \(𝑖\).

Kết quả: Ghi ra tệp B2.OUT gồm \(𝑡\) dòng, dòng thứ \(𝑖\) chứa kết quả của lần bốc thăm thứ \(𝑖\) (dữ liệu đầu vào luôn đảm bảo có kết quả).

Scoring

• 60% số test tương ứng 60% số điểm thoả mãn \(𝑘=0\);
• 20% số test tương ứng 20% số điểm thoả mãn \(1≤𝑁≤18\);
• 20% số test tương ứng 20% số điểm không có ràng buộc gì thêm.

Example

4
2433514 0
5295284 0
12324524 1
5321 1

24335
5295
1324524
531

Sau khi tham gia trò chơi “Bốc số”, An tiếp tục tham gia trò chơi “Xếp gạch”. Ban tổ chức cho trước 𝑛 chồng gạch được xếp thành một hàng ngang và đánh số từ 1 đến \(𝑛\). Số viên gạch ở các chồng lần lượt là \(𝑎_1,𝑎_2,…,𝑎_𝑛\).

An cần thực hiện \(𝑚\) lượt chơi tương ứng với dãy số nguyên dương \(𝑏_1,𝑏_2,…,𝑏_𝑚\) đã biết trước. Ở lượt thứ \(𝑖\ (1≤𝑖≤𝑚)\), An được quyền thực hiện chỉ một trong hai lựa chọn:

• Bỏ qua không sử dụng giá trị \(𝑏_𝑖\).
• Xếp thêm \(𝑏_𝑖\) viên gạch lên chồng gạch thứ \(𝑗\ (1≤𝑗≤𝑛)\) nếu tất cả các chồng gạch thứ \(𝑗,𝑗+1,𝑗+2,…,𝑛\) chưa từng được xếp thêm viên gạch nào trong các lượt trước đó.

Trò chơi dừng lại khi hết lượt hoặc An đã thực hiện xếp thêm gạch ở chồng thứ \(𝑛\). Khi đó ban tổ chức sẽ đếm số gạch ở mỗi chồng và lấy số gạch ở chồng ít nhất làm điểm số của An.

Cách chơi của An là tối ưu nhất nên cậu đã đạt được số điểm tối đa của trò chơi.

Yêu cầu: Hãy tìm ra số điểm An đạt được.
Dữ liệu: Nhập từ tệp B3.INP gồm 3 dòng:

• Dòng 1: ghi hai số nguyên dương \(𝑛\) và \(𝑚\) lần lượt là số chồng gạch ban đầu và số lượt chơi của An.
• Dòng 2: ghi \(𝑛\) số nguyên không âm \(𝑎_1,𝑎_2,…,𝑎_𝑛\ (𝑎_𝑖≤10^8)\) mô tả số gạch ở các chồng ban đầu.
• Dòng 3: ghi \(𝑚\) số nguyên dương \(𝑏_1,𝑏_2,…,𝑏_𝑚 (𝑏_𝑖≤10^8)\) mô tả các giá trị của ban tổ chức đưa trước cho An, \(𝑏_𝑖\) là giá trị được sử dụng ở lượt thứ \(𝑖\).

Kết quả: Ghi ra tệp B3.OUT gồm 1 dòng chứa số điểm An đạt được.

Scoring

• 40% số test tương ứng 40% số điểm thoả mãn \(𝑚=1,1≤𝑛≤10^2\);
• 30% số test tương ứng 30% số điểm thoả mãn \(𝑚=2\) và \(10^2<𝑛≤10^3\);
• 30% số test tương ứng 30% số điểm thoả mãn \(10^3<𝑛,𝑚≤10^5\).

Example

5 3
2 5 1 4 6
1 3 4

4        

Sau khi hoàn thành 2 trò chơi thú vị của lễ hội, An cảm thấy rất hứng thú và cậu quyết định chơi trò chơi cuối trước khi về. An chọn trò chơi có thưởng của lễ hội do một ông giáo về hưu trong làng chủ trì.
Ông giáo xếp các ống tre gồm hai màu xanh hoặc đỏ thành một hoặc hai hàng ngang.
Ông giáo có \(10^6\) thẻ bài được xếp thành một chồng, được đánh số từ 1 đến \(10^6\) theo thứ tự từ trên xuống dưới. Bắt đầu trò chơi, An bốc lần lượt các thẻ bài từ trên xuống dưới của chồng bài và chọn không bỏ thẻ bài này vào bất kì ống tre nào (kể cả trong những lượt bốc sau) hoặc bỏ thẻ bài đó vào một ống tre thỏa mãn các yêu cầu:

• Mỗi ống tre chứa đúng một thẻ bài duy nhất.
• Thẻ số chẵn chỉ được bỏ vào ống màu xanh, thẻ số lẻ chỉ được bỏ vào ống màu đỏ.
• Chỉ được bỏ thẻ bài vào ống tre thứ \(𝑖\) khi các ống tre \(1,2,…,𝑖−1\) của hàng đó đã được bỏ thẻ bài.

Trò chơi kết thúc khi An đã bỏ thẻ bài vào tất cả các ống tre mà ông giáo xếp ra. Điểm thưởng của An đạt được là số thẻ bài còn lại trong chồng bài ban đầu.
Với sự thông minh của mình thì trò chơi của ông giáo đã không làm khó được An và cậu đã đạt được số điểm cao nhất của trò chơi.

Yêu cầu: Hãy tìm số điểm mà An đạt được.

Dữ liệu: Nhập từ tệp B4.INP có cấu trúc:

• Dòng 1: Ghi số \(𝑘\) bằng 1 hoặc 2 thể hiện số lượng hàng ngang ông giáo xếp ra.
• Dòng 2: Ghi một chuỗi có độ dài không quá 5000 kí tự, gồm hai loại kí tự \(B\) và \(R\) (\(B\) tương ứng với ống tre màu xanh và \(R\) tương ứng với ống tre màu đỏ) mô tả hàng ống tre thứ nhất.
• Dòng 3: tùy vào giá trị của \(𝑘\), cụ thể:
  • \(𝑘=1\): bỏ trống
  • \(𝑘=2\): ghi một chuỗi có độ dài không quá 5000 kí tự, gồm hai loại kí tự \(B\) và \(R\) (\(B\) tương ứng với ống tre màu xanh và \(R\) tương ứng với ống tre màu đỏ) mô tả hàng ống tre thứ hai.

Kết quả: Ghi ra tệp B4.OUT gồm 1 dòng chứa số điểm cao nhất có thể đạt được.

Scoring

• 20% số test tương ứng 20% số điểm thoả mãn \(𝑘=1\);
• 30% số test tương ứng 30% số điểm thoả mãn \(𝑘=2\) và dòng 2 có các kí tự giống nhau;
• 50% số test tương ứng 50% số điểm thoả mãn \(𝑘=2\) và không ràng buộc gì thêm.

Example

1
BRR

999995        

2
BRR
BBB

999992        

2
BRBRB
RBRB

999990