Problem Description
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 (li, ci), where li is the length of the shortest path from crossing s to crossing t, not visiting crossing i, ci 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 li = ci = 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 (li, ci) by telling me the value of f(x) = (l1+c1x+l2x2+c2x3+l3x4+c3x5+…+lnx2n-2+cnx2n-1) mod 19880830, for some given x.
Input
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 xi (1 <= xi <= 109). The last test case is following by five zeros, which should not be processed.
Output
For each test case, print the case number and q integers f(x1), f(x2), …, f(xq) separated by a single space between consecutive items, on one line. Print a blank line after the output of each test case.
Sample Input
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
Sample Output
Case 1: 10 132400
Case 2: 0
