我住在一个充满路口和连接它们的双向道路的疯狂城市里。大多数日子里，其中一个路口会举行庆祝活动，这就是我称这座城市为“疯狂城市”的原因。

每天，我都要从家（路口 $s$）走到办公室（路口 $t$）。我不喜欢拥挤，但也不想浪费时间，所以我总是选择所有不经过庆祝活动所在路口的路径中最短的一条。如果不存在这样的路径，我就不去上班了（这真是个好借口，不是吗）！

为了详细分析这种“庆祝效应”，我需要 $n$ 对值 $(l_i, c_i)$，其中 $l_i$ 是从路口 $s$ 到路口 $t$ 且不经过路口 $i$ 的最短路径长度，$c_i$ 是此类最短路径（不经过路口 $i$）的数量。你能帮我吗？注意，如果庆祝活动在路口 $i$ 举行时我无法去上班，则定义 $l_i = c_i = 0$。这包括了即使在没有庆祝活动时，$s$ 和 $t$ 之间也没有路径的情况。

啊，等一下。请不要直接给我这些值——那会让我发疯的（数字太多了！）。我只需要找到这些值背后的一些有趣结论，但目前我还没想好到底想要什么。

在知道你应该计算什么之前，请证明你确实可以找到所有的 $(l_i, c_i)$ 对，方法是告诉我对于给定的 $x$，下式的值： $f(x) = (l_1 + c_1x + l_2x^2 + c_2x^3 + l_3x^4 + c_3x^5 + \dots + l_nx^{2n-2} + c_nx^{2n-1}) \pmod{19880830}$。

输入格式

最多有 20 组测试数据。每组数据以 5 个整数 $n, m, s, t, q$ 开头（$1 \le s, t, n \le 100,000$，$0 \le m \le 500,000$，$1 \le q \le 5$）。$n$ 是路口数量，$m$ 是道路数量，$q$ 是查询数量。$s$ 和 $t$ 是代表我家和办公室的不同整数。接下来的 $m$ 行，每行描述一条道路，包含三个整数：$u, v, w$（$1 \le u, v \le n$，$1 \le w \le 10,000$），表示连接路口 $u$ 和路口 $v$ 的双向道路，长度为 $w$。同一对路口之间可能有多条道路，但道路不能连接路口自身。下一行包含 $q$ 个整数 $x_i$（$1 \le x_i \le 10^9$）。最后一组测试数据后跟着五个零，这组数据不应被处理。

输出格式

对于每组测试数据，打印案例编号以及 $q$ 个整数 $f(x_1), f(x_2), \dots, f(x_q)$，相邻项之间用单个空格分隔，输出在一行上。每组测试数据的输出后打印一个空行。

样例

样例输入 1

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

样例输出 1

Case 1: 10 132400 
Case 2: 0

说明

在第一个样例中，$l_1=c_1=0, l_2=4, c_2=2, l_3=3, c_3=1, l_4=c_4=0$。在第二个样例中，所有值均为零。