Bài tập

Cho một cây có \(n\) đỉnh. Các đỉnh được đánh số từ \(1\) đến \(n\) và gốc của cây là đỉnh \(1\). Một số đỉnh của cây đã được tô màu đen, một số khác thì chưa được tô màu. Ta cần tìm cách tô màu cho tất cả các đỉnh.

Thao tác tô màu được định nghĩa như sau: Chọn một đỉnh \(u\) và tô tất cả các đỉnh \(v\) thành màu đen nếu thỏa mãn các điều kiện sau:

• Đỉnh \(v\) nằm trong cây con gốc \(u\).
• Khoảng cách giữa hai đỉnh \(u\) và \(v\) chính xác là \(i\). (Khoảng cách được định nghĩa là số cạnh ngắn nhất để đi từ \(u\) đến \(v\).)

Chi phí để tô màu một đỉnh có khoảng cách \(i\) là \(c_i\). Trong một thao tác, nếu chọn đỉnh \(u\) mà có nhiều hơn một đỉnh \(v\) cùng cách \(u\) một khoảng cách \(i\) thì tất cả các đỉnh đó sẽ được tô màu cùng lúc với chi phí \(c_i\).

Yêu cầu: Hãy tìm cách tô màu sao cho tất cả các đỉnh đều trở thành màu đen với tổng chi phí nhỏ nhất.

Input

• Dòng đầu chứa số nguyên \(n\) (\(1 \leq n \leq 10^6\)).
• Dòng thứ hai gồm \(n\) số \(c_0, c_1, \dots, c_{n-1}\) (\(c_i \leq 10^9\)), với \(c_i\) là chi phí để tô màu ở khoảng cách \(i\).
• Dòng thứ ba gồm \(n\) số \(a_1, a_2, \dots, a_n\). Nếu \(a_i = 0\) thì đỉnh \(i\) chưa được tô màu, nếu \(a_i = 1\) thì đỉnh \(i\) đã được tô màu.
• \(n - 1\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(u, v\) mô tả một cạnh của cây.

Output

Một dòng duy nhất ghi số nguyên là tổng chi phí nhỏ nhất để tô tất cả các đỉnh thành màu đen.

Example

5
10 5 1 5 5
0 1 0 0 1
1 2
2 3
2 4
4 5

11

Scoring

• Có 20% số test với \(n \leq 20\).
• Có 30% số test với \(n \leq 200\).
• Có 30% số test với \(n \leq 2000\).
• 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.

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.

Cho một dãy số nguyên \(A\) gồm \(n\) phần tử.

Với mỗi đoạn con \(A[l..r]\) (\(1 \le l \le r \le n\)), ta định nghĩa:

• \(W(l,r,x)\) là số lần giá trị \(x\) xuất hiện trong đoạn \(A[l],A[l+1],\dots,A[r]\).

• Gọi \(B\) là dãy gồm các phần tử đoạn \(A[l..r]\), và sắp xếp \(B\) tăng dần được dãy \(C\).

  Tập trung vị của đoạn là:
  $
  S(l,r) = { C[\lfloor (k-1)/2 \rfloor],\; C[\lceil (k-1)/2 \rceil] },
  $
  trong đó \(k = r-l+1\).

Giá trị của đoạn \((l,r)\) được định nghĩa là:
$
\max_{x \in S(l,r)} W(l,r,x).
$

Lưu ý: tập \(S(l,r)\) sẽ chứa phần tử trung vị duy nhất nếu đoạn có số phần tử lẻ, và chứa hai phần tử trung vị nếu đoạn có số phần tử chẵn.

Yêu cầu: Tìm giá trị lớn nhất trong tất cả các đoạn \((l,r)\).

\InputFile

• Dòng đầu chứa số nguyên \(n\) (\(1 \le n \le 5 \times 10^5\)).
• Dòng tiếp theo chứa \(n\) số nguyên \(A_i\) (\(1 \le A_i \le n\)).

\OutputFile

In ra một số nguyên duy nhất --- giá trị lớn nhất có thể đạt được.

\Scoring

• \(11\) điểm: \(n \le 100\).
• \(17\) điểm: \(n \le 2 \times 10^3\).
• \(7\) điểm: tồn tại \(x\) sao cho dãy tăng đến \(x\) rồi giảm sau đó.
• \(12\) điểm: \(A_i \le 3\).
• \(13\) điểm: mỗi giá trị xuất hiện nhiều nhất 2 lần.
• \(22\) điểm: \(n \le 8 \times 10^4\).
• \(18\) điểm: không có ràng buộc thêm.

Example

7
1 2 3 1 2 1 3

3

9
1 1 2 3 4 3 2 1 1

2