Tuấn là một học sinh rất yêu thích Tin học. Ước mơ của cậu sau này là trở thành một lập trình viên tài năng. Tuấn thường xuyên tìm hiểu các thông tin, sự kiện liên quan đến Công nghệ. Một sự kiện công nghệ nổi tiếng trên toàn thế giới trong thời gian gần đây là sự ra mắt robot thông minh ChatGPT của công ty công nghệ OpenAI. Tuấn cũng rất tò mò về ChatGPT nên đã sử dụng để giải bài toán. Bài toán mà Tuấn đưa cho ChatGPT như sau:
Cho số nguyên dương \(n\). Tìm số lượng các số nguyên dương \(x\) nhỏ hơn \(n\) thỏa mãn: \(x\) và \(n\) là hai số nguyên tố cùng nhau (tức là ước chung lớn nhất của \(x\) và \(n\) bằng 1).

Thật là thú vị, khi Tuấn nhập \(n = 5\). ChatGPT đưa ra kết quả là: Có 4 số, cụ thể là các số: \(1, 2, 3, 4\). Tuấn muốn các bạn lập trình giải bài toán này để cùng kiểm tra kết quả của ChatGPT nhé.

Input: Dữ liệu cho trong tệp văn bản NTCN.INP gồm một số nguyên dương \(n\ (2 ≤ n ≤ 2 \times 10)\).
Output: Kết quả ghi ra tệp văn bản NTCN.OUT gồm một số nguyên duy nhất là số lượng các số nguyên dương \(x\), nhỏ hơn \(n\) và nguyên tố cùng nhau với \(n\).

Scoring

• Có 50% số test ứng với 50% số điểm thỏa mãn: \(2 ≤ n ≤ 2000\).
• Có 40% số test ứng với 40% số điểm thỏa mãn: \(2000<n≤2×10^6\)
• Có 10% số test ứng với 10% số điểm thỏa mãn: \(2 × 10^6 <n≤2 \times 10^9\)

Example

5

4

10

4

Ngôi trường của Tuấn chuẩn bị kỉ niệm ngày thành lập trường. Nhà trường đã trồng một hàng cây xanh trông rất đẹp. Hàng cây gồm \(n\) cây xanh được đánh số thứ tự từ 1 đến \(n\) (theo hướng từ trái sang phải) và cách đều nhau, tức là khoảng cách giữa hai cây kề nhau là không đổi.

Để tưới nước cho cây, nhà trường có kế hoạch lập đặt \(m\ (1 \le m ≤ n)\) vòi tưới nước tự động. Vòi nước thứ \(i\ (i = 1,2,3,...,m)\) được lắp tại vị trí cây thứ \(X_i\) thì có thể tưới nước cho cây thứ \(X_i\), và \(R_i\) cây liền kề bên trái và \(R_i\) cây liền kề bên phải vòi nước đó, tức là vòi thứ \(i\) sẽ tưới nước được cho cây thứ j nếu \(|j − x_i| ≤ R_i\). \(R_i\) được gọi là bán kính tưới nước của vòi thứ \(i\).

Cho biết vị trí lắp \(m\) vòi nước tại m \(x^2\)cây có số thứ tự là \(X_1, X_2, ..., X_m\ (1 \le X_1 \le X_2 \le ...X_m \le n)\) và các bán kính tưới nước là \(R+1, R_2, ..., R_m\ (1 \le R_1 \le R_2 \le Rm \le 100)\).

Yêu cầu: Tính xem, có bao nhiêu cây được tưới nước khi lắp \(m\) vòi nước tự động như trên. Một cây được tưới nước nếu có ít nhất một vòi nước có thể tưới nước cho cây đó.

Input: Dữ liệu cho trong tệp văn bản HANGCAY.INP gồm:

• Dòng 1 ghi hai số nguyên dương \(n\) và \(m\ (2<n≤2000; 1≤ m ≤ n)\) tương ứng là số cây và số vòi nước.
• \(m\) dòng tiếp theo, dòng thứ \(i\ (i = 1, 2, ...,m)\) ghi hai số nguyên \(X_i, R_i\). Trong đó \(X_i\) là số thứ tự của cây đặt vòi nước thứ \(i\), \(R_i\) là bán kính tưới nước.

Output: Kết quả ghi ra tệp văn bản HANGCAY.OUT gồm một số nguyên duy nhất là số cây được tưới nước

Scoring

• Có 30% số test ứng với 30% số điểm thỏa mãn \(2 ≤ n ≤ 200; m = 1\).
• Có 30% số test ứng với 30% số điểm thỏa mãn \(2 \le n≤200; 2 \le m≤n;\) không có hai vòi nước trở lên có thể cùng tưới nước cho 1 cây.
• Có 40% số test ứng với 40% số điểm thỏa mãn \(200 < n \le 2000;2 \le m \le n\)

Example

8 2
2 2
5 1 

6

Ngày thành lập Đoàn 26/3 sắp đến. Tuấn cùng nhóm bạn của mình được giao thiết kế một trò chơi trí tuệ dành cho các đoàn viên trong trường. Sau một thời gian tìm hiểu và nghiện cứu, nhóm của Tuấn đã xây dựng một trò chơi có nội dung như sau:

