WoodPro là một nhà máy nổi tiếng chuyên sản xuất các sản phẩm về gỗ. Do nhu cầu thị trường ngày càng cao, nhà máy quyết định nhập khẩu một dây chuyền thông minh sản xuất ra hàng loạt những thanh gỗ. Mỗi một lượt sản xuất, dây chuyền sẽ nhận vào ~N~ thanh gỗ dạng hình trụ có cùng kích thước đáy. Các thanh gỗ được đánh số từ 1 đến ~N~, thanh gỗ thứ ~i~ có độ dài ~A_i~ xăng-ti-mét. Thứ tự các thanh gỗ đưa vào dây chuyền là ~1, 2, \ldots , N~. Khi dây chuyền bắt đầu hoạt động, các thanh gỗ được xếp nối duôi nhau trên một băng chuyền, theo đúng thứ tự nhận vào. Băng chuyền này sẽ di chuyển các thanh gỗ đi theo một chiều qua hai công đoạn xử lý, trước tiên là công đoạn cắt và công đoạn dán, mà vẫn giữ nguyên thứ tự các thanh gỗ trên băng chuyền.

• Ở công đoạn cắt, có một lưỡi cắt được cố định phía trên băng chuyền. Mỗi khi có thanh gỗ di chuyển qua, hệ thống có thể điều khiển lưỡi cắt hạ xuống để cắt thanh gỗ thành hai thanh có tổng độ dài bằng độ dài của thanh gỗ trước khi cắt. Sau khi cắt, vị trí hai thanh gỗ trên băng chuyền vẫn được giữ nguyên. Chi phí cho mỗi lần cắt như vậy là ~C~.

• Ở công đoạn dán, có một máy dán được đặt cố định trên băng chuyền. Mỗi khi có hai thanh gỗ kề ngau di chuyển qua, hệ thống có thể điều khiển máy dán hạ xuống để dán hai thanh gỗ này thành một thanh gỗ có đõ dài bằng tổng độ dài hai thanh gỗ trước khi dán. Sau khi dán, vị trí của thanh gỗ trên băng chuyền vẫn được giử nguyên. Chi phí cho mỗi lần dán như vậy là ~D~.

Tuấn là một lập trình viên của nhà máy đảm nhận nhiệm vụ lập trình cho hệ thống đối với yêu cầu của mỗi đơn hàng. Do mới nhận được một đơn hàng yêu cầu các thanh gỗ thành phẩm chỉ gồm loại độ dài ~L_1~ xăng-ti-mét hoặc loại độ dài ~L_2~ xăng-ti-mét, nhà máy giao cho Tuấn lập trình cho hệ thống để sản xuất ra các thanh gỗ thành phẩm như vậy từ ~N~ thanh gỗ đầu vào mà không để thừa thanh gỗ nào có độ dài khác ~L_1~ và ~L_2~.

Yêu cầu: Biết rằng luôn tồn tại một phương án sản xuất ra các thanh gỗ thành phẩm độ dài ~L_1~ và ~L_2~ từ ~N~ thanh gỗ đầu vào mà không để thừa thanh gỗ nào có độ dài khác ~L_1~ và ~L_2~, hãy tính tổng chi phí ít nhất có thể dùng cho việc cắt và dán, để dây chuyền sản xuất có thể hoàn thành được đơn hàng.

Input

Vào từ file văn bản WPRO.INP:

• Dòng đầu tiên chứa năm số nguyên ~N,L_1,L_2,C,D~ lần lượt là số lượng thanh gỗ, hai loại độ dài các thanh gỗ thành phẩm đầu ra, chi phí cho một lần cắt và chi phí cho một lần dán ~(1 \leq N \leq 10^4; 1 \leq L_1,L_2 \leq 10^9; 1 \leq C, D \leq 10^5)~.

• Dòng thứ hai chứa số nguyên ~A_1, A_2, \ldots, A_N~ là độ dài của ~N~ thanh gỗ đầu vào ~(1 \leq A_i \leq 10^9, \forall i=1,2,\ldots,N)~.

Dữ liệu đảm bảo luôn có phương án giải quyết theo yêu cầu đề bài.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Ghi ra file văn bản WPRO.OUT một số nguyên là tổng chi phí dùng cho việc cắt và dán tìm được.

