1071 - 雛ちゃん王国の改装

問題

雛ちゃん王国にはN個の都市とM本の道があります。
i本目の道は町A_iとB_iを結んでおり、長さはC_iです。
ある都市A,Bの距離とは、A,B間の最短経路長と定義します。
各都市には、雛ちゃんを象徴する"厄"のローマ字を取って'Y','D','K'のいずれかの文字が書かれています。
i番目の都市の文字はS_iです。

ある日、Miareさんは、'D'は"厄"のローマ字に含まれていないことに気が付きました。
そこで、YTAくんに'D'が書かれている都市を破壊するように頼みました。
YTAくんは以下のように破壊します。

• 破壊力X(Xは正の整数)の爆弾を用意し、'D'が書かれたすべての街に設置する。
• 爆弾に火をつける。
• 爆弾は爆発し、爆発した地点から距離がX以下で到達できるすべての都市が破壊される。

国王である雛ちゃんは、消滅した都市をすべて復旧する必要があります。
復旧にかかるコストは、'Y'が書かれた都市はY円、'D'が書かれた都市はD円、'K'と書かれた都市はK円です。
雛ちゃんは爆発に使われるであろう破壊力Xの値はQ種類であると予想しました。
そこで、各破壊力X_iについてその破壊力の爆弾が爆発した際、復旧にかかるお金がいくらであるかを求めてください。

入力

入力は以下のように与えらる。

N M Q
Y D K
S1S2...Sn
A1 B1 C1
A2 B2 C2
.
.
.
AM BM CM
X1
X2
.
.
.
XQ

出力

各破壊力X_iについて、その爆弾を爆発させた際の復旧にかかる金額を改行区切りで出力せよ。

制約

1 ≦ N ≦ 10⁵
N-1 ≦ M ≦ min(2*10⁵,N*(N-1)/2)
1 ≦ Y,D,K ≦10⁵
1 ≦ A, B ≦ N
1 ≦ C ≦ 1000
1 ≦ Q ≦ 10⁵
1 ≦ X ≦ 10⁹
与えられる都市は連結である。
二重辺や自己参照辺は存在しない。
'D'が書かれた都市は一つ以上存在する。

入力例

入力1

3 2 3
1 2 3
YDK
1 2 10
2 3 15
3
21
12

出力1

2
6
3

入力2

7 8 5
17 27 19
DYKKYDK
1 2 1
2 3 3
3 4 12
3 5 2
5 6 5
6 7 2
3 7 3
4 7 3
3
5
1
4
8

出力2

90
145
71
109
145