题目描述

晋太元中，武陵人瓜瓜以榨鸡为乐

大致意思：晋太元年间，瓜瓜是武陵人，也是当地臭名昭著的鸡养殖场场主，每天都把压榨鸡作为自己的快乐。

在瓜瓜的养殖场里的鸡都具有以下特征：

• 一只鸡，每天早上会下一颗蛋，连续下三天，第三天早上下完蛋就会马上累死。
• 蛋在第二天早上马上就会被瓜瓜孵化出来， 孵化出来的鸡马上就会开始下蛋，也就是在早上下一颗蛋。

瓜瓜不仅压榨鸡下蛋，还压榨鸡运动。

有一张无向图，有 $n$ 个节点 $m$ 条边，节点从 $1$ 到 $n$ 编号。

定义在一个节点上走一步，相当于走到除当前节点外离当前节点最近的点，如果存在距离相同的点，则会选择编号最小的点， 如果没有相邻的点，则保持不动。

每天晚上，每个节点的上的所有鸡都会走 $x_i$ 步到达一个新的节点，蛋保持不动。

因为瓜瓜惨无人道的行为，瓜瓜在 $q$ 天后被动物保护协会举报了。动物保护协会的人想知道 $q$ 天结束后，每个节点上都有多少只鸡，多少颗蛋？

特别的，初始时，每个节点上都有一只鸡。

鸡和蛋一天的流程：

• 鸡在早上下蛋，晚上运动，假定运动瞬时完成，当天晚上十二点称为一天的结束时间。 蛋在第二天早上孵化，马上会在早上下蛋，也会跟着在当天晚上运动。
• 蛋：被下 $\to$ 第二天早上孵化 $\to$ 马上走鸡的流程
• 鸡：早上在原地下蛋 $\to$ 马上死亡或者等到晚上去运动 $\to$ 晚上十二点清算数量

输入格式

第一行三个正整数 $n$ ($n \leqslant 300$), $m$ ($m \leqslant \frac{n(n - 1)}{2}$)， $q$ ($q \leqslant 10^4$),分别代表节点的数量，无向图的边数，瓜瓜作恶的天数。

接下来 $m$ 行，每行三个整数 $u, v，w$($w \leqslant 10^6$)表示两个节点之间有一条长度为 $w$ 的无向边。

接下来 $q$ 行，每行一个正整数 $x_i$（$x_i \leqslant 10^9$）表示第 $i$ 天，所有节点上鸡运动的步数。

输入保证不存在自环和重边。

输出格式

第一行 $n$ 个整数，分别代表 $1$ 到 $n$ 节点上对应的鸡的数目

第二行 $n$ 个整数，分别代表 $1$ 到 $n$ 节点上对应的蛋的数目

每行的输出中间用空格隔开, 答案对$998244353$取模

样例

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

0 3 4 1
1 2 3 2

5 10 3
1 2 3
1 3 4
1 4 5
1 5 1
2 3 3
2 4 3
2 5 6
3 4 1
3 5 2
4 5 3
1
2
3

5 0 3 3 4
6 1 4 4 5

如：一只鸡在一号节点，一天结束后，一号节点有一颗蛋，$0$ 只鸡。$1$ 号节点开始，走 $x_i$ 步到达的地方有一只鸡