Scoring

Sample Input 1

3 2 5 10 4
6 5 6

Sample Output 1

38

Sample Input 2

3 1 1 2 3
3 4 5

Sample Output 2

18

Sample Input 3

3 12 13 2 3
3 4 5

Sample Output 3

6

Notes

Test 1:

• Một phương án tối ưu là dây chuyền thực hiện 3 lần cắt và thực hiện 2 lần dán như trong hình vẽ minh họa ở dưới.

• Tổng chi phí là ~10+10+10+4+4=38~.

Test 2: Phương án tối ưu là dây chuyền thực hiện 9 lần cắt.

Test 3: Phương án tối ưu là dây chuyền thực hiện 2 lần dán.

Một mạng truyền tin có ~N~ máy tính, các máy tính được đánh số từ ~1~ đến ~N~. Có ~N - 1~ dây cáp, được đánh số từ ~1~ đến ~N - 1~. Dây cáp thứ ~i~ nối máy tính ~u_i~ với máy tính ~v_i~ và có giới hạn truyền tải ~w_i~. Các dây cáp bảo đảm từ một máy tính bất kì có thể truyền tin đến tất cả các máy tính còn lại theo dây cáp trực tiếp giữa chúng hoặc thông qua đường truyền tin đi qua một số máy tính và dây cáp nào đó. Khi hai máy tính truyền tin cho nhau, chúng sẽ luôn sử dụng đường truyền tin sao cho không sử dụng dây cáp nào quá một lần. Độ lớn của gói tin truyền đi phải không lớn hơn giới hạn truyền tải của mọi dây cáp mà nó sử dụng. Chi phí để truyền một gói tin giữa hai máy tính bằng kích thước của gói tin nhân với bình phương số lượng dây cáp trên đường truyền tin.

Người ta muốn chọn ra một máy tính ~r~ để làm máy chủ. Khi đó, máy tính ~r~ sẽ truyền tin đến tất cả các máy tính khác. Vì phải dự trù cho mọi trường hợp, ta cần phải xét chi phí truyền tin tối đa. Chi phí truyền tin tối đa giữa máy tính ~r~ và máy tính ~x~ là ~C_{min}(r, x) \times (D(r, x))^2~ với ~C_{min}(r, x)~ là giới hạn truyền tải nhỏ nhất trong số các giới hạn truyền tải của các dây cáp trên đường truyền tin giữa máy tính ~r~ và máy tính ~x~, ~D(r, x)~ là số dây cáp trên đường truyền tin giữa máy tính ~r~ và máy tính ~x~. Chi phí vận hành mạng là tổng của chi phí truyền tin tối đa giữa máy tính ~r~ và tất cả các máy tính khác.

~\textbf{Yêu cầu}~: Với mỗi ~r = 1, 2, \ldots, N~, hãy tính chi phí vận hành mạng nếu chọn máy tính ~r~ làm máy chủ.

Input

Vào từ file văn bản NETW.INP:

• Dòng đầu chứa một số nguyên ~N~ là số lượng máy tính ~(1 \leq N \leq 10^5)~.

• Dòng thứ ~i~ trong số ~N - 1~ dòng tiếp theo chứa ba số nguyên ~u_i, v_i~ và ~w_i~ cho biết có một dây cáp nối máy tính ~u_i~ với máy tính ~v_i~ và có giới hạn truyền tải là ~w_i~ ~(1 \leq u_i, v_i \leq N; 1 \leq w_i \leq 10^9)~.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Ghi ra file văn bản NETW.OUT:

• Gòm ~N~ dòng, trong đó dòng thứ ~r~ chứa một số nguyên là phần dử của chi phí vận hành mạng nếu chọn máy tính ~r~ làm máy chủ trong phép chia cho ~998244353~.

Scoring

Sample Input 1

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

Sample Output 1

44
26
85
35
43
36
73

Cô Tuyết chuẩn bị một bài tập đặc biệt dành cho các bạn trong đội tuyển học sinh giỏi vào giáng sinh năm nay. Đó là môt bài tập về thứ tự từ điển với đề bài như sau.

