Trong mọi kỳ thi lập trình của APC, việc giữ gìn tính trung thực học thuật là yêu cầu bắt buộc. Để đảm bảo tính công bằng và nghiêm túc trong suốt quá trình thi, ban tổ chức quy định 5 điều luật sau đây về việc cấm sử dụng AI và ngăn chặn mọi hành vi gian lận.

Nội dung 5 điều luật:

1. Không được sử dụng bất kỳ công cụ AI để tạo ra lời giải.
2. Không được chia sẻ code hoặc thảo luận bài với thí sinh khác.
3. Không được sử dụng tài liệu hoặc nguồn tham khảo ngoài phạm vi cho phép.
4. Không được chỉnh sửa hệ thống hoặc tìm cách can thiệp vào môi trường thi.
5. Mọi hành vi gian lận sẽ bị loại trực tiếp khỏi UMTOJ và báo cáo về CLB.

Yêu cầu

Hãy in ra chính xác điều luật trên, nhưng ở dạng không dấu, mỗi dòng tương ứng với một điều luật, theo đúng thứ tự.

Dữ liệu vào

Không có dữ liệu vào.

Dữ liệu ra

Ghi ra thiết bị chuẩn chính xác 5 dòng điều luật, không thêm, không bớt, không dấu tiếng Việt.

Ví dụ

Dữ liệu vào

Dữ liệu ra

1. Khong duoc su dung bat ky cong cu AI de tao ra loi giai.
2. Khong duoc chia se code hoac thao luan bai voi thi sinh khac.
3. Khong duoc su dung tai lieu hoac nguon tham khao ngoai pham vi cho phep.
4. Khong duoc chinh sua he thong hoac tim cach can thiep vao moi truong thi.
5. Moi hanh vi gian lan se bi loai truc tiep khoi UMTOJ va bao cao ve CLB.

Buổi sáng hôm ấy, phòng sinh hoạt CLB APC vẫn còn yên tĩnh theo đúng cái cách thường thấy vào đầu ngày, trước khi mọi âm thanh của buổi thi bắt đầu ập vào nơi này. Ánh nắng len qua khung cửa kính đã cũ, tạo nên một vệt sáng dài trên mặt bàn gỗ, nơi mấy vết sơn trắng còn sót lại từ buổi trang trí poster năm trước vẫn chưa kịp chà sạch. Cái im lặng của căn phòng không phải là sự trống trải, mà giống như trạng thái nghỉ của một nơi đã quen với nhịp làm việc đều đặn -- từng buổi thi, từng buổi họp, từng buổi sinh hoạt nối tiếp nhau qua nhiều năm.

SOTan đẩy cửa bước vào. Anh không mở mạnh, cũng không rón rén, mà mở đúng theo kiểu người đã quá quen với cái bản lề kêu nhẹ ở cuối hành trình. Ánh sáng lùa vào sau lưng anh, hòa vào luồng sáng của buổi sớm, khiến căn phòng như sáng thêm một chút. Trên tay SOTan là bìa hồ sơ của buổi thi thử hôm nay -- thứ anh nhận ở cuối buổi họp tối qua sau khi mọi thứ đã được thống nhất xong. Anh treo balo lên móc, một chiếc móc đã hơi nghiêng sang phải vì nhiều năm phải gánh quá nhiều áo khoác mùa thi. Rồi anh rót một chút nước từ bình lọc mà ai đó đã thay từ sớm, nhấp một ngụm nhỏ, để chất nước lạnh đánh thức cơ thể trước khi bắt tay vào công việc quen thuộc.

