問題文

$N$ 頂点 $M$ 本の無向辺からなる単純連結無向グラフが与えられます。 頂点に $1$ から $N$ の番号が、辺には $1$ から $M$ の番号がついています。 それぞれの頂点には色が塗られており、頂点 $i$ は $s_i$ が B ならば青で、R ならば赤で塗られています。

辺 $i$ は頂点 $a_i$ と $b_i$ を双方向につなぐ辺です。

太郎君と次郎君がこのグラフを使ってゲームをすることにしました。

グラフ上のどこかの頂点に $1$ つの駒が置かれています。 太郎君と次郎君は以下の操作を交互に行います。太郎君が最初に操作を行います。

• 操作：駒が置かれている頂点に隣接する頂点を $1$ つ選び、選んだ頂点に駒を移動させる

操作を $K$ 回行ったのち、駒が置かれている頂点の色が青ならば太郎君の、そうでなければ次郎君の勝利です。

はじめに駒が置かれている位置は $N$ 通りありえます。 それぞれの場合について、$2$ 人が最適に行動したときの勝者がどちらかを判定してください。

制約

• $2 \\leq N \\leq 10^5$
• $1 \\leq M \\leq 10^5$
• $1 \\leq K \\leq 10^{18}$
• $|s| = N$
• $s_i$ は B あるいは R
• $1 \\leq a_i,b_i \\leq N$
• 与えられるグラフは単純かつ連結

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $K$ $s$ $a_1$ $b_1$ $:$ $a_M$ $b_M$

出力

答えを $N$ 行に出力せよ。 $i$ 行目でははじめに頂点 $i$ に駒が置かれていたときの勝者が太郎君ならば First、次郎君ならば Second を出力せよ。

入力例1

2 1 3
BR
1 2

出力例1

Second
First

• 駒は $1 \\rightarrow 2, 2 \\rightarrow 1$ のいずれかの移動を繰り返します。
• 駒が頂点 $1$ に置かれていたならば $3$ 回の操作後には頂点 $2$ に置かれているため次郎君が勝者となります。
• 駒が頂点 $2$ に置かれていたならば $3$ 回の操作後には頂点 $1$ に置かれているため太郎君が勝者となります。

入力例2

2 1 1000000000000000000
BR
1 2

出力例2

First
Second

入力例3

5 7 9
BRRBR
3 1
5 2
4 2
2 1
5 4
5 1
3 2

出力例3

Second
First
First
Second
First