Thành phố Hà Nội - thủ đô ngàn năm văn hiến, ngày nay là trung tâm kinh tế, văn hóa và chính trịlớn của cả nước. Thế nhưng, trước khi trở thành đô thị hiện đại và sầm uất bậc nhất Việt Nam, Hà Nội cũng từng là làng quê thanh bình với những người nông dân quanh năm chăm chỉ cày cấy trên những cánh đồng thẳng cánh có bay.

Thành phố Hà Nội có \(f\) ngôi làng được đánh số từ \(1\) đến \(f\). Các ngôi làng này được nối bởi những con đường hai chiều với độ dài khác nhau. Về mạng lưới giao thông trong thành phố, sử sách ghi rằng: Trong suốt chiều dài ngàn năm lịch sử, thành phố từng có \(o\) cụm dân cư, các cụm dân cư được đánh số từ \(1\) đến \(o\). Cụm dân cư thứ \(i\) gồm \(t_i\) ngôi làng \(u_{i, 1}, u_{i, 2}, ..., u_{i, t_i}\). Đây là những ngôi làng có quan hệ chặt chẽ về con người và kinh tế với nhu cầu đi lại, trao đổi và buôn bán cao. Để phục vụ nhu cầu giao thương của người dân, người ta lập ra một con đường hai chiều với độ dài \(h_i\) giữa mọi cặp ngôi làng trong cụm. Như thế, có tất cả \(\frac{t_i \cdot (t_i - 1)}{2}\) con đường được lập ra; và với mọi \(1 \leq x < y \leq t_i\), có một con đường độ dài \(h_i\) nối hai ngôi làng \(u_{i, x}\) và \(u_{i, y}\). Do biến động của lịch sử, các cụm dân cư bị ''khắc nhập, khắc xuất'' nhiều lần, vì thế một ngôi làng có thể thuộc vào nhiều hơn một cụm dân cư, nhưng những con đường đã lập ra thì vẫn còn tồn tại cho tới bây giờ. Khi chiến tranh kết thúc, chính quyền thành phố quyết định xây dựng thêm \(s\) con đường hai chiều. Các con đường được đánh số từ \(1\) đến \(s\), con đường thứ \(j\) kết nối ngôi làng \(a_j\) với ngôi làng \(n_j\) và có chiều dài \(s_j\).

Sử gia fosthuandz quyết định ghé thăm Hà Nội để nghiên cứu về mạng lưới giao thông của thành phố. Anh chọn ra \(z\) ngôi làng \(1, 2, ..., z\) để khảo sát. Với mỗi ngôi làng từ \(1\) đến \(z\), anh muốn biết độ dài đường đi ngắn nhất từ ngôi làng này tới tất cả \(f\) ngôi làng trong thành phố. Tuy nhiên, do mạng lưới giao thông tại Hà Nội quá rộng lớn, fosthuandz muốn các bạn viết chương trình tìm đường đi ngắn nhất. Các bạn hãy giúp sử gia nhé.

Để giảm kích thước của file dữ liệu đầu ra, các bạn cần in kết quả theo hướng dẫn sau:

• Với mọi cặp số nguyên \(i, j\) thỏa mãn \(1 \leq i \leq z\) và \(1 \leq j \leq f\), ta định nghĩa \(D(i, j)\) là độ dài đường đi ngắn nhất từ ngôi làng \(i\) tới ngôi làng \(j\). Nếu không tồn tại đường đi giữa hai ngôi làng này, ta coi \(D(i, j) = -1\).
• Với mọi số nguyên \(j\) thỏa mãn \(1 \leq j \leq f\), ta gọi \(S_j = \sum_{i = 1}^{z} D(i, j) \cdot i^i\).
• Các bạn cần in ra phần dư của các số \(S_1, S_2, \ldots, S_f\) khi chia cho \(998244353\).

Input

• Dòng đầu tiên chứa ba số nguyên \(f\), \(o\) và \(s\) \((0 \leq \frac{f}{2}, o, \frac{s}{3} \leq 10^5)\), lần lượt là số ngôi làng trong thành phố, số cụm dân cư và số con đường hai chiều được xây dựng thêm.

• Trong \(o\) dòng tiếp theo, dòng thứ \(i\) mô tả cụm dân cư thứ \(i\) theo khuôn dạng sau:

• Đầu tiên là số nguyên \(t_i\) \((1 \leq t_i \leq f)\).

• Tiếp theo là số nguyên \(h_i\) \((1 \leq h_i \leq 10^9)\).

• Cuối cùng là \(t_i\) số nguyên đôi một phân biệt \(u_{i, 1}, u_{i, 2}, \ldots, u_{i, t_i}\) \((1 \leq u_{i, j} \leq f)\).

• Dòng này mang ý nghĩa: Với mọi cặp chỉ số \((x, y)\) thỏa mãn \(1 \leq x < y \leq t_i\), có một con đường với độ dài \(h_i\) kết nối hai ngôi làng \(u_{i, x}\) và \(u_{i, y}\). Dữ liệu vào đảm bảo tổng số ngôi làng trong các cụm dân cư không quá \(5 \cdot 10^5\). Nói cách khác, \(t_1 + t_2 + \ldots + t_o \leq 5 \cdot 10^5\).

• Trong \(s\) dòng tiếp theo, dòng thứ \(j\) chứa ba số nguyên \(a_j\), \(n_j\) và \(d_j\) \((1 \leq a_j, n_j \leq f, 1 \leq d_j \leq 10^9)\) cho biết có một con đường với độ dài \(d_j\) kết nối hai ngôi làng \(a_j\) và \(n_j\).

• Dòng cuối cùng chứa số nguyên \(z\) \((1 \leq z \leq \min(f, 7))\) là số ngôi làng sử gia fosthuandz muốn khảo sát.

Output

• In ra một dòng duy nhât với \(f\) số nguyên không âm là phần dư của các giá trị \(S_1, S_2, \ldots, S_f\) khi chia cho \(998244353\).

Example

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

155 140 25 160 192 240 248