Trong một tòa tháp có ~N~ tầng, được đánh số từ ~1~ đến ~N~, có đúng một kỹ sư làm việc ở mỗi tầng. Buổi sáng, tất cả kỹ sư đều ở tầng hầm ~0~.

Có một bệ nâng tự động xuất phát từ tầng ~0~ và chỉ được phép dừng đúng một lần tại một tầng do các kỹ sư chọn trước. Sau khi bệ nâng dừng, mỗi kỹ sư có thể:

• đi bộ hoàn toàn từ tầng ~0~ đến tầng làm việc của mình;
• đi bằng bệ nâng đến tầng dừng, rồi đi bộ lên hoặc xuống đến tầng làm việc.

Thời gian di chuyển:

• đi bộ lên ~1~ tầng mất ~A~ giây;
• đi bộ xuống ~1~ tầng mất ~B~ giây;
• bệ nâng đi qua ~1~ tầng mất ~C~ giây.

Giả sử mỗi kỹ sư luôn chọn cách di chuyển nhanh nhất cho mình.

Yêu cầu

Hãy xác định thời gian nhỏ nhất để tất cả kỹ sư đến được tầng làm việc.

Dữ liệu

Gồm ~4~ dòng:

• Dòng ~1~ chứa số nguyên dương ~N~.
• Dòng ~2~ chứa số nguyên dương ~A~.
• Dòng ~3~ chứa số nguyên dương ~B~.
• Dòng ~4~ chứa số nguyên dương ~C~.

Kết quả

In ra một số nguyên duy nhất là thời gian nhỏ nhất để tất cả kỹ sư đến được tầng làm việc.

Ví dụ

Ví dụ 1

Input

6
20
10
5

Output

45

Giải thích

Ví dụ 1

Chọn bệ nâng dừng ở tầng ~5~.

• Kỹ sư tầng ~6~ đi bệ nâng rồi đi bộ lên ~1~ tầng, mất ~5 \cdot 5 + 1 \cdot 20 = 45~ giây.
• Kỹ sư tầng ~3~ đi bệ nâng rồi đi bộ xuống ~2~ tầng, mất ~5 \cdot 5 + 2 \cdot 10 = 45~ giây.
• Các kỹ sư còn lại có thể chọn cách đi nhanh hơn.

Thời gian hoàn thành của tất cả kỹ sư khi đó là ~45~ giây, và đây là giá trị nhỏ nhất.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le N \le 2 \times 10^9~
• ~1 \le B \le A \le 2 \times 10^9~
• ~1 \le C \le A~

Chấm điểm

• Subtask 1 (~20\%~): ~N < 1000~
• Các test còn lại không có ràng buộc bổ sung

Có hai dãy thiết bị song song, mỗi dãy gồm ~n~ vị trí.

• Dãy thứ nhất chứa các máy chủ, được đánh số từ trái sang phải là ~1, 2, \ldots, n~.
• Dãy thứ hai chứa các bộ chuyển mạch. Tại vị trí ~i~ có bộ chuyển mạch mang mã ~d_i~. Dãy ~d_1, d_2, \ldots, d_n~ là một hoán vị của các số từ ~1~ đến ~n~.

Một máy chủ có mã ~x~ có thể nối với bộ chuyển mạch ở vị trí ~i~ nếu và chỉ nếu ~|x - d_i| \le k~.

Mỗi kết nối dùng một sợi cáp. Mỗi máy chủ và mỗi bộ chuyển mạch chỉ được dùng trong nhiều nhất một kết nối. Các sợi cáp được coi là các đoạn thẳng nối giữa hai dãy và không được phép cắt nhau.

Yêu cầu

Hãy xác định số lượng kết nối lớn nhất có thể thiết lập.

Dữ liệu

• Dòng đầu chứa hai số nguyên ~n~ và ~k~.
• Dòng thứ hai chứa ~n~ số nguyên ~d_1, d_2, \ldots, d_n~.

Kết quả

In ra một số nguyên duy nhất là số lượng kết nối lớn nhất có thể thiết lập.

Ví dụ

Ví dụ 1

Input

3 1
3 2 1

Output

2

Giải thích

Ví dụ 1

Có thể nối:

• máy chủ ~1~ với bộ chuyển mạch ở vị trí ~2~ vì ~|1 - 2| = 1~;
• máy chủ ~2~ với bộ chuyển mạch ở vị trí ~3~ vì ~|2 - 1| = 1~.

