BÀI TEST TÍNH NĂNG TRẮC NGHIỆM (QUIZ)

Đây là bài kiểm tra thử nghiệm tính năng trắc nghiệm mới trên hệ thống UMTOJ.

Thông tin bài tập:

• Số lượng câu: 30 câu.
• Lưu ý quan trọng: Hệ thống đã kích hoạt chế độ One-shot (Nộp 1 lần). Bạn sẽ không thể sửa lại bài sau khi đã bấm nộp.

Yêu cầu:

1. Làm đủ các câu hỏi.
2. Test thử khả năng hiển thị công thức Toán học.
3. Bấm nộp bài và xem kết quả chấm tự động.

Thầy Thư luôn có những bài giảng về lập trình và đạo đức nghề nghiệp rất sâu sắc. Thầy nhấn mạnh rằng không có gì là hoàn hảo và phải biết vượt qua những khó khăn để có thể không ngừng học hỏi trở thành các lập trình viên chân chính. Trong bài này, chúng ta sẽ cùng tìm hiểu một trong các bài giảng của thầy về xử lý chuỗi. Thầy rất thích các chuỗi ký tự non-palindrome, không đối xứng (là chuỗi mà đảo ngược của nó khác với chuỗi ban đầu). Thầy gọi những chuỗi như vậy là đẹp vì thầy thích những điều không hoàn hảo. Với một chuỗi s cho trước, thầy muốn cắt nó ra thành nhiều chuỗi con rời nhau mà số chuỗi đẹp thu được là càng nhiều càng tốt (tất nhiên trong số đó vẫn có thể xen lẫn các chuỗi không đẹp).

Ví dụ: với chuỗi ~s_1 = abcabc~, thầy có thể cắt thành ~ab, ca, bc~ là được 3 chuỗi đẹp; còn với chuỗi ~s_2 = xyzz~ thì thầy có thể cắt thành ~xyz~ và ~z~ thì được 1 chuỗi đẹp là ~xyz~ (còn ~z~ là đối xứng nên không đẹp), chú ý rằng thầy cũng có thể giữ nguyên chuỗi ~s_2~ ban đầu vì nó cũng là một chuỗi đẹp, việc cắt ra không làm tăng số lượng chuỗi đẹp (điều này cho thấy để ra được số lượng chuỗi đẹp lớn nhất là 1, ta có thể có nhiều cách cắt); còn với chuỗi ~s_3 = cccc~ thì không có cách cắt nào để tạo thành chuỗi đẹp nên kết quả sẽ là 0. Trong một buổi thi vấn đáp, thầy có nhiều sinh viên (không quá ~10^4~ em) và có một chuỗi ký tự gốc là s. Thầy muốn giao task cho mỗi sinh viên lấy một chuỗi con từ vị trí ~L~ đến ~R~ nào đó trong s và cắt nó ra thành càng nhiều chuỗi đẹp càng tốt. Để đổi đề cho mới lạ, có thể đôi lúc thầy còn chọn một vị trí bất kỳ trong s và sửa nó lại thành một ký tự khác. Là lớp trưởng gương mẫu, Tiến được thầy giao cho giải hết số bài tập này trước để thầy có đáp án mà check với các bạn coi làm đúng hay sai. Bạn hãy cùng giúp Tiến thực hiện công việc này nhé.

Input

Dòng đầu tiên là một chuỗi s có độ dài n không vượt quá 104 gồm các ký tự tiếng Anh viết thường. Dòng tiếp theo là một số q cho biết số lượng câu hỏi mà thầy đặt ra cho CLB, trong đó ~1 ≤ q ≤ 10^5~. Mỗi dòng tiếp theo trong q dòng sẽ có một trong hai dạng:

• Dạng 1: gồm một số nguyên ~k~ với ~1 ≤ k ≤ n~ và một ký tự ~c~ nào đó, cho biết sẽ gán ~s[k] = c~.

• Dạng 2: gồm hai số nguyên L, R với 1 ≤ L ≤ R ≤ n, yêu cầu tính số lượng chuỗi đẹp nhiều nhất có thể cắt ra được từ chuỗi con xét từ vị trí ~L~ đến vị trí ~R~. Cho biết rằng có không quá ~10^4~ câu hỏi loại này.

Output

Hãy trả lời tất cả các câu hỏi dạng 2 ở các dòng khác nhau.

Sample Input 1

abcabc
3
2 1 6
1 2 a
2 1 6

Sample Ouput 1

3
2

Giải thích

Chuỗi ban đầu có thể cắt thành 3 chuỗi đẹp, sau khi sửa ký tự 2 thành ~a~ thì có chuỗi mới là ~aacabc~, dễ dàng kiểm tra được chỉ có thể cắt nó được thành tối đa 2 chuỗi đẹp, chẳng hạn: ~aa, ca, bc~ (gồm 2 chuỗi đẹp và 1 chuỗi không đẹp) hoặc ~aaca, bc~.

Subtask:

• Subtask 1 (50% số điểm): ~n ≤ 10~.

• Subtask 2 (50% số điểm): Không giới hạn gì thêm.

Trong buổi phỏng vấn để giành chức vụ Cố vấn cao cấp của CLB lập trình UMT, hai coder An và Khang đã biểu diễn nhiều kỹ năng coding đỉnh cao của mình cho các thầy xem. Do qua nhiều vòng nhưng chưa phân thắng bại, trong vòng cuối, MC Sơn Tân quyết định rằng sẽ dựa theo số phận để lựa chọn. Biết rằng An sinh vào tháng 9, còn Khang sinh vào tháng 11 nên MC đã cho ngẫu nhiên một số ~n~ và bỏ đi một vị trí bất kỳ trong đó, MC yêu cầu hai bạn chọn một số để điền vào vị trí kia sao cho số thu được chia hết cho tháng sinh của mình (cho phép số 0 đứng đầu). Ai thu được số lớn hơn (hoặc người kia không điền được số vào) thì thắng cuộc (tất nhiên ai cũng muốn điền số càng lớn càng tốt), còn nếu không phân thắng bại thì MC Sơn Tân sẽ giữ chức vụ này luôn.

Input

Dòng đầu tiên gồm số bộ test ~T~ với ~1 ≤ T ≤ 5~. Trong các dòng tiếp theo, mỗi dòng có duy nhất một số n có giá trị không vượt quá ~10^100000~ (nghĩa là số chữ số của nó không quá 100000), trong đó có một vị trí được điền bởi dấu ?.

Output

Tên của Cố vấn cao cấp được chọn: An, Khang hay Son Tan.

Sample Input 1

3
202?
8?
?9

Sample Ouput 1

An
Khang
Son Tan

Giải thích

Trong Ví dụ 1, An chỉ có thể thay ? bởi 5 để được 2025 chia hết cho 9, còn Khang chỉ có thể thay ? bởi 4 để được 2024 chia hết cho 11; vì số của An lớn hơn nên An thắng. Trong Ví dụ 2, An thay 1 còn Khang thay 8 nên Khang thắng. Trong Ví dụ 3, cả An và Khang sẽ đều thay 9 nhưng khi đó hoà nên Sơn Tân thắng.

Subtask:

• Subtask 1 (40% số điểm): các giá trị đều không quá 5 chữ số.

• Subtask 2 (60% số điểm): Không giới hạn gì thêm.