SOTan ngồi xuống chỗ của mình -- không phải ghế được phân công, mà là cái ghế anh vẫn hay ngồi mỗi lúc kiểm tra hồ sơ. Chỗ đó, theo cách nào đó, đã trở thành vị trí "tự nhiên mà thành" của anh qua nhiều mùa thi. Anh đặt bìa hồ sơ lên mặt bàn, vuốt nhẹ bìa giấy đã hơi nhăn ở góc, rồi bắt đầu mở từng tờ một. Trong bộ hồ sơ, giữa các tài liệu phân công nhiệm vụ, lịch ca trực, bản hướng dẫn setup máy chiếu và thiết bị mạng, có một tờ phiếu được kẹp riêng. Tờ phiếu ghi nhận vật tư -- thứ mà CLB vẫn dùng từ nhiều thế hệ thành viên trước. Nó không có màu sắc hấp dẫn, cũng không có ký hiệu phức tạp. Chỉ là một mẫu giấy trắng với hai dòng ghi chú được viết bằng bút mực xanh.

Trên phiếu, như mọi khi, là hai dòng thông tin quen thuộc: một phần vật tư được chuẩn bị từ buổi tối hôm trước, gọn gàng xếp vào hộp nhựa trong kho; và một phần vật tư được bổ sung thêm vào sáng nay, sau khi đội hậu cần kiểm tra lại lượng đồ còn dư từ tuần trước.

SOTan dừng lại vài giây, nhìn hai con số ấy -- ký hiệu là ~X~ và ~Y~. Anh đưa ngón tay vuốt nhẹ mép giấy, như thói quen của người luôn muốn đảm bảo mọi thứ nằm đúng vị trí của nó trước khi bắt đầu. Không phải để kiểm tra, mà như để tâm trí mình hòa vào nhịp làm việc quen thuộc.

Khi đến giờ mang đồ ra phòng thi, người phụ trách vật tư sẽ cần xác định một con số cuối cùng -- con số phản ánh toàn bộ vật tư nằm trong hai phần ấy. Phiếu được ghi riêng cho dễ đối chiếu, nhưng con số cần mang đi luôn được xác định dựa trên việc tính đủ cả hai phần đã ghi lại. Không ai nói ra, nhưng từ nhiều năm nay, mọi thành viên đều hiểu rằng: khi hai con số đã nằm trên phiếu, người chuẩn bị chỉ cần dựa trên đó để xác định giá trị cuối cùng của cả hai phần, đầy đủ và gọn gàng trước khi bước ra khỏi căn phòng này.

Yêu cầu

Hãy xác định con số mà SOTan sẽ ghi lại trên phiếu, dựa trên hai giá trị ~X~ và ~Y~ ghi nhận trên hai phần vật tư.

Dữ liệu vào

Vào từ thiết bị chuẩn có khuôn dạng:

• Một dòng gồm hai số nguyên dương ~X~ và ~Y~ ~(1 \leq X, Y \leq 10^9)~.

Dữ liệu ra

Ghi ra thiết bị chuẩn một số nguyên duy nhất -- giá trị thể hiện lượng vật tư đầy đủ khi cả hai phần đều được tính đủ.

Ví dụ

Dữ liệu vào

4 9

Dữ liệu ra

13

Ngày hội Gặp gỡ Tân Sinh viên của Khoa Công nghệ năm nay diễn ra trong không khí rộn ràng và háo hức. Từ sảnh lớn cho đến từng gian trưng bày, đâu đâu cũng phảng phất sự tươi mới của những gương mặt lần đầu bước chân vào con đường học thuật. Thế nhưng, giữa tất cả sắc màu rực rỡ ấy, có một góc nhỏ lại thu hút ánh nhìn của không ít sinh viên: bảng trưng bày thành tích của chị AnnVo.

Đối với nhiều người, đó đơn thuần là một bảng thành tích được trang trí cho đẹp mắt. Nhưng với chị AnnVo -- cố vấn tận tâm của CLB APC -- bảng ấy chứa đựng nhiều hơn thế. Nó là hành trình của kiến thức, là kỷ niệm của những mùa hoạt động đã qua, và cũng là thông điệp chị muốn gửi gắm đến thế hệ sinh viên mới: rằng nỗ lực học thuật sẽ luôn được trân trọng.