Hai đoạn nối này không cắt nhau, nên thiết lập được ~2~ kết nối.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 10^5~
• ~0 \le k \le 10^9~
• ~d_1, d_2, \ldots, d_n~ là một hoán vị của các số từ ~1~ đến ~n~

Chấm điểm

• Subtask 1 (~25\%~): ~n \le 1000~, ~k = 0~
• Subtask 2 (~50\%~): ~n \le 5000~
• Subtask 3 (~25\%~): ~n \le 10^5~, ~k \le 3~

Cho một đồ thị vô hướng có ~N~ đỉnh và ~M~ cạnh, các đỉnh được đánh số từ ~1~ đến ~N~. Đỉnh ~1~ là trung tâm chính, đỉnh ~N~ là trung tâm dự phòng.

Cần chọn một số đỉnh làm điểm giám sát. Hệ thống được coi là hợp lệ nếu tồn tại:

• một đường đi từ ~1~ đến ~N~;
• một đường đi từ ~N~ đến ~1~;

sao cho:

• mọi đỉnh nằm trên hai đường đi này đều thuộc tập điểm giám sát;
• hai đường đi không dùng chung cạnh nào.

Yêu cầu

Hãy xác định số lượng đỉnh nhỏ nhất cần chọn làm điểm giám sát.

Dữ liệu

• Dòng đầu chứa hai số nguyên ~N~ và ~M~.
• ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~A~, ~B~, biểu diễn một cạnh nối hai đỉnh ~A~ và ~B~.

Kết quả

In ra một số nguyên duy nhất là số lượng đỉnh nhỏ nhất cần chọn.

Ví dụ

Ví dụ 1

Input

6 7
1 3
3 4
4 5
5 1
4 2
2 6
6 3

Output

6

Giải thích

Ví dụ 1

Có thể chọn hai đường đi không chung cạnh:

• ~1 \to 3 \to 6~
• ~1 \to 5 \to 4 \to 2 \to 6~

Hợp của hai đường đi này gồm các đỉnh ~1, 2, 3, 4, 5, 6~, nên cần chọn tối thiểu ~6~ đỉnh.

Ràng buộc và chấm điểm

Ràng buộc

• ~2 \le N \le 100~
• ~2 \le M \le 200~
• ~1 \le A, B \le N~
• ~A \ne B~
• Không có cạnh nối một đỉnh với chính nó
• Dữ liệu đảm bảo luôn tồn tại đáp án

Chấm điểm

• Subtask 1 (~20\%~): ~N \le 20~
• Các test còn lại không có ràng buộc bổ sung

Cho hai bảng ký tự ~A~ và ~B~, mỗi bảng có kích thước ~M \times N~. Mỗi ô chứa một chữ cái Latin thường.

Một hình chữ nhật con được xác định bởi một đoạn hàng liên tiếp và một đoạn cột liên tiếp. Hai hình chữ nhật con của ~A~ và ~B~ được gọi là giống nhau nếu chúng có cùng kích thước và trùng nhau ở mọi vị trí tương ứng.

Yêu cầu

Với mỗi bộ dữ liệu, hãy tìm diện tích lớn nhất của một hình chữ nhật con xuất hiện giống hệt nhau trong cả hai bảng ~A~ và ~B~.

Dữ liệu

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

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

  • Dòng đầu chứa hai số nguyên dương ~M~ và ~N~.
  • ~M~ dòng tiếp theo, mỗi dòng là một xâu độ dài ~N~, mô tả bảng ~A~.
  • ~M~ dòng tiếp theo, mỗi dòng là một xâu độ dài ~N~, mô tả bảng ~B~.

Kết quả

Gồm ~T~ dòng. Với mỗi bộ dữ liệu, in ra một số nguyên là diện tích lớn nhất của hình chữ nhật con chung.

Ví dụ

Ví dụ 1

Input

1
5 6
banana
orange
applep
grapes
cherry
pqpqpq
wxange
wxplep
wxapes
zzzzzz

Output

12

Giải thích

Ví dụ 1

Hình chữ nhật con chung lớn nhất có kích thước ~3 \times 4~ là:

ange
plep
apes

Trong cả hai bảng, hình chữ nhật này xuất hiện tại các hàng ~2 \to 4~ và các cột ~3 \to 6~. Do đó diện tích lớn nhất là ~3 \times 4 = 12~.

