Một chuỗi ký tự A có thể tạo ra các chuỗi mới bằng cách lấy một ký tự ở đầu chuyển xuống cuối chuỗi (phép xoay vòng). Cho hai chuỗi A và B, hãy kiểm tra xem chuỗi B có phải là một trạng thái xoay vòng của chuỗi A hay không.

Input:

Dòng 1: Chuỗi A (Độ dài <= 10^5).

Dòng 2: Chuỗi B (Độ dài <= 10^5).

Output: In YES nếu đúng, ngược lại in NO.

Ví dụ:

Input:

abcde
cdeab

Output:

YES

Sự cân bằng của hệ thống phụ thuộc vào một mảng A gồm N số tự nhiên. Bạn cần tìm ra một dải các phần tử liên tiếp nhau trong mảng A có độ dài lớn nhất sao cho "số lượng số chẵn" trong dải đó bằng đúng "số lượng số lẻ".

Input:

Dòng 1: N (1 <= N <= 10^5).

Dòng 2: N số nguyên Ai (0 <= Ai <= 10^9).

Output: Độ dài của dải liên tiếp dài nhất thỏa mãn. Nếu không có, in 0.

Ví dụ:

Input:

6
2 4 1 3 6 8

Output:

4

(Giải thích: Dải [4, 1, 3, 6] có 2 số chẵn (4,6) và 2 số lẻ (1,3)).

Máy chủ nhận được N tác vụ, tác vụ thứ i tốn A_i giây xử lý. Máy chủ có K nhân CPU. Bạn cần chia N tác vụ này (giữ nguyên thứ tự ban đầu) thành đúng K đoạn liên tiếp nhau, mỗi nhân CPU sẽ xử lý 1 đoạn. Thời gian xử lý của một nhân CPU bằng tổng thời gian các tác vụ trong đoạn nó nhận. Để tối ưu hiệu suất, hãy tìm cách chia sao cho nhân CPU mất nhiều thời gian nhất có thời gian xử lý là nhỏ nhất.

Input:

Dòng 1: N, K (1 <= K <= N <= 10^5).

Dòng 2: N số nguyên Ai (1 <= Ai <= 10^4).

Output: Thời gian xử lý cực đại nhỏ nhất.

Ví dụ:

Input:

5 2
7 2 5 10 8

Output:

18

(Giải thích: Chia thành [7, 2, 5] (tổng 14) và [10, 8] (tổng 18). CPU lâu nhất là 18s).

Bạn biết trước giá cổ phiếu của một công ty trong N ngày tới, giá ngày thứ i là P_i. Bạn được phép mua và bán nhiều lần để kiếm lời, nhưng phải tuân thủ luật: Bạn không thể nắm giữ quá 1 cổ phiếu tại cùng 1 thời điểm; và sau khi bán cổ phiếu, bạn bắt buộc phải nghỉ ngơi 1 ngày (không được mua vào ngày hôm sau, gọi là ngày đóng băng - cooldown). Tính lợi nhuận lớn nhất bạn có thể thu được.

Input:

Dòng 1: N (1 <= N <= 10^5).

Dòng 2: N số nguyên Pi (0 <= Pi <= 10^4).

Output: Lợi nhuận cực đại.

Ví dụ:

Input:

5
1 2 3 0 2

Output:

3