Bảng thành tích gồm một hàng ngang với ~n~ vị trí. Tại mỗi vị trí, chị đặt vào đó một chứng nhận học thuật, thuộc một trong hai loại:

• A -- Huy chương Olympic, biểu tượng cho tư duy sắc bén và tinh thần thi đấu không ngừng bỏ cuộc.
• B -- Bằng khen Nghiên cứu Khoa học, tượng trưng cho sự sáng tạo, kiên nhẫn và tầm nhìn nghiên cứu.

Thế nhưng trong lúc chuẩn bị gấp rút trước giờ khai mạc, bảng thành tích bị xáo trộn khi vận chuyển. Một vài chứng nhận bị đặt lệch vị trí, màu sắc xen lẫn lộn, khiến tổng thể mất đi sự hài hoà vốn có. Khi chị AnnVo bước đến kiểm tra, chị khựng lại trong giây lát. Sự xáo trộn này không thể qua được đôi mắt quá sức tinh tế của AnnVo, chị liền nói với Nhóm hậu cần bằng giọng trầm ấm nhưng không kém phần nghiêm cẩn:

"Bảng này không chỉ để trưng bày, mà là để kể một câu chuyện. Các chứng nhận của chị phải được sắp xen kẽ tuyệt đối: Olympic rồi Nghiên cứu, hoặc Nghiên cứu rồi Olympic. Không lệch một nhịp nào thì câu chuyện mới trọn vẹn!"

Nói cách khác, dãy thành tích phải trở thành một trong hai mẫu hoàn chỉnh:

ABABAB...      hoặc      BABABA...

Nhóm hậu cần có thể chỉnh lại bằng cách thực hiện mốt số thao tác (có thể không thực hiện thao tác nào) có dạng:

Chọn một vị trí bất kỳ và đổi loại chứng nhận ở đó: A ↔ B.

Không lo thiếu chứng nhận vì chị AnnVo luôn chuẩn bị dư để phòng bất trắc. Nhưng thời gian trước khai mạc không còn nhiều, và bảng thành tích -- vốn là niềm tự hào của chị -- cần phải đạt vẻ chỉn chu nhất. Vì vậy, nhóm muốn hoàn thành việc sắp xếp với số thao tác ít nhất.

Yêu cầu

Hãy xác định số thao tác tối thiểu cần thiết để biến dãy bảng thành tích hiện tại thành một dãy xen kẽ hoàn chỉnh theo yêu cầu của chị AnnVo.

Dữ liệu vào

Vào từ thiết bị chuẩn có khuôn dạng:

• Dòng 1: số nguyên ~n~ ~(2 \leq n \leq 10^5)~.
• Dòng 2: một xâu gồm ~n~ ký tự A và B.

Dữ liệu ra

Ghi ra thiết bị chuẩn một số nguyên duy nhất -- số thao tác tối thiểu.

Ví dụ

Dữ liệu vào

4
AAAA

Dữ liệu ra

2

Giải thích

• Có thể đổi thành ABAB hoặc BABA, đều tốn ít nhất 2 thao tác.

Chiều muộn hôm đó, thầy H96 vừa hoàn thành buổi dạy Olympic Tin học cho sinh viên. Buổi học kéo dài với nhiều nội dung nặng về tư duy, từ kỹ thuật quy hoạch động đến các chiến lược code dơ tối ưu hoá; từ cách lựa chọn quán ăn hợp lý đến việc chọn món ăn sao cho tối ưu ví tiền. Sau khi kết thúc bài giảng, thầy cảm thấy mệt và quyết định ghé một quán ăn gần trường để dùng bữa.

Tại khu bếp, thầy nhận thấy trên bàn có một lượng lớn chân gà đã được chuẩn bị sẵn. Quán phục vụ nhiều loại gà khác nhau (ví dụ như gà cựa đỏ, gà KFC, gà Lotte, gà Popeyes, ...), mỗi loại có một số chân cố định, có thể không giống nhau do đặc thù giống gà hoặc cách chế biến (ví dụ gà Tam Hoàng có 3 chân). Nhân viên bếp không còn nhớ chính xác đã dùng bao nhiêu con mỗi loại, chỉ biết rằng tổng cộng hiện có đúng một số lượng chân nhất định.