Cho một dãy số khác rỗng ~C = [C_1, C_2, \ldots, C_M]~ thỏa mãn ~C_i \ne C_{i-1}, \forall i = 2, 3, \ldots, M~. Ta gọi một cách phân đoạn dãy là một cách chia dãy thành các đoạn con chứa các phần tử liên tiếp, mà mỗi phần tử đều thuộc đúng một đoạn con. Một cách phân đoạn dãy được coi là hợp lệ nếu mỗi đoạn con chỉ chứa các phần tử đôi một phân biệt.

Ví dụ, với ~M = 10~ và dãy ~C = [1,2,4,3,1,2,8,6,8]~, thì một cách phân đoạn dãy hợp lệ là chia dãy ~C~ thành ~4~ đoạn con lần lượt là ~[1,2,4,3],[2,1],[2,8],[6,8]~.

Một cách phân đoạn hợp lệ khác là chia dãy ~C~ thành ~5~ đoạn con lần lượt là ~[1,2,4],[3,2,1],[2,8],[6],[8]~.

Cả hai cách phân đoạn trên đều thỏa mãn mọi đoạn con chỉ chứa các phần tử đôi một phân biệt. Mặt khác, nếu ta chia dãy ~C~ thành ~4~ đoạn con lần lượt là ~[1,2,4,3],[2,1],[2],[8,6,8]~ thì sẽ không hợp lệ bởi có hai phần tử cùng bằng ~8~ trong đoạn con cuối cùng. Tương tự, nếu ta chia dãy ~C~ thành 5 đoạn con lần lượt là ~[1],[2,4,3,2,1,2],[8],[6],[8]~ thì cũng không hợp lệ bởi có ba phần tử cùng bằng ~2~ trong đoạn con thứ hai.

Mỗi dãy có thể có nhiều cách phân đoạn dãy hợp lệ. Mỗi cách phân đoạn dãy được mã hóa bằng một dãy mã hóa phân đoạn ~A = [A_1, A_2, \ldots, A_K]~, với ~K~ là số lượng đoạn con, và ~A_i~ là số lượng phần tử của đoạn con thứ ~i~. Chẳng hạn, với ~M=10~ và dãy ~C = [1,2,4,3,2,1,2,8,6,8]~, thì cách phân đoạn dãy trong hình đầu tiên sẽ được mã hóa bằng dãy ~A = [4,2,2,2]~.

Tương tự, cách phân đoạn dãy trong hình thứ hai sẽ được mã hóa thành dãy ~A = [3,3,2,1,1]~

Cô Tuyết viết lên bảng một dãy số khác rỗng ~C = [C_1, C_2, \ldots, C_M]~ thỏa mãn ~C_i \ne C_i-1, \forall i = 2,3,\ldots,M~, rồi lại viết lên bảng thêm ~2~ số nguyên dương ~X~ và ~Y~. Sau đó cô gọi một bạn lên bảng để trả lời câu hỏi sau:

"Khi liệt kê tất cả các dãy mã hóa phân đoạn của dãy ~C~ rồi sắp xếp chúng theo thứ tự từ điển ngược thì dãy mã hóa phân đoạn thứ ~X~ và dãy mã hóa phân đoạn thứ ~Y~ có độ dài tiền tố chung dài nhất là bao nhiêu?"

Nhắc lại: Một dãy mã hóa phân đoạn ~U = [U_1, U_2, \ldots, U_K]~ gọi là đi trước dãy mã hóa phân đoạn ~V = [V_1, V_2, \ldots, V_H]~ theo thứ tự từ điển ngược nếu thỏa mãn một trong hai điều kiện sau:

• ~K > H~ và ~U_i = V_i, \ \forall i = 1,2,\ldots,H~;

• Tồn tại ~1 \le T \le min(K,H)~ sao cho ~U_i = V_i, \ \forall i = 1,2,\ldots,T - 1~ và ~U_T > V_T~.

Dãy số ~U = [U_1, U_2, \ldots, U_K]~ được gọi là tiền tố độ dài ~K~ của dãy ~V = [V_1, V_2, \ldots, V_H]~ khi và chỉ khi ~K\le H~ và ~U_i = V_i, \forall i = 1,2,\ldots, K~. Lưu ý, dãy rỗng (ký hiệu là ~[]~) là tiền tố độ dài ~0~ của mọi dãy số.

