Bài tập

Tuấn có một bộ bài gồm \(n\) quân bài được trải ra thành một dãy từ trái sang phải, trên mỗi quân bài ghi một số nguyên là giá trị của quân bài đó. Giá trị của \(n\) quân bài lần lượt theo dãy trải ra là \(A_1, A_2, \ldots, A_n\). Tuấn định nghĩa các khái niệm sau:

• Đoạn con: Một chuỗi các quân bài liên tiếp nhau trong dãy \(n\) quân bài ban đầu.
• Trọng số của một đoạn con: Là tổng các giá trị của các quân bài trong đoạn đó.
• Độ cân bằng của bộ bài: Là trọng số lớn nhất của bất kỳ đoạn con nào trong dãy \(n\) quân bài. Lưu ý, dãy con rỗng không được tính hợp lệ.

Tuấn mời Tú đến nhà chơi bài và yêu cầu Tú tính độ cân bằng của bộ bài theo định nghĩa trên. Sau khi Tú tính xong, Tuấn tiếp tục thách đố Tú bằng cách yêu cầu chỉnh sửa giá trị một số quân bài để đạt được độ cân bằng cao nhất với các nguyên tắc chỉnh sửa như sau:

• Ban đầu, Tuấn cung cấp thêm một dãy \(n\) số nguyên \(B_1, B_2, \ldots, B_n\).
• Tú có tối đa \(k\) lượt chỉnh sửa. Trong mỗi lượt chỉnh sửa, Tú được phép chọn một đoạn con từ vị trí \(\ell\) đến vị trí \(r\) \((1 \leq \ell \leq r \leq n)\) và thực hiện phép gán:
  \(A_i = A_i \cdot B_i\) với \(i\) thuộc \([l,r]\).

Yêu cầu:
Hãy tính và đưa ra độ cân bằng lớn nhất có thể đạt được sau tối đa \(k\) lượt chỉnh sửa.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) \((1 \leq n \le 10^5, \; 0 \le k \leq 10)\), lần lượt là số lượng quân bài và số lượt chỉnh sửa tối đa.
• Dòng thứ hai chứa \(n\) số nguyên \(A_1, A_2, \ldots, A_n\) \((-10^6 \leq A_i \leq 10^6)\), biểu diễn giá trị ban đầu của các quân bài.
• Dòng thứ ba chứa \(n\) số nguyên \(B_1, B_2, \ldots, B_n\) \((-10 \leq B_i \leq 10)\), biểu diễn hệ số nhân cho mỗi quân bài.

Output

In ra một số nguyên duy nhất, là độ cân bằng lớn nhất có thể đạt được sau tối đa \(k\) lượt chỉnh sửa.

Example

5 1
-3 4 -5 2 -2
1 -2 -1 2 1

13

3 0
-4 -10 -8
2 2 -1

-4

Scoring

• \(15\%\) số test ứng với \(k = 0\) (không có lượt chỉnh sửa nào).
• \(15\%\) số test ứng với \(k = 1\) và \(n \leq 5000\).
• \(20\%\) số test khác ứng với \(k = 1\).
• \(25\%\) số test khác ứng với \(k = 2\).
• \(25\%\) số test còn lại không có ràng buộc gì thêm.

Trong một lớp có \(n\) bạn và \(n - 1\) cặp bạn trực tiếp, giữa hai bạn bất kỳ luôn tồn tại một mối quan hệ gián tiếp qua các cặp bạn trung gian này.

Qua một bài kiểm tra, cô giáo nhận thấy bạn thứ \(i\) đã làm được \(a_i\) bài của bài kiểm tra. Bằng một phép thần kỳ nào đó, không có hai bạn nào làm được cùng số lượng bài và mỗi bạn (trừ bạn chỉ làm được 1 bài) đều có ít nhất một người bạn trực tiếp làm được ít bài hơn.

Cô giáo muốn chấm điểm cho các bạn dựa trên thang điểm nguyên từ \(1 \rightarrow k\) sao cho không có hai bạn nào có cùng điểm. Sẽ rất bất công nếu như trong một cặp bạn trực tiếp, bạn này làm ít bài hơn nhưng lại nhận được điểm cao hơn.

Yêu cầu: Hãy tìm số cách chấm điểm hợp lý giúp cô giáo. Hay nói cách khác, gọi \(b_i\) là điểm của bạn thứ \(i\), cô giáo muốn tìm số cách chấm điểm sao cho với mọi cặp bạn trực tiếp gồm bạn \(i\) và bạn \(j\), nếu \(a_i > a_j\) thì \(b_i > b_j\) và ngược lại.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) (\(1 \leq n \leq 10^5\), \(1 \leq k \leq 10^9\)) lần lượt là số bạn và thang điểm của cô giáo.
• Mỗi dòng trong số \(n - 1\) dòng tiếp theo chứa hai số nguyên \(i\) và \(j\) (\(1 \leq i, j \leq n, i \ne j\)) thể hiện một cặp bạn trực tiếp.
• Dòng cuối cùng chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \leq a_i \leq n\), \(a_i \ne a_j\) \(\forall\) \(i \ne j\)) là số bài làm được mỗi bạn.

Output

• In ra một số nguyên duy nhất là số cách chấm điểm hợp lệ modulo \(10^9 + 7\).

Example

1 4
1

4

3 4
1 2
1 3
1 2 3

8

5 5
1 2
2 3
3 4
4 5
1 2 3 4 5