Giả sử quán có tất cả ~n~ loại gà, được đánh số từ 1 đến ~n~. Mỗi con gà loại ~i~ có đúng ~a_i~ chân. Thầy H96 đếm kỹ và ghi nhận rằng tổng cộng có ~M~ chân gà trên bàn. Với con mắt của một nhà Toán học thuần túy (kiêm nhà văn, tiểu thuyết gia, nhà giáo dục học, ...), thầy liền đặt ra một vấn đề:

Với số chân gà là ~M~, hãy xác định số con gà ít nhất và số con gà nhiều nhất có thể đã được sử dụng, nếu biết rằng mỗi con gà đều thuộc đúng một trong ~n~ loại nói trên.

Nói cách khác, ta xét các nghiệm nguyên không âm (~c_1~, ~c_2~, ..., ~c_n~) thoả mãn:

$$ a_1 c_1 + a_2 c_2 + \dots + a_n c_n = M,\qquad c_i \in \mathbb{Z}_{\ge 0}. $$

Trong tất cả các nghiệm như vậy (nếu tồn tại), ta quan tâm đến:

$$ \text{minCnt} = \min (c_1 + c_2 + \dots + c_n), \qquad \text{maxCnt} = \max (c_1 + c_2 + \dots + c_n). $$

Nếu không tồn tại nghiệm nào, nghĩa là không có cách nào biểu diễn ~M~ chân gà bằng các loại gà đã cho, thì coi như cấu hình hiện tại là không hợp lệ, in ra ~-1~.

Yêu cầu

Hãy giúp thầy H96 xác định giá trị ~minCnt~ và ~maxCnt~, hoặc xác định rằng không tồn tại nghiệm.

Dữ liệu vào

Vào từ thiết bị chuẩn có khuôn dạng:

• Dòng 1: hai số nguyên ~n~, ~M~ ~(1 \le n \le 100,\, 1 \le M \le 10^5)~.
• Dòng 2: ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^5)~.

Dữ liệu ra

Ghi ra thiết bị chuẩn:

• Nếu không tồn tại nghiệm ~(c_1, \dots, c_n)~ thoả mãn
  ~a_1 c_1 + a_2 c_2 + \dots + a_n c_n = M~, ~c_i \ge 0~, hãy in ra: ~-1~

• Ngược lại, hãy in ra hai số nguyên: ~minCnt~ ~maxCnt~, trong đó:

  • ~minCnt~ là số con gà ít nhất có thể,
  • ~maxCnt~ là số con gà nhiều nhất có thể,
    tương ứng với tổng số chân đúng bằng ~M~.

Ví dụ

Dữ liệu vào

3 10
2 3 5

Dữ liệu ra

2 5

Ràng buộc

• Subtask 1 (20 điểm): ~1 \le n \le 2~, ~1 \le M \le 1000~, ~1 \le a_i \le 1000~.
• Subtask 2 (30 điểm): ~1 \le n \le 10~, ~1 \le M \le 2000~, ~1 \le a_i \le 1000~.
• Subtask 3 (50 điểm): Không có ràng buộc nào thêm.

CLB Lập trình APC tổ chức các buổi training định kỳ cho thành viên. Sau mỗi buổi, hệ thống chấm tự động sẽ ghi lại một chỉ số hiệu suất (performance score) biểu thị mức độ phong độ của thành viên trong buổi đó.

Trong một học kỳ, hệ thống lưu lại dãy điểm hiệu suất: $$ a_1, a_2, \dots, a_n $$ trong đó ~a_i~ là điểm hiệu suất của thành viên ở buổi training thứ ~i~.

Ban Cố vấn sử dụng dashboard để theo dõi phong độ theo thời gian và cần hai chức năng quan trọng:

1. Cập nhật điểm của một buổi training: Do lỗi nhập liệu hoặc sai sót từ hệ thống chấm, Ban Kỹ thuật có thể cần chỉnh giá trị của một buổi: ~a_i := x.~

2. Phân tích chuỗi tiến bộ liên tiếp: Một chỉ số quan trọng để đánh giá sự tiến bộ là độ dài của chuỗi tăng dần liên tiếp.
   Cụ thể, trong đoạn từ ~l~ đến ~r~, Ban Cố vấn muốn biết độ dài lớn nhất của một đoạn con liên tiếp:
   ~a_L < a_{L+1} < a_{L+2} < \dots < a_R~, với ~l \le L \le R \le r~.

Yêu cầu

Bạn được giao nhiệm vụ xây dựng hệ thống xử lý tất cả các thao tác trên.

Dữ liệu vào

Vào từ thiết bị chuẩn có khuôn dạng:

• Dòng 1: hai số nguyên ~n~ và ~q~ - số buổi training và số thao tác.
• Dòng 2: ~n~ số nguyên ~a_1, a_2, \dots, a_n~ - điểm hiệu suất ban đầu.
• Mỗi trong số ~q~ dòng tiếp theo mô tả một thao tác theo một trong hai dạng:
  • 1 i x - gán ~a_i := x~.
  • 2 l r - truy vấn độ dài đoạn tăng dần liên tiếp dài nhất trên đoạn ~[l, r]~.

Dữ liệu ra

Với mỗi truy vấn dạng 2 l r, hãy ghi ra thiết bị chuẩn một số nguyên duy nhất -- độ dài lớn nhất của một đoạn con liên tiếp tăng dần trong đoạn ~[l, r]~.

Ví dụ

Dữ liệu vào

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

Dữ liệu ra

3
5
3
2

Ràng buộc

• Subtask 1 (20 điểm): ~1 \le n, q \le 2000~.
• Subtask 2 (30 điểm):không có thao tác cập nhật (chỉ xuất hiện thao tác loại 2 l r).
• Subtask 3 (50 điểm): Không có ràng buộc gì thêm.

Trong những ngày CLB APC mở đợt training lập trình kéo dài ~n~ buổi, phòng học lúc nào cũng rộn ràng tiếng gõ phím và những cuộc bàn luận chiến thuật giải bài.
Nhưng giữa không khí nghiêm túc ấy, có một bóng hình bí ẩn luôn khiến Groot (a.k.a vuivethoima) phải đau đầu -- PhucHuynh, bậc thầy tàng hình của CLB.

Mặc dù rất đam mê trốn training, PhucHuynh cũng hiểu rõ một điều: trốn liên tục hai buổi là coi như tự nộp mình cho Groot. Thế nên mỗi buổi trốn, em đều thực hiện với tinh thần kính kếp, thận trọng như tránh bẫy của Bruce.

Tuy nhiên, ở một góc nào đó trong tim, PhucHuynh vẫn biết mình phải học hành tử tế để không trở thành gánh nặng tinh thần cho đội. Vì vậy, em tự đưa ra mục tiêu:

• Không bao giờ trốn 2 buổi liên tiếp.
• Phải đi học ít nhất ~k~ buổi, để còn kịp theo mọi người trước ngày thi.

Yêu cầu

Bạn được giao nhiệm vụ thống kê xem PhucHuynh có bao nhiêu cách "vừa học đủ, vừa trốn hợp lý". Mỗi lịch training là một chuỗi độ dài ~n~, gồm:

• A - Attend: đi học.
• S - Skip: trốn một buổi một cách tinh vi.

Hãy đếm số chuỗi thoả mãn:

• Không chứa đoạn SS.
• Có ít nhất ~k~ ký tự A.

Vì số lượng lịch training có thể rất lớn, hãy in ra đáp án modulo ~10^9 + 7~.

Dữ liệu vào

