In A Crazy City

I live in a crazy city full of crossings and bidirectional roads connecting them. On most of the days, there will be a celebration in one of the crossings, that’s why I call this city crazy.

Everyday, I walk from my home (at crossing s) to my office (at crossing t). I don't like crowds, but I don't want to waste time either, so I always choose a shortest path among all possible paths that does not visit the crossing of the celebration. If no such path exists, I don’t go to work (it’s a good excuse, isn’t it)!

In order to analyze this “celebration effect” in detail, I need n pairs of values (l_i, c_i), where l_i is the length of the shortest path from crossing s to crossing t, not visiting crossing i, c_i is the number of such shortest paths (not visiting crossing i). Could you help me? Note that if I can’t go to work when celebration is held at crossing i, define l_i = c_i = 0. This includes the case when there is no path between s and t even if there’s no celebration at all.

Ah, wait a moment. Please don’t directly give me the values - that’ll drive me crazy (too many numbers!). All I need is finding some interesting conclusions behind the values, but currently I’ve no idea what exactly I want.

Before I know what you should calculate, please prove that you can indeed find all the pairs (l_i, c_i) by telling me the value of f(x) = (l₁+c₁x+l₂x²+c₂x³+l₃x⁴+c₃x⁵+…+l_nx^2n-2+c_nx^2n-1) mod 19880830, for some given x.

There will be at most 20 test cases. Each case begins with 5 integers n, m, s, t, q (1 <= s,t <= n <= 100,000, 0 <= m <= 500,000, 1 <= q <= 5). n is the number of crossings, m is the number of roads and q is the number of queries. s and t are different integers that represent my home and office, respectively. Each of the following m lines describes a road with three integers: u, v, w (1 <= u,v <= n, 1 <= w <= 10,000), indicating a bidirectional road connecting crossing u and crossing v, with length w. There may be multiple roads connecting the same pair of crossings, but a road cannot be connecting a crossing and itself. The next line contains q integers x_i (1 <= x_i <= 10⁹). The last test case is following by five zeros, which should not be processed.

For each test case, print the case number and q integers f(x₁), f(x₂), …, f(x_q) separated by a single space between consecutive items, on one line. Print a blank line after the output of each test case.

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

Case 1: 10 132400

Case 2: 0

Explanation

In the first sample, l1 = c1 = 0, l2 = 4, c2 = 2, l3 = 3, c3 = 1, l4 = c4 = 0. In the second sample, everything is zero.

2009 Asia Wuhan Regional Contest Hosted by Wuhan University