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. Explanation: Inthefirstsample,l1 =c1 =0,l2 =4,c2 =2,l3 =3,c3 =1,l4 =c4 =0. Inthesecondsample, everything is zero. Sample Input 45142 121 131 242 343 144
2/2 1 10 32131 1 2 12 232 1 00000 Sample Output Case 1: 10 132400 Case 2: 0