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\leq i \leq 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 \cdot (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 \leq u < v \leq 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 ~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, \ldots, K~ tương ứng là ~W_1, W_2, \ldots, W_K~ tấn, chi phí vận chuyển của xe này là ~C_1 \cdot W_1^2 + C_2 \cdot W_2^2 + \ldots + C_K \cdot W_K^2~, trong đó ~C_1, C_2, \ldots, 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, \ldots, 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 \cdot (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 \leq j \leq 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.

Input

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

• 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 \leq K \le 20~, ~1 \leq N, Q, \leq 2 \cdot 10^5~).

• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, \ldots, 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 \leq A_i \leq K~, ~\forall i = 1, 2, \ldots, N~).

• Dòng thứ ba chứa ~K~ số nguyên ~C_1, C_2, \ldots,C_k~ là hệ số chi phí vận chuyển của các loại nông sản (~1 \leq C_i \leq 10^9~, ~\forall i = 1, 2, \ldots 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 \leq T_j \leq N~; ~1 \leq B_j \leq K~).

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 FBUY.OUT:

• 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~.

Scoring

Sample Input 1

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

Sample Output 1

120
137
139

Notes

Trong năm nay, các ngôi làng thứ ~1, 2, 3, 4, 5~ lần lượt sản xuất các loại nông sản thứu ~1, 1, 1, 2, 3~. Có tất cả ~\frac{5 \cdot (5 - 1)}{2} = 10~ xe tải với các lộ trình vận chuyển và chi phí như sau:

Tổng chi phí vận chuyển của các xe là ~8 + 18 + 11 + 7 + 8 + 5 + 13 + 11 + 23 + 16 = 120~.

Theo kế hoạch canh tác các năm tiếp theo:

• Trong năm thứ ~1~, các ngôi làng thứ ~1, 2, 3, 4~ sẽ lần lượt sản xuất các loại nông sản thứ ~1, 3, 1, 2, 3~. Số lượng xe và lộ trình di chuyển của các xe vẫn giống như ở trên, nhưng tổng chi phí vận chuyển của các xe là: ~7 + 13 + 10 + 7 + 7 + 8 + 22 + 10 + 28 + 25 = 137~.

• Trong năm thứ ~2~, các ngôi làng thứ ~1, 2, 3, 4~ sẽ lần lượt sản xuất các loại nông sản thứ ~1, 3, 2, 2, 3~. Số lượng xe và lộ trình di chuyển của các xe vẫn giống như ở trên, nhưng tổng chi phí vận chuyển của các xe là: ~7 + 10 + 10 + 7 + 8 + 8 + 22 + 17 + 25 + 25 = 139~.