Nguồn ảnh: vietnamnet.vn

Theo tín ngưỡng dân gian Việt Nam, ngày 23 tháng Chạp, Táo Quân (Ông Công Ông Táo) lên chầu trời để báo cáo với Ngọc Hoàng những việc tốt xấu trong năm. Mỗi nhà chuẩn bị lễ vật, thắp hương và thường thả cá chép để các Táo đi đường thủy cho kịp giờ.

Năm nay, vì sông đông, cá chép chỉ chịu được một lượng khói hương tối đa cho mỗi lượt chở. Táo Quân muốn ghé một dải nhà liên tiếp ven sông trong cùng một lượt đi, sao cho tổng khói hương không quá giới hạn.

Có ~N~ nhà đánh số từ ~1~ đến ~N~ theo đúng thứ tự ven sông. Nhà thứ ~i~ dâng một lễ vật có mã số ~A_i~.

Định nghĩa khói hương của một lễ vật là:

~\Omega(x) =~ tổng số thừa số nguyên tố của ~x~ tính cả bội số.

Trong một lượt cá chép chở Táo, tổng khói hương tối đa cho phép là ~K~.

Táo quân sẽ chọn một trong các tòa nhà ~[l..r]~ để ghé trong cùng một lượt, và hợp lệ nếu:

$$\sum_{i=l}^r \Omega(A_i) \leq K$$

Yêu cầu: đếm số lượng đoạn ~[l..r]~ hợp lệ.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~ ~(1 \leq N \leq 2 \times 10^5, 0 \leq K \leq 10^9)~.
• dòng tiếp theo chứa ~N~ số nguyên ~A_1, A_2, \dots, A_n~ ~(1 \leq A_i \leq 10^6)~.

Output

• Gồm một dòng duy nhất chứa một số nguyên là đáp án thỏa mãn yêu cầu đề bài.

Scoring

Example input 1

10 5
1 12 5 64 18 7 100 2 27 30

Example output 1

16

Nguồn ảnh: Báo tuổi trẻ Thủ Đô

Những ngày cuối năm, nhiều gia đình có thói quen dọn nhà đón Tết: lau dọn bàn thờ, sắp xếp lại đồ đạc, bỏ bớt những thứ không cần thiết để nhà cửa gọn gàng, thoáng đãng. Khi dọn, mọi người thường chia khu vực theo "mốc" trên nền nhà (ví dụ theo các ô gạch), để dễ phân công và kiểm tra xem có chỗ nào còn bừa bộn.

Bạn coi mặt sàn nhà là mặt phẳng tọa độ Oxy. Trên sàn có ~N~ vị trí cần kiểm tra (mỗi vị trí là một điểm). Hai vị trí được coi là "gần nhau" nếu chúng nằm trong cùng một vùng hình vuông song song với trục tọa độ có cạnh không vượt quá một giá trị nào đó. Nếu tìm được cặp vị trí "gần nhau" sớm, bạn có thể gom việc dọn chung một lượt.

Có ~N~ điểm phân biệt, điểm thứ ~i~ có tọa độ ~(x_i, y_i)~.

Định nghĩa khoảng cách Chebyshev giữa hai điểm:

$$d_\infty((x_1,y_1),(x_2,y_2)) = \max(|x_1-x_2|,\ |y_1-y_2|)$$

Yêu cầu: hãy tìm giá trị nguyên nhỏ nhất ~D~ sao cho tồn tại hai điểm phân biệt ~i \ne j~ thỏa:

$$d_\infty(P_i, P_j) \le D$$

Nói cách khác, ~D~ là cạnh nhỏ nhất của một hình vuông song song trục có thể chứa được ít nhất 2 điểm.

Input

• Dòng đầu tiên chứa số nguyên ~N~ ~(2 \le N \le 2 \times 10^5)~.
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~x_i, y_i~ ~( -10^9 \le x_i, y_i \le 10^9 )~.

Output

• In ra một số nguyên duy nhất là ~D~ nhỏ nhất thỏa mãn yêu cầu.

Scoring

Example input 1

5
0 0
5 5
3 4
10 0
8 2

Example output 1

2

Nguồn ảnh: cellphones.com.vn

Những ngày giáp Tết, Hà Nội rực rỡ theo một cách rất riêng: sắc đào hồng, cúc vàng, ly trắng, rồi cả những cành mộc lan thanh nhã xuất hiện sớm ở chợ hoa. Chợ đông dần khi trời về khuya, tiểu thương tranh thủ tưới gốc - phun sương - tỉa lá - buộc cành để hoa giữ được độ tươi, nụ "đúng hẹn" lúc khách ghé mua.

Để giảm hao hụt và tiết kiệm công chăm, ban quản lý chợ muốn đồng bộ lịch chăm hoa giữa các sạp. Mỗi sạp chọn một chu kỳ chăm (tính theo phút), và cứ hết một chu kỳ thì sạp đó lại thực hiện một lượt chăm hoa.

Có ~N~ sạp hoa, đánh số từ ~1~ đến ~N~. Sạp thứ ~i~ chọn chu kỳ ~A_i~ (số nguyên dương).