Ràng buộc và chấm điểm

Ràng buộc

• ~T \le 10~
• ~1 \le M, N \le 100~

Chấm điểm

• Subtask 1 (~25\%~): ~M, N \le 10~
• Subtask 2 (~25\%~): ~M = 1~, ~N \le 100~
• Subtask 3 (~25\%~): ~M, N \le 50~
• Subtask 4 (~25\%~): ~M, N \le 100~

Cho dãy ~A_1, A_2, \ldots, A_N~ gồm ~N~ số nguyên dương. Một đoạn liên tiếp được gọi là đề bài hay nếu mọi phần tử trong đoạn đó đều không phải số nguyên tố.

Lưu ý rằng ~1~ không phải là số nguyên tố.

Yêu cầu

Hãy đếm số lượng đoạn liên tiếp là đề bài hay.

Dữ liệu

• Dòng đầu chứa số nguyên dương ~N~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \ldots, A_N~.

Kết quả

In ra một số nguyên duy nhất là số lượng đoạn liên tiếp thỏa mãn.

Ví dụ

Ví dụ 1

Input

7
4 6 2 1 4 7 3

Output

6

Giải thích

Ví dụ 1

Các đoạn hợp lệ theo chỉ số là:

• ~[1,1]~
• ~[1,2]~
• ~[2,2]~
• ~[4,4]~
• ~[4,5]~
• ~[5,5]~

Phần tử ~A_4 = 1~ không phải số nguyên tố nên thuộc đoạn hợp lệ.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le N \le 10^5~
• ~1 \le A_i \le 10^6~

Chấm điểm

• Subtask 1 (~30\%~): ~N \le 100~
• Subtask 2 (~40\%~): ~N \le 5000~
• Subtask 3 (~30\%~): ~N \le 10^5~

Cho dãy ~a_1, a_2, \ldots, a_N~ gồm ~N~ số nguyên dương. Với ~1 \le x \le y \le N~, đặt

~F(x,y) = a_x \cdot a_{x+1} \cdot \ldots \cdot a_y~.

Có ~Q~ truy vấn. Mỗi truy vấn cho hai số nguyên ~L_i, R_i~. Với mỗi truy vấn, cần xác định xem ~F(L_i, R_i)~ có phải là số chính phương hay không.

Yêu cầu

Với mỗi truy vấn, in ra YES nếu tích các phần tử trong đoạn là số chính phương, ngược lại in ra NO.

Dữ liệu

• Dòng đầu chứa hai số nguyên dương ~N~ và ~Q~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, \ldots, a_N~.
• ~Q~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~L_i, R_i~.

Kết quả

Gồm ~Q~ dòng. Dòng thứ ~i~ in ra YES nếu ~F(L_i, R_i)~ là số chính phương, ngược lại in ra NO.

Ví dụ

Ví dụ 1

Input

5 3
2 4 8 16 32
1 3
2 4
1 5

Output

YES
NO
NO

Giải thích

Ví dụ 1

• Truy vấn ~[1,3]~: ~2 \cdot 4 \cdot 8 = 64 = 8^2~, nên in YES.
• Truy vấn ~[2,4]~: ~4 \cdot 8 \cdot 16 = 512~, không phải số chính phương.
• Truy vấn ~[1,5]~: ~2 \cdot 4 \cdot 8 \cdot 16 \cdot 32 = 32768~, không phải số chính phương.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le N, Q \le 70000~
• ~1 \le a_i \le 70000~
• ~1 \le L_i \le R_i \le N~

Chấm điểm

• Subtask 1 (~20\%~): ~1 \le N, Q \le 18~, ~1 \le a_i \le 10~
• Subtask 2 (~20\%~): ~1 \le N, Q \le 2000~, và mọi ~a_i~ có dạng ~2^k~ với ~k \ge 0~
• Subtask 3 (~20\%~): ~1 \le N, Q \le 70000~, và mọi ~a_i~ có dạng ~2^k~ với ~k \ge 0~
• Subtask 4 (~20\%~): ~1 \le N \le 70000~, ~Q \le 100~
• Subtask 5 (~20\%~): không có ràng buộc bổ sung

--

Có ~N~ máy tính được đặt trên một đường thẳng theo thứ tự từ trái sang phải và đánh số từ ~1~ đến ~N~. Khoảng cách giữa máy ~i~ và máy ~i+1~ là ~d_i~.

