Farmer John と風変わりな踊る牛たちは新ミュージカル「欲望という名の街の牛」を練習中です。途中で $N$ $(1 \le N \le 1,000)$ 組、それぞれ 30 頭が他の牛の背に立って積み重なります（驚くべき牛です）。牧場にはこの牛の塔と、別の位置の $M$ $(1 \le M \le 1,000)$ 干草の山があります。配置例です。C は 30 頭の塔、H は干草の山です。

                8 .........
                7 ....CH.H.         C = stack of 30 cows
                6 .........
                5 .........         H = haystack
                4 ..C.HH...
                3 .........
                2 .....C.HH
                1 .........
                  123456789

指揮者 Farmer John の異なる音の四つの笛は、各塔の一番下の牛とその上の全頭を、北、南、東、西のいずれかへ一単位動かします。

干草の山のマスに入るたび、最上部の牛は一頭だけの塔でも山へ跳び、残りは同じマスへ移ります。最下部が干草の山に 30 回出会えば、別の山でも同じ山でも、全頭が山か山の上の牛に乗り塔はなくなります。各丈夫な山は無制限の牛を支えられます。

牧場越しに Farmer Don の搾乳施設を見て、FJ は巨大なミルクタンクの爆発と踊る牛へ迫るミルクの大波に恐怖します！山の上の牛は安全です。単純な踊りが救命技術となり、できるだけ多くを救わなければなりません。

波が来るまで笛を吹ける回数 $K$ $(1 \le K \le 30)$、$N$ 塔と $M$ 山の位置 $X_{i}$、$Y_{i}$ $(1 \le X_{i} \le 1,000; 1 \le Y_{i} \le 1,000)$ が与えられます。山には現在牛はいません。救える最大頭数と笛の列を求めてください。東 E、北 N、西 W、南 S を使い、最適列の辞書順最小を選びます。入力の初期位置で牛の塔と干草は重なりません。

牧場外を含め、どこへでも移動できます。

入力

• 1 行目：空白区切り整数 $N$、$M$、$K$。
• $2,\ldots,N+1$ 行目：第 $i+1$ 行は 30 頭の塔の $X$、$Y$ 座標を空白区切り整数 $X_{i}$、$Y_{i}$ で表します。
• $N+2,\ldots,N+M+1$ 行目：第 $i+N+1$ 行は山の $X$、$Y$ 座標を空白区切り整数 $X_{i}$、$Y_{i}$ で表します。

出力

• 1 行目：救える最大頭数の整数。
• 2 行目：頭数を最大にする辞書順最小の $K$ 文字の命令列。

入出力例

入力 1

3 6 3
3 4
6 2
5 7
8 2
9 2
6 4
5 4
6 7
8 7

出力 1

6
EEE

注記

東の笛を三回吹いた後、ミルクが牧場を覆います。各山が一頭ずつ救います。

問題作成者：Thomas Williamson、2004