Giải bài trực tuyến

                Sau nhiều năm trời rong ruổi trên nước Mỹ, Trung đã trở thành một chuyên gia hàng đầu trong lĩnh vực Robot và làm việc cho NASA. Năm 2030 có một dự án hợp tác giữa Mỹ và Việt Nam hứa hẹn sẽ đưa ngành công nghiệp vũ trụ thế giới lên một tầm cao mới : đưa robot thăm dò địa chất lên sao Mộc. Do là kỹ sư hàng đầu, Trung được giao cho việc lập trình hệ thống điều khiển của Robot.

            Ngày trọng đại đã đến : Robot LEGO được phi thuyền SSO đưa vào vũ trụ và hạ cánh trên sao Mộc. LEGO được dự tính sẽ hạ cánh trên một mỏ quặng nhưng do có sai sót nhỏ trong quá trình tính toán, SSO đưa LEGO đến một địa điểm khác. Trên Trái đất, Trung có nhiệm vụ truyền lệnh để LEGO đến được mỏ quặng. Một dãy lệnh S là một dãy các số nguyên S_i với độ dài L. Khi LEGO nhận được dãy S, bộ giải mã sẽ bắt đầu đọc theo thứ tự S₁, S₂, S₃, …, S_L. Khi gặp số nguyên S_i, nếu

• S_i> 0 : LEGO di chuyển về phía trước S_i bước
• S_i = 0 : LEGO quay sang trái 90⁰
• S_i = -1 : LEGO quay sang phải 90⁰
• S_i< -1 : LEGO đi lùi về phía sau (-S_i -1) bước (hướng trước mặt vẫn không đổi)

            Điều khiển LEGO tới mở quặng là một chuyện hết sức đơn giản với Trung. Tuy nhiên do là cựu học sinh chuyên Tin, Trung hứng thú với một câu hỏi vừa nảy ra trong đầu : có bao nhiêu dãy lệnh điều khiển khác nhau gồm ít lệnh nhất để LEGO đến được mỏ quặng ? Hai dãy lệnh điều khiển S và T độ dài L được xem là khác nhau nếu tồn tại một vị trí i <= L sao cho S_i ≠ T_i. Trung chỉ cần điều khiển LEGO di chuyển đến mỏ quặng, hướng của nó không quan trọng.

            LEGO có một camera hồng ngoại ghi lại địa hình khu vực xung quanh. Hình ảnh này được truyền về Trái đất dưới dạng một bản đồ hình chữ nhật kích thước MxN (miêu tả trong input).   LEGO chỉ di chuyển được trên địa hình bằng phẳng. Mỗi bước di chuyển LEGO có thể đi đến ô ngay phía trước hoặc phía sau hướng nó đang quay mặt tới.

Input

               Dòng đầu tiên là 2 số nguyên dương M, N            (1 <= M, N <= 200)

            M dòng sau, dòng thứ i gồm N kí tự A[i,j] thể hiện bản đồ. A[i,j] có thể là :

• ‘.’                          : địa hình bằng phẳng
• ‘*’                         : địa hình gồ ghề, hiểm trở
• ‘X’                         : vị trí mỏ quặng. Có duy nhất một mỏ.
• ‘E’ , ‘W’, ‘S’ hoặc ‘N’ : vị trí hiện tại và hướng trước mặt của LEGO (tương ứng với Đông, Tây, Nam, Bắc).

Output

                Gồm 2 số nguyên dương là L – độ dài dãy lệnh ngắn nhất và K – số dãy lệnh khác nhau có cùng độ dài L có thể đưa LEGO đến mỏ quặng. Nếu không tồn tại đường đi xem như L = K = 0.

Example

Input:
6 5
. . . . X
. * * * .
. * * * .
. * * * .
. * * * .
N . . . .

Chú ý : Trong bộ test thật giữa các kí tự A[i,j] không có khoảng trắng
Output:
3 2

Giải thích : Có 2 dãy lệnh là 5 -1 4 và 5 0 -5