1

Scoring

• Subtask 1 (20% số điểm): \(k \leq 10\).
• Subtask 2 (20% số điểm): \(k \leq 10^2\).
• Subtask 3 (20% số điểm): \(k \leq 10^3\).
• Subtask 4 (20% số điểm): \(k = n\).
• Subtask 5 (20% số điểm): Không có ràng buộc gì thêm.

Trong một chuyến phiêu lưu tới thành phố hiện đại Lumina, cô gái Lan Anh đang đứng trước một dãy các toà nhà chọc trời rực rỡ ánh đèn. Cô quyết định chụp một bức ảnh thật đẹp để ghi lại khoảnh khắc này.

Dãy các toà nhà này có thể được mô tả bởi một dãy số gồm \(n\) toà nhà với chiều cao lần lượt là \(h_1, h_2, \dots, h_n\). Lan Anh sẽ chọn một đoạn liên tiếp của dãy toà nhà này để chụp ảnh. Tuy nhiên, để bức ảnh trở nên đáng giá, đoạn được chọn phải có ít nhất \(k\) toà nhà.

Lan Anh có một tiêu chí rất đặc biệt để đánh giá vẻ đẹp của một bức ảnh: cô thích những toà nhà cao, và còn thích hơn nếu chiều cao của các toà nhà có ước chung lớn! Cụ thể, nếu cô chọn một đoạn từ \(h_l\) đến \(h_r\), gọi \(g\) là ước số chung lớn nhất (GCD) của các chiều cao trong đoạn đó, thì vẻ đẹp của bức ảnh được tính bằng:

Bạn hãy giúp Lan Anh tính ra giá trị vẻ đẹp lớn nhất mà cô ấy có thể đạt được với một bức ảnh chụp ít nhất \(k\) toà nhà liên tiếp.

Input

\begin itemize

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) (\(1 \le n, k \le 10^6\)).

• Dòng thứ hai chứa \(n\) số nguyên \(h_1, h_2, \dots, h_n\) (\(1 \le h_i \le 10^6\)).
  \end itemize

Output

In ra một số nguyên --- vẻ đẹp lớn nhất có thể đạt được.

Example

6 2
2 1 4 4 4 2

48

4 1
7 3 9 4

81

Scoring

• Subtask 1 (11 điểm): \(n, k \le 100\)
• Subtask 2 (28 điểm): \(n, k \le 5000\)
• Subtask 3 (18 điểm): \(h_i \le 100\)
• Subtask 4 (17 điểm): \(n, k \le 5 \cdot 10^4\)
• Subtask 5 (26 điểm): Không có ràng buộc thêm

Khu vườn của kiến trúc sư Minh được quy hoạch trên một mặt phẳng dạng lưới có kích thước \(n \times m\). Các ô trên lưới có thể trống (kí hiệu '\(.\)') hoặc đã có một bức tượng đặt sẵn (kí hiệu 'B').

Minh muốn trang trí khu vườn bằng cách xây dựng một hàng rào dọc và một hàng rào ngang để chia khu vườn thành bốn phần. Hàng rào ngang sẽ chạy qua giữa hai hàng, và hàng rào dọc sẽ chạy qua giữa hai cột. Sau khi chia, Minh đếm số lượng bức tượng trong mỗi phần:
\begincenter
\begintabular|l|c| \hline
a & b
\hline
c & d
\hline
\endtabular
\endcenter

với \(a, b, c, d\) lần lượt là số bức tượng ở phần trên-trái, trên-phải, dưới-trái và dưới-phải.

Minh không thể nhớ được cách anh ấy đã đặt hàng rào, nhưng anh ấy có một số câu hỏi liên quan đến số bức tượng ở mỗi phần.

Yêu cầu: Cho trước kích thước khu vườn và vị trí các bức tượng. Với mỗi câu hỏi của Minh, hãy xác định xem có tồn tại một cách đặt hàng rào thỏa mãn số lượng bức tượng ở mỗi phần hay không.

Input

• Dòng đầu tiên chứa ba số nguyên \(n, m, q\) (\(1 < n, m \le 1000, 1 \le q \le 10^5\)) lần lượt là số hàng, số cột và số lượng câu hỏi.
• \(n\) dòng tiếp theo, mỗi dòng chứa một chuỗi \(m\) kí tự mô tả trạng thái của mỗi ô đất: '\(.\)' là ô trống, 'B' là ô có bức tượng.

• \(q\) câu hỏi tiếp theo, mỗi câu hỏi trên hai dòng:

• Dòng đầu tiên chứa 2 số nguyên \(a, b\).

• Dòng thứ hai chứa 2 số nguyên \(c, d\).

  với \(a, b, c, d\) là số lượng bức tượng ở 4 phần tương ứng. Dữ liệu đảm bảo tổng số bức tượng trong câu hỏi không vượt quá tổng số bức tượng trên toàn khu vườn.

Output

• Với mỗi câu hỏi, nếu tồn tại cách chia thỏa mãn thì in ra YES. Ngược lại, in ra NO.

Example

3 4 3
..B.
.BB.
B..B
1 2
1 1
2 1
0 1
3 1
0 1

YES
NO
NO

Scoring

• Subtask 1 (30% số điểm): \(n, m \le 20, q \le 100\).
• Subtask 2 (30% số điểm): \(n \le 20, m \le 100, q \le 10000\).
• Subtask 3 (40% số điểm): Không có ràng buộc gì thêm.