Tiền tố chung dài nhất của hai dãy số ~Z_1~ và ~Z_2~ là dãy số có độ dài lớn nhất vừa là tiền tố của dãy ~Z_1~ vừa là tiền tố của dãy ~Z_2~.

Nhận thấy rằng nếu chỉ đặt ra câu hỏi cho một cặp số ~(X,Y)~ thì bài toán chưa đủ khó, cô Tuyết quyết định thềm vào một vài tham số mới. cô gọi ~Q~ bạn lần lượt lên bảng, bạn thứ ~i~ sẽ nhận được ~4~ số ~L_i, R_i, X_i, Y_i~ và có nhiệm vụ trả lời câu hỏi sau:

"Khi liệt kê tất cả các dãy mã hóa phân đoạn của dãy ~C' = [C_{L_i}, C_{L_i + 1}, \ldots, C_{R_i}]~ rồi sắp xếp chúng theo thứ tự từ điển ngược thì dãy mã hóa phân đoạn thứ ~X_i~ và dãy mã hóa phân đoạn thứ ~Y_i~ có độ dài tiền tố chung dài nhất là bao nhiêu?"

Yêu cầu: Hãy giúp các bạn trả lời ~Q~ câu hỏi của cô Tuyết.

Input

Vào từ file văn bản NOEL.INP:

• Dòng đầu chứa hai số nguyên ~M~ và ~Q~ lần lượt là độ dài của dãy ~C~ và số lượng bạn được cô Tuyết gọi lên bảng ~(1 \le M,Q \le 2 \times 10^5)~

• Dòng thứ hai chứa ~M~ số nguyên ~C_1, C_2, \ldots, C_M~ ~(1 \le C_i \le M, \forall i = 1,2, \ldots, M~; ~C_i \ne C_{i-1}~, ~\forall i = 2,3,\ldots,M)~.

• Dòng thứ ~i~ trong số ~Q~ dòng tiếp theo biểu diễn một câu hỏi với bốn số nguyên ~L_i,R_i,X_i,Y_i~ ~(1 \le L_i \le R_i \le M; 1 \le X_i,Y_i \le 10^{17})~. Dữ liệu bảo đảm một số lượng dãy mã hóa phân đoạn của dãy ~C' = [C_{L_i}, C_{L_i + 1}, \ldots, C_{R_i}]~ không nhỏ hơn ~max(X_i,Y_i)~.

Các số trên dùng một dòng cách nhau bởi dấu cách.

Output

Ghi ra file văn bản NOEL.OUT:

• Gồm ~Q~ dòng, trong đó dòng thứ ~i~ chứa một số nguyên là độ dài tiền tố chung dài nhất của hai dãy mã hóa phân đoạn của dãy ~C' = [C_{L_i}, C_{L_i + 1}, \ldots, C_{R_i}]~, với dãy mã hóa thứ nhất có thứ tự từ điển ngược bằng ~X_i~ và dãy mã hóa thứ hai có thứ tự từ điển ngược bằng ~Y_i~.

Scoring

Ràng buộc

Sample Input 1

10 2
1 2 4 3 2 1 2 8 6 8
2 5 6 7
4 10 7 6

Sample Output 1

2
0

Notes

• Trong câu hỏi đầu tiên, dãy cần xét đến là ~C' = [2,4,3,2]~. Tất cả các dãy mã hóa phân đoạn sắp xếp theo thứ tự từ điển ngược lần lượt là ~[3,1]; [2,2]; [2,1,1]; [1,3]; [1,2,1]; [1,1,2]; [1,1,1,1]~. Hai dãy mã hóa phân đoạn có thứ tự từ điển ngược bằng ~6~ và bằng ~7~ tương ứng là ~Z_1 = [1,1,2]~ và ~Z_2 = [1,1,1,1]~. Độ dài tiền tố chung dài nhất của hai dãy ~Z_1~ và ~Z_2~ là ~2~.

• Trong câu hỏi thứ hai, dãy cần xét đến là ~C' = [3,2,1,2,8,6,8]~. Hai dãy mã hóa phân đoạn có thứ tự từ điển ngược bằng ~7~ và bằng ~6~ tương ứng là ~Z_1 = [2,4,1]~ và ~Z_2 = [3,1,1,1,1]~. Độ dài tiền tố chung dài nhất của hai dãy ~Z_1~ và ~Z_2~ là ~0~.