Orange Ami

ami có một xâu kí tự nhị phân \(S\) định làm quà tặng cho đội trưởng đội tuyển quốc gia tin học Thanh Ngọc nhân dịp đội trưởng đạt được một tầm cao mới trên Codeforces. Thanh Ngọc là một người đơn giản, nhưng vô cùng tinh tế, cậu không thích những thứ quá lớn. Do đó, Thanh Ngọc đã đánh giá mòn quà của ami qua \(q\) câu hỏi, mỗi câu hỏi là một số tự nhiên \(k\). ami cần trả lời xem, với mỗi số tự nhiên \(k\) có tồn tại một đoạn con liên tiếp của xâu \(S\) mà tổng các kí tự trong đoạn con này đúng bằng \(k\) hay không.

Do ami quá bận rộn, các bạn hãy giúp ami trả lời câu hỏi này nhé.

Input

• Dòng đầu tiên chứa một số nguyên dương \(n\) là độ dài xâu \(S\) của ami.
• Dòng tiếp theo chứ xâu \(S\) độ dài đúng bằng \(n\).
• Dòng tiếp theo là một số nguyên dương \(q\) là số câu hỏi mà Thanh Ngọc sẽ hỏi.
• \(q\) dòng cuồi cùng, mỗi dòng là một số nguyên không âm \(k\) là một câu hỏi của Thanh Ngọc.

Output

• In ra \(q\) dòng, với mỗi dòng, in "Ami Dep Trai" nếu tồn tại một đoạn con liên tiếp của \(S\) có tổng bằng \(k\), hoặc in ra "Luong Xiao Lin" trong trường hợp ngược lại.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n , k \leq 10^3, q \leq 10^5\)

• Subtask \(2\) (\(70\%\) số điểm): \(n, q , k \leq 10^5\)

Example

3
110
3
1
2
100000

Ami Dep Trai
Ami Dep Trai
Luong Xiao Lin

Cho \(n\) số nguyên dương \(a_1, a_2, ..., a_n\) rải đều trên một đường tròn theo chiều kim đồng hồ. Hãy tìm cung tròn có độ dài nhỏ nhất mà tổng các số trên cung tròn lớn hơn hoặc bằng \(S\). In ra số lượng số trên cung tròn đó. Nếu không có cung tròn nào thỏa mãn thì in ra \(-1\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, S \ (S \leq 10^{18})\).

• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, ..., a_n \ (1 \leq a_i \leq 10^9)\)

Output

• In ra độ dài cung tròn tìm được

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 100\)
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 2000\)
• Subtask \(3\) (\(40\%\) số điểm): \(n \leq 200000\)

Example

5 7
3 1 1 1 4 

2

5 6
1 1 1 1 4

3

7 80
70 11 32 43 43 11 54

2

Gần đây thoi_bay_corona ra bài Không Chia Hết trong đó input gồm hai số \(n, k\). Giới hạn bài toán như sau: \(2 \leq n \leq M; 1 \leq k \leq M\) (trong bài gốc \(M=10^9\)). Tuy nhiên admin phát hiện SPyofgame làm thuật \(O(\frac{k}{n})\) nhưng lại AC. Các admin ngay lập tức ngồi lại tìm hiểu nguyên nhân. Họ nghi ngờ rằng chương trình sinh test của thoi_bay_corona có dạng như sau:

cout << randInt(2, M) << " " << randInt(1, M);

trong đó randInt(a, b) là một hàm trả về một số nguyên ngẫu nhiên trong đoạn \([a, b]\). Nói cách khác chương trình in ra hai số \(n, k\) ngẫu nhiên trong đoạn \([2, M]\) và \([1, M]\)

Biết rằng máy chấm của LQDOJ có thể tính được \(N\) phép tính trong 1s. Vì sao lời giải của SPyofgame lại AC? Hãy giúp các admin tính xác suất mà \(\dfrac{k}{n} \leq N\) nhé.

Input

• Gồm một dòng có 2 số nguyên \(M, N (M \geq 2, N \geq 1)\).

Output

• In ra một số thực là kết quả bài toán. Kết quả sẽ được chấp nhận nếu chênh lệch so với đáp án không vượt quá \(10^{-6}\)

Scoring

• Subask \(1\) (\(30\%\) số điểm): \(M, N \leq 10^6\)
• Subask \(2\) (\(30\%\) số điểm): \(M, N \leq 10^9\)
• Subask \(3\) (\(40\%\) số điểm): \(M, N \leq 10^{18}\)

