Bài tập

\begincenter

\endcenter

Cho một xâu gồm \(n\) kí tự \(a - z\). Các kí tự trong xâu được đánh số từ \(1 - n\).
Cho \(m\) truy vấn, gồm \(2\) loại:

• \(1\) \(k\) \(x\) : thay đổi kí tự ở vị trí k thành kí tự x (truy vấn loại 1)
• \(2\) \(a\) \(b\) : kiểm tra xem xâu con [a..b] có phải là xâu đối xứng hay không. (truy vấn loại 2)

Input

Dòng đầu tiên chứa hai số nguyên dương \(n, m\) - số lượng kí tự và số truy vấn.

Dòng thứ hai là một xâu có \(n\) kí tự.

\(m\) dòng tiếp theo, mỗi dòng là truy vấn loại 1 hoặc truy vấn loại 2

Output

Với mỗi truy vấn loại 2, in ra "YES" nếu xâu con đó là xâu đối xứng, ngược lại in "NO".

Example

7 5
aybabtu
2 3 5
1 3 x
2 3 5
1 5 x
2 3 5

YES
NO
YES

Scoring

Có \(50\) phần trăm số test có \(n, m <= 1000\).

\(50\) phần trăm số test còn lại có \(n, m <= 2.10^5\).

Trong một kỳ thi, việc sáng tạo bài dễ nhất trong đề thi nhiều khi cũng mất không ít thời gian. Trong đề thi Duyên Hải năm 2021, Ban giám khảo muốn tạo một bài dễ thao tác trên dãy số cho các học sinh khối 10. Bài toán dưới đây đã được sáng tạo và chọn vào đề thi, bài toán này có thể giải được bằng nhiều thuật toán khác nhau.

Cho dãy số nguyên \(a_1, a_2, ..., a_n\), một đoạn \(a_L, a_{L+1},..., a_R (1 \le L \le R \le N)\) được gọi là đoạn đẹp nếu \(L, R\) đều là số nguyên tố. Hãy tìm đoạn đẹp có tổng lớn nhất.

Input

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

• Dòng đầu chứa số nguyên dương \(n (n \ge 2)\);

• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n (|a_i| \le 10^6)\)

Output

• Ghi ra thiết bị ra chuẩn một số nguyên là tổng lớn nhất của đoạn đẹp tìm được.

Example

6
9 5 -2 6 -1 1

8

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 100\);

• Subtask \(2\) (\(30\%\) số điểm): \(n \le 3000\);

• Subtask \(3\) (\(30\%\) số điểm): \(n \le 10^6\);

Cho một bảng hình chữ nhật kích thước \(m \times n\) được chia thành lưới ô vuông đơn vị \(m\) hàng, \(n\) cột. Các hàng được đánh số từ \(1\) tới \(m\) theo thứ tự từ trên xuống dưới và các cột được đánh số từ \(1\) tới \(n\) theo thứ tự từ trái qua phải.

Người ta tiến hành tô màu các ô của bảng theo từng cột: Các ô trên mỗi cột \(j\) sẽ được tô từ trên xuống dưới: \(h_j\) ô màu vàng tiếp đến là \(m - h_j\) ô màu xanh. Như vậy, tình trạng màu trên bảng hoàn toàn xác định nếu ta biết được số hàng \(m\), số cột \(n\) và các số nguyên \(h_1, h_2, \ldots, h_n\).

\begincenter

\endcenter

Yêu cầu: Hãy xác định một hình chữ nhật gồm các ô trắng đã cho thỏa mãn các yêu cầu sau:

• Có cạnh song song với cạnh bảng.
• Đơn sắc (chỉ gồm các ô vàng hoặc chỉ gồm các ô xanh).
• Diện tích lớn nhất có thể.

Input

• Dòng \(1\): Chứa hai số nguyên dương \(m\), \(n\) \((n \leq 5 \times 10^5)\).
• Dòng \(2\): Chứa \(n\) số nguyên \(h_i\).

Output

• Ghi ra một số nguyên duy nhất là diện tích hình chữ nhật tìm được.
• Các số trên một dòng của input files được ghi cách nhau ít nhất một dấu cách.

Example

5 9
1 3 4 4 5 4 4 3 1

21

Scoring

• \(20\%\) số test có \(n \leq 100\).
• \(20\%\) số test có \(n \leq 1000\).
• \(30\%\) số test có dãy \(h\) là dãy tăng dần.
• \(30\%\) số test không có ràng buộc gì thêm.