Định nghĩa:

$$LCM(x_1, x_2, \dots, x_n)$$

Là bội chung nhỏ nhất của các số ~x_1, x_2, \dots, x_n~.

Thời điểm sớm nhất mà tất cả sạp cùng rơi vào một mốc chăm trùng nhau sẽ là:

$$LCM(A_1, A_2, \dots, A_N)$$

Ban quản lý đặt mục tiêu: thời điểm đồng bộ sớm nhất phải đúng bằng ~K~ phút.

Yêu cầu: đếm số lượng dãy ~A_1, A_2, \dots, A_N~ ~(A_i > 0)~ sao cho:

$$LCM(A_1, A_2, \dots, A_N) = K$$

Vì đáp án có thể rất lớn, hãy in ra theo modulo ~10^9 + 7~.

Input

• Dòng duy nhất chứa hai số nguyên dương ~N~ và ~K~ ~(1 \le N \le 10^9,\ 1 \le K \le 10^9)~.

Output

• Gồm một dòng duy nhất chứa một số nguyên là số lượng dãy thỏa mãn yêu cầu, lấy modulo ~10^9 + 7~.

Scoring

Example input 1

2 4

Example output 1

5

Nguồn ảnh: Văn Việt, FPT

Theo truyền thuyết "Bánh chưng, bánh giầy", hoàng tử Lang Liêu đã dâng lên Vua Hùng hai thứ bánh làm từ gạo nếp: bánh chưng hình vuông tượng trưng cho Đất và bánh giầy hình tròn tượng trưng cho Trời. Từ đó, mỗi dịp Tết, người Việt làm bánh để tưởng nhớ tổ tiên và trân trọng hạt gạo, nghề nông.

Ngày nay, nhiều gia đình vẫn giữ thói quen gói bánh và thức xuyên đêm canh nồi bánh chưng: thêm củi để giữ lửa, canh nước để bánh luôn được luộc đều, và quây quần kể chuyện cho đỡ buồn ngủ.

Để chia ca canh nồi "cho khoa học", cả nhà ghi lại nhật ký đêm canh nồi dưới dạng một chuỗi ký tự ~S~. Mỗi ký tự là một hành động đã được mã hóa (ví dụ: thêm củi, châm nước, kiểm tra lửa, trở bánh, ...). Từ nhật ký này, mọi người muốn tìm ra "mẫu công việc" lặp lại nhiều lần nhất có thể, vì độ dài của mẫu đó thể hiện mức độ "ổn định" và dễ lập lịch cho năm sau.

Mỗi nhật ký được biểu diễn bằng chuỗi ký tự ~S~ gồm ~N~ ký tự ~S_1, S_2, ..., S_N~.

Bạn được cung cấp ba số nguyên ~N, K, T~ với ý nghĩa:

• ~N~ là độ dài của chuỗi ~S~.
• ~K~ là số lần xuất hiện tối thiểu yêu cầu.
• ~T~ quy định cách tính số lần xuất hiện của các chuỗi con.

Một chuỗi con liên tiếp (substring) ~S[l..r]~ được coi là "hợp lệ" nếu nó xuất hiện ít nhất ~K~ lần trong chuỗi ~S~, với quy tắc phụ thuộc vào giá trị ~T~:

• Nếu ~T = 1~, các lần xuất hiện được phép chồng lấn nhau.
• Nếu ~T = 2~, các lần xuất hiện không được phép chồng lấn nhau, tức là hai lần xuất hiện bất kỳ không được chia sẻ ký tự chung.

Yêu cầu: hãy tìm độ dài lớn nhất của một chuỗi con thỏa mãn điều kiện trên.

Input

• Dòng đầu tiên chứa ba số nguyên ~N~, ~K~ và ~T~ ~(1 \leq N \leq 300\ 000~, ~1 \leq K \leq N~, ~1 \leq T \leq 2)~
• Dòng thứ hai chứa chuỗi ký tự ~S~ gồm ~N~ ký tự, mỗi ký tự là chữ cái latin viết thường.

Output

• In ra một số nguyên duy nhất là độ dài lớn nhất của một chuỗi con thỏa mãn yêu cầu đề bài.

Scoring

Example input 1

8 3 1
abababab

Example output 1

4

Explanation

Với ~T = 1~, các lần xuất hiện được phép chồng lấn.

Chuỗi con ~abab~ có độ dài ~4~ và xuất hiện tại các vị trí:

• từ ~1~ đến ~4~
• từ ~3~ đến ~6~
• từ ~5~ đến ~8~

Tổng cộng có ~3~ lần xuất hiện, thỏa mãn yêu cầu ~K = 3~. Không tồn tại chuỗi con nào có độ dài lớn hơn ~4~ xuất hiện ít nhất ~3~ lần, nên kết quả là ~4~.

Nguồn ảnh: govi.vn