Một rổ bóng có \(n\) quả bóng. Các quả bóng được đánh số từ 1 đến \(n\). Quả bóng thứ \(i\) có màu được mã hóa bởi một số nguyên dương \(c_i\) (\(1 \le c_i \le k\)), trong đó \(k\) là số màu khác nhau trong \(n\) quả bóng. Mỗi lần chơi, người chơi sẽ chọn hai quả bóng khác màu trong rổ bóng và đưa hai quả bóng này ra khỏi rổ. Người chơi sẽ dừng lại khi trong rổ không còn quả bóng nào hoặc không có hai quả bóng khác màu. Số bóng được lấy ra khỏi rổ là số điểm của người chơi.

Tuấn cùng nhóm bạn muốn biết người chơi có thể đạt được điểm lớn nhất là bao nhiêu? Bạn hãy lập trình để tìm kết quả này nhé.

Input: Dữ liệu cho trong tệp văn bản CHONBONG.INP gồm:

• Dòng 1 ghi hai số nguyên \(n\) và \(k\) (\(2 \le k \le n \le 2 \times 10^5\)) tương ứng là số quả bóng trong rổ và số màu khác nhau của \(n\) quả bóng.
• Dòng 2 ghi \(n\) số nguyên dương \(c_1, c_2, ..., c_n\) (\(1 \le c_i \le k\) ) tương ứng là mã màu của quả \(n\) bóng

Output: Kết quả ghi ra tệp văn bản CHONBONG.OUT gồm một số nguyên duy nhất là số điểm lớn nhất người chơi có thể nhận được.

Scoring

• Có 20% số test ứng với 20% số điểm thỏa mãn \(2 ≤ n ≤ 2000\); \(k = 2\).
• Có 30% số test ứng với 30% số điểm thỏa mãn \(3 ≤ n ≤ 2000; k = 3\).
• Có 30% số test ứng với 30% số điểm thỏa mãn \(4 ≤ n ≤ 2000; 3< k \le n\)
• Có 20% số test ứng với 20% số điểm thỏa mãn \(2000<n≤2 \times 10^5;3<k \le n\)

Example

6 2
1 2 2 1 1 1

4

4 3
3 3 1 2

4

Trò chơi chọn bóng mà nhóm của Tuấn thiết kế được bạn bè và giáo viên trong trường đánh giá rất cao. Sau thành công này, Tuấn cùng nhóm bạn tập trung học tập để thi vào lớp chuyên tin của một trường chuyên danh giá trong tỉnh. Những bài tập mà Tuấn làm đều yêu cầu kỹ năng thiết kế thuật toán chuyên nghiệp. Một trong các bài tập mà bạn ấy đang xây dựng thuật toán có nội dung như sau:

Cho chuỗi kí tự \(S\) chỉ gồm các kí tự chữ cái latinh thường từ a,...,z. Một chuỗi con \(X\) (gồm các kí tự ở vị trí liên tiếp) của \(S\) được gọi là một chuỗi có mật độ xuất hiện cao nếu trong chuỗi \(X\) có một kí tự mà số lần xuất hiện của kí tự đó nhiều hơn số các kí tự còn lại trong chuỗi \(X\).
Ví dụ: chuỗi \(S =\) abbbabced, chuỗi con \(X =\) abbbabc là một chuỗi có mật độ xuất hiện cao, vì có kí tự b xuất hiện 4 lần, số các kí tự còn lại là 3. Nếu \(X =\) abbbabce, kí tự xuất hiện nhiều lần nhất 4 lần (ki tự b) và số kí tự còn lại là 4. Do vậy chuỗi \(X=\)abbbabce không phải là một chuỗi có mật độ xuất hiện cao.

Yêu cầu: Tìm một chuỗi con \(X\) (gồm các kí tự ở vị trí liên tiếp) của \(S\) là một chuỗi có mật độ xuất hiện cao và độ dài lớn nhất.

Tuấn cũng đã có thuật toán của mình, còn bạn thì sao? Hãy lập trình giải bài toán trên để đối chiếu kết quả nhé.

Input: Dữ liệu cho trong tệp văn bản MATDO.INP gồm một chuỗi kí tự \(S\) chỉ gồm các kí tự chữ cái latinh thường và có độ dài không lớn hơn 2 × 105.

Output: Kết quả ghi ra tệp văn bản MATDO.OUT gồm một số nguyên duy nhất là số điểm lớn nhất người chơi có thể nhận được.

Scoring

• Có 20% số test ứng với 20% số điểm thỏa mãn \(2 ≤ n ≤ 2000\); \(k = 2\).
• Có 30% số test ứng với 30% số điểm thỏa mãn \(3 ≤ n ≤ 2000; k = 3\).
• Có 30% số test ứng với 30% số điểm thỏa mãn \(4 ≤ n ≤ 2000; 3< k \le n\)
• Có 20% số test ứng với 20% số điểm thỏa mãn \(2000<n≤2 \times 10^5;3<k \le n\)

Example

abbbabced

7

ababab

5