Có thể nối một dây cáp giữa hai máy bất kỳ. Chi phí của một dây nối giữa hai máy bằng khoảng cách vật lý giữa chúng trên bàn.

Cần chọn một số dây sao cho mỗi máy được nối với ít nhất một máy khác.

Yêu cầu

Hãy tìm tổng chiều dài cáp nhỏ nhất cần sử dụng.

Dữ liệu

• Dòng đầu chứa số nguyên dương ~N~.
• ~N-1~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên dương ~d_i~, là khoảng cách giữa máy ~i~ và máy ~i+1~.

Kết quả

In ra một số nguyên duy nhất là tổng chiều dài cáp nhỏ nhất cần sử dụng.

Ví dụ

Ví dụ 1

Input

6
2
2
3
2
2

Output

7

Giải thích

Ví dụ 1

Có thể nối:

• máy ~1~ với máy ~2~, chi phí ~2~;
• máy ~3~ với máy ~4~, chi phí ~3~;
• máy ~5~ với máy ~6~, chi phí ~2~.

Tổng chi phí là ~2 + 3 + 2 = 7~.

Ràng buộc và chấm điểm

Ràng buộc

• ~2 \le N \le 25000~
• ~1 \le d_i~
• ~d_1 + d_2 + \ldots + d_{N-1} \le 10^6~

Chấm điểm

• Subtask 1 (~30\%~): ~N \le 20~
• Subtask 2 (~30\%~): ~N \le 1000~
• Subtask 3 (~40\%~): ~N \le 25000~

Có ~N~ trạm điện và ~M~ đường dây điện hai chiều. Trạm ~1~ là trạm điện chính. Một trạm có điện nếu tồn tại đường đi từ trạm đó đến trạm ~1~.

Ban đầu mạng điện gồm đầy đủ ~M~ đường dây. Sau đó xảy ra ~Q~ sự kiện sửa chữa. Ở sự kiện thứ ~i~, đường dây nối giữa hai trạm ~C_i~ và ~D_i~ bị ngừng hoạt động vĩnh viễn.

Yêu cầu

Với mỗi trạm từ ~2~ đến ~N~, hãy xác định trạm đó bị mất điện sau sự kiện thứ mấy.

• Nếu trạm không có điện ngay từ ban đầu, in ra ~0~.
• Nếu sau tất cả các sự kiện trạm vẫn còn điện, in ra ~-1~.

Dữ liệu

• Dòng đầu chứa ba số nguyên ~N, M, Q~.
• ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~A_i, B_i~, biểu diễn một đường dây nối giữa hai trạm ~A_i~ và ~B_i~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~C_i, D_i~, biểu diễn một sự kiện ngừng hoạt động đường dây giữa hai trạm đó.

Dữ liệu đảm bảo:

• ~1 \le A_i < B_i \le N~
• ~1 \le C_i < D_i \le N~
• giữa hai trạm có nhiều nhất một đường dây
• mỗi đường dây bị sửa chữa nhiều nhất một lần

Kết quả

In ra ~N-1~ dòng.

• Dòng thứ ~i~ cho biết thời điểm mất điện của trạm ~i+1~.
• Nếu trạm không có điện từ đầu, in ~0~.
• Nếu trạm không mất điện sau mọi sự kiện, in ~-1~.

Ví dụ

Ví dụ 1

Input

6 7 5
1 2
1 6
2 4
2 3
3 5
4 5
5 6
2 3
2 4
1 2
4 5
1 6

Output

3
5
4
5
5

Giải thích

Ví dụ 1

• Sau ~3~ sự kiện đầu tiên, trạm ~2~ bị mất điện.
• Ở sự kiện ~4~, trạm ~4~ bị mất điện.
• Ở sự kiện ~5~, các trạm ~3~, ~5~, ~6~ bị mất điện.

Vì vậy các trạm ~2,3,4,5,6~ lần lượt mất điện ở các thời điểm ~3, 5, 4, 5, 5~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le N \le 10^5~
• ~1 \le M \le 2 \times 10^5~
• ~1 \le Q \le M~

Chấm điểm

• Subtask 1 (~10\%~): ~N \le 3000~, và ban đầu tất cả các trạm đều có điện
• Subtask 2 (~30\%~): ~N \le 3000~
• Subtask 3 (~60\%~): ~N \le 10^5~