Lì xì (mừng tuổi) là một phong tục quen thuộc mỗi dịp Tết: phong bao đỏ tượng trưng cho lời chúc may mắn, sức khỏe và bình an đầu năm. Để chuẩn bị "đúng bài", nhiều người thường lên danh sách đối tượng cần lì xì, dự trù tổng tiền, rồi chia nhỏ thành các mệnh giá phù hợp. Việc đổi tiền cũng cần cẩn thận để tránh rủi ro không đáng có.

Năm nay, bạn quyết định chuẩn bị lì xì theo một "lộ trình" rõ ràng gồm nhiều công đoạn (ví dụ: rút tiền, đổi mệnh giá, chuẩn bị phong bao, ghi lời chúc...). Mỗi công đoạn được gán một giá trị ~W_i~ (có thể hiểu là chi phí, thời gian, hoặc điểm công việc đã chuẩn hóa). Bạn sẽ sắp xếp thứ tự thực hiện các công đoạn theo một đồ thị có hướng, sao cho tồn tại một lộ trình từ bước ~1~ đến bước ~n~ với tổng giá trị đúng bằng ~S~.

Cho một đồ thị có hướng ban đầu chỉ có ~n~ đỉnh đánh số từ ~1~ đến ~n~. Bạn tạo các cung theo quy tắc sau:

• Với mỗi đỉnh ~i < n~, bạn chọn đúng một đỉnh ~j~ sao cho ~i < j \le n~, rồi tạo cung ~(i, j)~.

Cho trước các số ~W_1, W_2, \dots, W_n~.

Trọng số của một đường đi đi qua các đỉnh ~u_1, u_2, \dots, u_k~ (với ~u_1 = 1~, ~u_k = n~) được định nghĩa là:

$$W_{u_1} + W_{u_2} + \dots + W_{u_k}$$

Yêu cầu: hãy đếm số cách tạo cung sao cho tồn tại một đường đi từ ~1~ đến ~n~ có trọng số đúng bằng ~S~. Vì đáp án có thể rất lớn, hãy in ra theo modulo ~10^9 + 9~.

Input

• Dòng đầu tiên chứa số nguyên dương ~\tau~ là số bộ dữ liệu.

• Với mỗi bộ dữ liệu:

  • Dòng đầu chứa hai số nguyên ~n~ và ~S~ ~(1 \le n \le 4 \times 10^3,\ 0 \le S \le 5 \times 10^3)~.
  • Dòng tiếp theo chứa ~n~ số nguyên ~W_1, W_2, \dots, W_n~ ~(0 \le W_i \le 10^3)~.
• Dữ liệu đảm bảo ~\sum n + \sum S \le 5 \times 10^3~.

Output

• Với mỗi bộ dữ liệu, in ra số cách tạo cung thỏa mãn yêu cầu, modulo ~10^9 + 9~.

Scoring

Example input 1

1
4 4
1 2 2 1

Example output 1

3

Đêm giao thừa, thành phố tổ chức chương trình "bắn pháo hoa" theo một kịch bản được mã hóa thành chuỗi ký tự. Mỗi ký tự biểu diễn một hiệu ứng pháo (màu sắc, tầm cao, nhịp nổ...). Để tạo điểm nhấn, đạo diễn muốn chọn hai đoạn kịch bản không giao nhau, ghép lại theo đúng thứ tự, sao cho tạo thành một màn pháo đối xứng hoàn hảo giống như "phản chiếu" qua trục giữa.

Bạn được cho chuỗi ký tự ~S~ độ dài ~N~ được đánh số từ ~1~ đến ~N~. Nhiệm vụ của bạn là chọn hai đoạn con:

• ~S[l_1..r_1]~ và ~S[l_2..r_2]~
• thỏa ~1 \leq l_1 \leq r_1 < l_2 \leq r_2 \leq N~

Sau đó ghép lại tạo thành chuỗi mới ~T = S[l_1..r_1] + S[l_2..r_2]~ (các bạn lưu ý đọc kĩ đoạn này nhé).

Chuỗi ~T~ được gọi là "màn pháo đối xứng" nếu ~T~ là chuỗi đối xứng.

Yêu cầu: hãy tìm độ dài lớn nhất có thể của một chuỗi ~T~ như vậy. Nếu không thể tạo ra bất kỳ chuỗi ~T~ thỏa mãn nào, hãy in ra ~0~.

Input

• Dòng đầu tiên chứa số nguyên ~N~ ~(2 \leq N \leq 300\ 000)~ - độ dài của chuỗi.
• Dòng thứ hai chứa chuỗi ~S~ gồm ~N~ ký tự, mỗi ký tự là chữ cái latin viết thường.

Output

• In ra một số nguyên duy nhất là độ dài lớn nhất của chuỗi đối xứng ~T~ có thể tạo ra. Nếu không thể, in ra ~0~.

Scoring

Sample Input 1

7
abcbaba

Sample Output 1

5

Sample Input 2

5
abcde

Sample Output 2

0

Explanation

Một cách chọn tối ưu ở Sample 1 là:

• ~S[l_1..r_1] =~ abc.
• ~S[l_2..r_2] =~ ba.

Ghép lại được ~T =~ abcba, là chuỗi đối xứng có độ dài ~5~.