Vào từ thiết bị chuẩn có khuôn dạng:

• Một dòng gồm hai số nguyên ~n~ và ~k~ ~(1 \le n \le 2000, 0 \le k \le n)~ - tổng số buổi training và số buổi tối thiểu PhucHuynh phải đi học.

Dữ liệu ra

Ghi ra thiết bị chuẩn một số nguyên duy nhất - số lượng lịch training hợp lệ modulo ~10^9 + 7~.

Ví dụ

Dữ liệu vào

3 2

Dữ liệu ra

4

Giải thích

• Các lịch hợp lệ mà PhucHuynh có thể "di chuyển âm thầm": AAA, AAS, ASA, SAA. Tổng cộng có 4 cách.

Ràng buộc

• Subtask 1 (25 điểm): ~1 \le n \le 20, 1 \le k \le n~
• Subtask 2 (25 điểm): ~k = 0~
• Subtask 3 (50 điểm): Không có ràng buộc nào thêm.

Sau khi chinh phục bài chạy xoắn ốc trên sân vận động mà không tỏ ra chút mệt mỏi nào, Bruce còn buông một câu đầy tự tin:

"Có gì khó hơn thì đưa luôn đi, chứ cái sân đó nhẹ quá :)."

Soraino tất nhiên không bỏ lỡ cơ hội. Sáng hôm sau, Bruce nhìn thấy trên bàn mình một bản đồ chạy bộ mới, lần này không còn là ma trận hay xoắn ốc nữa mà là một hệ thống nút giao phức tạp cùng các đoạn đường nối giữa chúng. Có ~N~ nút giao, có ~M~ đoạn đường vô hướng, và giữa hai nút bất kỳ không có quá một đoạn đường. Toàn bộ hệ thống được thiết kế theo mô hình ``xương rồng'', tức mỗi đoạn đường thuộc không quá một chu trình đơn.

Bruce nhìn sơ qua bản đồ và lập tức nhận ra vấn đề thú vị nhất: giữa những nút giao này có tồn tại các vòng chạy khép kín. Một vòng chạy hợp lệ chính là một chu trình đơn: bắt đầu ở một nút bất kỳ, đi qua các đoạn đường khác nhau, không ghé lại cùng một nút hai lần (ngoại trừ quay về điểm xuất phát). Và dù không nói thành lời, việc Bruce bắt đầu cầm bút dò theo các đường trông đủ để biết anh đang tự hỏi vòng chạy dài nhất trong hệ thống này sẽ có bao nhiêu đoạn đường.

Nhiệm vụ của bạn là giúp Bruce trả lời đúng câu hỏi đó: hãy tìm độ dài của chu trình đơn dài nhất trong bản đồ Soraino đưa ra. Nếu không tồn tại chu trình nào, hãy in ra 0.

Dữ liệu vào

Vào từ thiết bị chuẩn:

• Dòng đầu chứa hai số nguyên ~N, M~ ~(1 \leq N \leq 5000, 1 \leq M \leq 10000)~.
• ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ ~(1 \leq u, v \leq N, u \neq v)~ mô tả một đoạn đường vô hướng.

Bảo đảm rằng không tồn tại đa cạnh và mỗi đoạn đường thuộc không quá một chu trình đơn.

Dữ liệu ra

Ghi ra một số nguyên duy nhất - độ dài của chu trình đơn dài nhất. Nếu không tồn tại chu trình nào, in 0.

Ví dụ

Dữ liệu vào

7 8
3 4
1 4
1 3
7 1
2 7
7 5
5 6
6 2

Dữ liệu ra

4

Minh họa

Chu trình đơn dài nhất là ~7 \rightarrow 5 \rightarrow 6 \rightarrow 2 \rightarrow 7~, gồm ~4~ đoạn đường.

Ràng buộc

• Subtask 1 (30 điểm): ~N, M \leq 2000~.
• Subtask 2 (70 điểm): Không có ràng buộc nào thêm.