Você conhece a Just Odd Inventions Co., Ltd.? O negócio dessa empresa é fazer “apenas invenções estranhas”. Aqui, vamos chamá-la simplesmente de JOI Company.

A JOI Company desenvolveu um novo vírus, o “JOI Virus”. A JOI Company quer realizar um experimento infectando os habitantes da IOI Island com o JOI Virus.

A IOI Island tem formato retangular. Há $R-1$ estradas paralelas de leste a oeste e $C-1$ estradas paralelas de norte a sul, que dividem a ilha em $RC$ setores. Em cada setor mora exatamente 1 habitante. Chamamos de “habitante $(i,j)$” a pessoa que mora no setor que é o $i$-ésimo a partir do norte e o $j$-ésimo a partir do oeste ($1 \le i \le R$, $1 \le j \le C$).

Na IOI Island, cada dia tem $M$ períodos. Chamamos o $k$-ésimo período de “período $k$”. O vento está sempre soprando de alguma direção: norte, sul, leste ou oeste. A direção pode mudar conforme o período. Em um mesmo período, o vento sempre sopra da mesma direção, independentemente do dia.

Cada habitante tem uma característica chamada “resistência”. A resistência do habitante $(i,j)$ ($1 \le i \le R$, $1 \le j \le C$) é representada por um inteiro não negativo $U_{i,j}$.

• Se $U_{i,j}=0$, o habitante $(i,j)$ tem alta resistência e não é infectado pelo JOI Virus.

• Se $U_{i,j}$ é um inteiro positivo, o habitante $(i,j)$ pode ser infectado pelo JOI Virus. Se a condição abaixo se mantiver por $U_{i,j}$ períodos consecutivos, ele estará infectado a partir do período seguinte:

  • O habitante do setor adjacente na direção de onde o vento está vindo já está infectado pelo JOI Virus.

  Observe que o último período de um dia e o primeiro período do dia seguinte são consecutivos.

Para os fins do experimento, queremos infectar pelo menos 1 habitante, mas não queremos infectar habitantes demais. No início, escolhemos 1 habitante como a primeira pessoa infectada e o infectamos com o JOI Virus. Não podemos escolher como primeira pessoa infectada um habitante cuja resistência seja $0$.

Dadas a direção de onde o vento vem em cada período e a resistência de cada habitante, escreva um programa que calcule o menor número de habitantes infectados após $10^{100}$ dias e a quantidade de habitantes cuja escolha como primeira pessoa infectada atinge esse mínimo.

Entrada

Leia os seguintes dados da entrada padrão.

$$ \begin{array}{lll} M & R & C\\ D & &\\ U_{1,1} & \cdots & U_{1,C}\\ \vdots & & \vdots\\ U_{R,1} & \cdots & U_{R,C} \end{array} $$

$D$ é uma string de comprimento $M$ que indica a direção de onde o vento vem na IOI Island. $D$ consiste nos quatro tipos de caracteres N, S, W e E. O $k$-ésimo caractere ($1 \le k \le M$) indica a direção de onde o vento vem no período $k$. Observe que essa não é a direção para onde o vento sopra. N significa norte, S significa sul, W significa oeste e E significa leste.

Saída

Escreva duas linhas na saída padrão.

A primeira linha deve conter o menor número de habitantes infectados após $10^{100}$ dias. A segunda deve conter a quantidade de habitantes cuja escolha como primeira pessoa infectada atinge esse número mínimo de habitantes infectados.

Restrições

• $1 \le M \le 100\,000$.
• $1 \le R \le 800$.
• $1 \le C \le 800$.
• $D$ é uma string de comprimento $M$ que contém apenas N, S, W e E.
• $0 \le U_{i,j} \le 100\,000$ ($1 \le i \le R$, $1 \le j \le C$).
• Existe pelo menos um par $(i,j)$ tal que $1 \le U_{i,j}$ ($1 \le i \le R$, $1 \le j \le C$).

Subtarefas

1. (14 pontos) $D$ contém apenas W e E.
2. (6 pontos) $1 \le R \le 50$, $1 \le C \le 50$.
3. (80 pontos) Não há restrições adicionais.

Exemplos

Entrada 1

6 3 4
SWNEES
2 1 1 2
1 0 1 3
1 1 2 2

Saída 1

8
8

Explicação

Considere a escolha do habitante $(3,1)$ como a primeira pessoa infectada.

• Para o habitante $(2,1)$, no período $1$ do dia $1$, o vento vem do sul e o habitante adjacente ao sul já está infectado. Portanto, ele estará infectado a partir do período $2$ do dia $1$.
• Para o habitante $(3,2)$, no período $2$ do dia $1$, o vento vem do oeste e o habitante adjacente a oeste já está infectado. Portanto, ele estará infectado a partir do período $3$ do dia $1$.
• Para o habitante $(1,1)$, no período $6$ do dia $1$, o vento vem do sul e o habitante adjacente ao sul já está infectado; no período $1$ do dia $2$, o vento também vem do sul e o habitante adjacente ao sul já está infectado. Portanto, ele estará infectado a partir do período $2$ do dia $2$.
• Para o habitante $(1,2)$, no período $2$ do dia $2$, o vento vem do oeste e o habitante adjacente a oeste já está infectado. Portanto, ele estará infectado a partir do período $3$ do dia $2$.
• Para o habitante $(1,3)$, no período $2$ do dia $3$, o vento vem do oeste e o habitante adjacente a oeste já está infectado. Portanto, ele estará infectado a partir do período $3$ do dia $3$.
• Para o habitante $(2,3)$, no período $3$ do dia $3$, o vento vem do norte e o habitante adjacente ao norte já está infectado. Portanto, ele estará infectado a partir do período $4$ do dia $3$.
• Para o habitante $(3,3)$, no período $2$ do dia $4$, o vento vem do oeste e o habitante adjacente a oeste já está infectado; no período $3$ do dia $4$, o vento vem do norte e o habitante adjacente ao norte já está infectado. Portanto, ele estará infectado a partir do período $4$ do dia $4$.

Nenhum outro habitante será infectado pelo JOI Virus. Assim, ao escolher o habitante $(3,1)$ como a primeira pessoa infectada, haverá $8$ habitantes infectados pelo JOI Virus após $10^{100}$ dias.

Independentemente de qual habitante seja escolhido como a primeira pessoa infectada, não podemos obter menos de $8$ habitantes infectados pelo JOI Virus após $10^{100}$ dias. Portanto, devemos escrever $8$ na primeira linha. Se escolhermos o habitante $(1,1)$, $(1,2)$, $(1,3)$, $(2,1)$, $(2,3)$, $(3,1)$, $(3,2)$ ou $(3,3)$ como a primeira pessoa infectada, o número de habitantes infectados após $10^{100}$ dias será $8$. Portanto, devemos escrever $8$ na segunda linha.

Entrada 2

4 4 4
EWWE
1 2 1 2
1 1 1 1
0 0 0 0
2 2 2 4

Saída 2

3
3

Explicação

Este exemplo de entrada e saída satisfaz as restrições da Subtarefa 1.