Example

100 15

0.9797979798

100 10

0.9636363636

Lương Xiao Lin có \(n\) em gái có mức độ yêu thương lần lượt là \(a_1, a_2, ..., a_n\). Lương muốn chọn ra \(k\) cặp em gái rời nhau. Gọi \(x\) là chênh lệch lớn nhất giữa hai bạn trong một nhóm. Vì nếu chênh lệch mức độ yêu thương giữa 2 em gái quá lớn thì có thể một em sẽ buồn. Lương là anh trai cao cả, Lương không muốn em gái nào phải buồn. Do đó, Lương muốn x càng nhỏ càng tốt. Các bạn hãy tìm \(x\) giúp Lương nhé, Lương sẽ chia có các bạn 1 em gái nếu các bạn giúp Lương.

Input

• Dòng đầu có 2 số nguyên \(n, k\).

• Dòng thứ hai có \(n\) số nguyên \(a_1, a_2, \ldots, a_n\)

Output

• In ra một số nguyên là kết quả bài toán

Scoring

• Subtask \(1\) (\(100\%\) số điểm): \(2 \leq n \leq 3 \times 10^5, 1 \leq k \leq \dfrac{n}{2}\) và \(1 \leq a_i \leq 10^9\).

Example

6 3
1 4 3 7 11 9 

3

6 2
1 4 3 7 11 9

2

 6 1
1 4 3 7 11 9

1

Cho \(n\) học sinh có năng lực \(a_1\), \(a_2\),..., \(a_n\). Thầy giáo muốn chọn ra \(k\) cặp học sinh rời nhau. Gọi \(x\) là chênh lệch nhỏ nhất giữa hai bạn trong một nhóm. Thầy muốn \(x\) càng lớn càng tốt. Hãy in ra \(\max x\).

Input

• Dòng đầu có 2 số nguyên \(n, k \ (2 \leq n \leq 3 \times 10^5, 1 \leq k \leq \dfrac{n}{2})\).

• Dòng thứ hai có \(n\) số nguyên \(a_1, a_2, ..., a_n \ (1 \leq a_i \leq 10^9)\)

Output

• In ra một số nguyên là kết quả bài toán

Example

6 2
1 4 3 7 12 9

8

6 1
1 4 3 7 11 9 

10

ami nhận được mật mã người ngoài hành tinh. Mật mã người ngoài hành tinh được viết bằng ngôn ngữ ugnmouc. Để thuận tiện cho các bạn, ami đã dịch thứ ngôn ngữ khó hiểu này sang ngôn ngữ tiếng Anh là xâu \(S\). Ý nghĩa của mật mã này, các bạn không cần biết, các bạn chỉ cần kiểm tra xem mật mã này có ngon hay không.

Tiêu chuẩn ngon của người ngoài hành tinh cũng rất khác biệt. ami sẽ đưa cho các bạn một xâu khác, gọi là \(T\). Xâu \(S\) được xem là ngon nếu có thể chọn ra \(K \geq 1\) xâu con không giao nhau của \(S\), mỗi xâu đều có độ xài \(L\). Tạm gọi các xâu này là \(X_1, X_2, X_3, ..., X_K\), các xâu này phải có thứ tự từ điển nhỏ hơn hoặc bằng xâu \(T\) và \(K \geq C\). ami sẽ cho các bạn xâu \(S\), xâu \(T\) và số \(C\), các bạn cần đếm số lượng số \(L\) để có thể biến xâu \(S\) thành ngon.

Xâu \(X\) được gọi là xâu con của S nếu ta có thể xoá đi một vài kí tự đầu tiên và cuối cùng (có thể không xoá) của \(S\) và thu được xâu \(X\)

Input

• Dòng đầu tiên chứa 2 số nguyên dương \(L_S, L_T,\) và \(C\) lần lượt là chiều dài xâu \(S, T\) và số \(C\).
• Dòng tiếp theo chứa xâu \(S\) có đúng \(L_S\) kí tự.
• Dòng cuối cùng chứa xâu \(T\) có đùng \(L_T\) kí tự.

Output

• In ra một số nguyên là số lượng số \(L\) thoả mãn để biến xâu S thành ngon.

Scoring

• Subtask \(1\) (\(100\%\) số điểm): \(L_S, L_T, C \leq 100000\).

Example

2 1 2
AA
Z 

1