Thu mua nông sản

Quốc gia Delta có nền nông nghiệp hàng đầu thế giới. Năm nay, nhờ ứng dụng công nghệ thông tin sâu rộng trong sản xuất nông nghiệp, nông dân quốc gia Delta đã được mùa lớn. Để chúc mừng thành công lớn của bà con cũng như đẩy mạnh việc xuất khẩu, chính phủ quyết định bố trí các xe thu mua nông sản từ khắp mọi nơi trên cả nước.

Trong quốc gia có $N$ ngôi làng được đánh số từ $1$ đến $N$. Mạng lưới giao thông tại đây gồm $N-1$ con đường hai chiều, mỗi con đường nối trực tiếp hai ngôi làng nào đó. Các con đường này bảo đảm sự liên thông toàn quốc. Nói cách khác, từ một ngôi làng bất kỳ có thể đi tới tất cả các ngôi làng còn lại thông qua một hoặc nhiều con đường. Người dân tại quốc gia Delta có khả năng sản xuất được $K$ loại nông sản khác nhau, được đánh số từ $1$ đến $K$. Năm nay, người dân tại ngôi làng thứ $i$ ($1\le i\le N$) sản xuất loại nông sản thứ $A_i$.

Chính phủ quốc gia Delta sẽ bố trí $\frac{N·(N-1)}{2}$ xe tải đi thu mua nông sản. Cụ thể, với mỗi cặp số nguyên $(u,v)$ sao cho $1\le u<v\le N$, có một xe tải xuất phát từ ngôi làng thứ $u$, đi qua một hoặc nhiều con đường rồi dừng lại ở ngôi làng thứ $v$. Biết rằng, xe tải luôn chọn đi theo tuyến đường qua ít con đường nhất có thể, và khi tới bất kỳ một ngôi làng nào (bao gồm cả hai ngôi làng thứ $u$ và thứ $v$), xe tải sẽ thu mua $1$ tấn nông sản được sản xuất tại ngôi làng đó. Nhờ mùa màng bội thu, tất cả các ngôi làng đều có đủ nông sản cho mọi xe đi qua thu mua.

Việc vận chuyển nông sản luôn phát sinh chi phí. Tùy theo đặc tính, chi phí vận chuyển từng loại nông sản có thể khác nhau. Theo tính toán của chính phủ, nếu trong toàn bộ hành trình, một xe tải thu mua được khối lượng nông sản các loại thứ $1,2,\dots ,K$ tương ứng là $W_1,W_2,\dots ,W_K$ tấn, chi phí vận chuyển của xe này là $C_1·W_1^2+C_2·W_2^2+\dots +C_K·W_K^2$, trong đó $C_1,C_2,\dots ,C_K$ tương ứng là hệ số chi phí vận chuyển của $K$ loại nông sản thứ $1,2,\dots ,K$. Chính phủ sẽ tài trợ toàn bộ chi phí vận chuyển, nên cần biết tổng chi phí của tất cả $\frac{N·(N-1)}{2}$ xe tải này.

Ngoài ra, với niềm tin rằng nền nông nghiệp còn phát triển mạnh trong nhiều năm về sau, chính phủ muốn dự trù chi phí vận chuyển nông sản cho những năm tiếp theo. Theo kế hoạch canh tác trong $Q$ năm tiếp theo, vào năm thứ $j$ ($1\le j\le Q$), ngôi làng thứ $T_j$ sẽ chuyển qua sản xuất loại nông sản thứ $B_j$, trong khi $N-1$ ngôi làng còn lại sẽ tiếp tục canh tác loại nông sản như năm thứ $j-1$ (năm nay được coi là năm thứ $0$). Với mỗi năm, chính phủ muốn biết tổng chi phí vận chuyển nông sản nếu tiếp tục bố trí các xe tải thu mua như phương án ở trên.

Yêu cầu: Hãy viết chương trình tính tổng chi phí vận chuyển nông sản của chính phủ trong năm nay và trong $Q$ năm tiếp theo, dựa trên kế hoạch thay đổi canh tác.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $N$, $K$ và $Q$ lần lượt là số ngôi làng của quốc gia Delta, số loại nông sản được sản xuất tại đây và số năm trong kế hoạch canh tác ($1\le K\le 20$, $1\le N,Q\le 2·{10}^5$).
• Dòng thứ hai chứa $N$ số nguyên $A_1,A_2,\dots ,A_N$ thể hiện loại nông sản chuyên được sản xuất tại các ngôi làng trong năm nay ($1\le A_i\le K$, $\forall i=1,2,\dots ,N$).
• Dòng thứ ba chứa $K$ số nguyên $C_1,C_2,\dots ,C_K$ là hệ số chi phí vận chuyển của các loại nông sản ($1\le C_i\le {10}^9$, $\forall i=1,2,\dots ,K$).
• Mỗi dòng trong số $N-1$ dòng tiếp theo chứa hai số nguyên $x$ và $y$ cho biết có một con đường hai chiều nối ngôi làng thứ $x$ và ngôi làng thứ $y$.
• Dòng thứ $j$ trong số $Q$ dòng cuối cùng chứa hai số nguyên $T_j$ và $B_j$ với ý nghĩa: vào năm thứ $j$ trong $Q$ năm tiếp theo, ngôi làng thứ $T_j$ sẽ chuyển sang sản xuất loại nông sản thứ $B_j$ ($1\le T_j\le N$; $1\le B_j\le K$).

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

Dữ liệu ra

• Dòng đầu chứa một số nguyên là phần dư của tổng chi phí vận chuyển nông sản trong năm nay trong phép chia cho $998244353$.
• Dòng thứ $j$ trong số $Q$ dòng còn lại chứa một số nguyên là phần dư của tổng chi phí vận chuyển nông sản trong năm thứ $j$ trong phép chia cho $998244353$.

Ràng buộc

• $1\le N,Q\le 2·{10}^5$; $1\le K\le 20$.
• $1\le A_i\le K$; $1\le C_i\le {10}^9$.
• Các con đường tạo thành một cây (liên thông, $N-1$ con đường).
• $1\le T_j\le N$; $1\le B_j\le K$.

Subtasks

• Subtask 1 ($7,5\%$ số điểm): $N\le 30$ và $Q\le 800$.
• Subtask 2 ($12,5\%$ số điểm): $N\le 100$ và $Q\le 800$.
• Subtask 3 ($10\%$ số điểm): $N\le 2000$ và $Q\le 800$.
• Subtask 4 ($15\%$ số điểm): $N\le 5000$ và $Q\le 8000$.
• Subtask 5 ($17,5\%$ số điểm): Luôn tồn tại một con đường nối ngôi làng thứ $i$ và ngôi làng thứ $\lfloor \frac{i}{2}\rfloor$, $\forall i=2,3,\dots ,N$ ($\lfloor \frac{i}{2}\rfloor$ là số nguyên lớn nhất không vượt quá $i/2$).
• Subtask 6 ($22,5\%$ số điểm): Luôn tồn tại một con đường nối ngôi làng thứ $i$ và ngôi làng thứ $i-1$, $\forall i=2,3,\dots ,N$.
• Subtask 7 ($15\%$ số điểm): Không có ràng buộc gì thêm.

Ví dụ