• Trận Bulge thuộc chiến dịch Ardennes diễn ra vào mùa đông năm 1944 cũng là giai đoạn cuối của thế chiến II. Địa điểm nằm ở khu rừng Ardennes thuộc Bỉ, Luxembourg và Đức. Trận chiến gồm liên quân đồng minh và Đức Quốc Xã. Bối cảnh diễn ra chiến dịch Ardennes là khi Đức đang phải phòng thủ trên hai mặt trận ở phía đông và phía Tây. Trận Bulge là trận phản công lớn nhất cuối cùng của Đức nhằm đột kích qua vùng núi Ardennes để chia cắt lực lượng Anh và Mỹ để chiếm lại cảng chiến lược Antwerp. Không chỉ vậy, nếu Đức chiếm được thành công trong chiến dịch Ardennes thì sẽ có thể ép được phe đồng minh ký hiệp ước hòa bình riêng rẽ để tập trung lực lượng vào một mặt trận duy nhất ở phía đông để đấu với Liên Xô.
• Về tương quan lực lượng, Đức sử dụng khoảng 30 sư đoàn thiện chiến nhất như tập đoàn quân thiết giáp SS6 gồm sư đoàn thiết giáp SS1, SS2, SS9 và SS12 cùng với một số sư đoàn khác. Các lực lượng này bao gồm \(410.000\) quân (tăng lên \(500.000\) quân trong giai đoạn cao điểm của chiến dịch), số xe tăng và xe bọc thép được sử dụng từ \(1.400 - 1.800\) chiếc, \(2.600\) khẩu pháo các loại và \(1.000 - 1.600\) chiếc máy bay. Đối với phe đồng minh, đã dùng tổng cộng \(25 - 30\) sư đoàn bao gồm sư đoàn dù 101, 82, 6; sư đoàn thiết giáp số 2, 4 và sư đoàn thiết giáp cận vệ của Anh với cùng các sư đoàn bộ binh khác, lực lượng bao gồm \(700.000 - 800.000\) quân với Mỹ là chủ lực (\(600.000\) quân) và Anh (\(55.000\) quân) còn lại là của Pháp, Bỉ, Canada, Luxembourg. Tổng số xe tăng và xe bọc thép ban đầu chỉ có \(400\) chiếc nhưng đã tăng lên hơn \(3.000\) chiếc sau khi có viện binh. Về phần không quân và pháo binh, có hơn \(4.100\) khẩu pháo và hàng nghìn chiếc máy bay các loại.

• Để chiến dịch được diễn ra thuận lợi, người Đức đã chọn thời gian diễn ra vào mùa đông sương mù dày đặc và tuyết rơi nhiều để vô hiệu hóa ưu thế về không quân của phe đồng minh. Trong giai đoạn đầu, 16/12/1944, Đức mở màn bằng trận pháo kích dữ dội và tung \(200.000\) quân cùng các sư đoàn thiết giáp panzer đột kích qua rừng Ardennes. Từ 20/12 đến 27/12/1944, Sư đoàn dù 101 của Mỹ bị bao vây tại nút giao thông Bastogne nhưng đã kiên cường cố thủ. Đến ngày 26, tập đoàn quân số 3 do tướng Patton (Mỹ) đã gỡ vòng vây và giải cứu sư đoàn dù 101 ở Bastogne, đồng thời không quân đồng minh xuất kích càn quét xe tăng và đoàn xe tiếp tế nhiên liệu của Đức. Đến ngày 25/01/1945, quân Mỹ và liên quân đã đẩy lùi hoàn toàn quân Đức và đưa đường ranh giới về vị trí ban đầu.
• Trận chiến Bulge là cuộc tấn công tiêu hao toàn bộ lực lượng xe tăng, không quân, nhiên liệu dự trữ cuối cùng của Đức Quốc Xã, mở đường cho quân đồng minh tiến thẳng vào lãnh thổ Đức từ phía Tây, góp phần kết thúc Thế chiến II tại châu Âu vào tháng 5/1945.

Input

• Cho \(n\) và \(m\) lần lượt là chiều dọc và chiều ngang (\(0 < n, m < 206\)). (vị trí bắt đầu từ 1 1)
• Nhập \(1\) mảng \(2\) chiều:
  • O là đường có thể đi (số bước tối ưu, thực tế +1).
  • X là đường không thể đi qua do đang là vị trí của quân Đức.
  • V là đường có thể đi (số bước tối ưu -1) (nếu V nằm trong phạm vi của Q thì số bước giữ nguyên -1).
  • Q là đường không thể đi qua. Nếu O nằm trong phạm vi \(1\) ô quanh Q thì O có giá trị là \(1\) còn V giữ nguyên. Số bước tối ưu sẽ bị ảnh hưởng bởi Q còn số bước thực tế thì không (O = \(1\)).
  • S là vị trí bắt đầu.
  • E là vị trí kết thúc.

Output

• In ra số bước khi đi đường tối ưu để vượt qua phòng tuyến bao vây của quân Đức (không tính bước khi ở S và E). In ra số bước di chuyển thực tế (số bước chỉ tính bằng O và không tính bằng Q, V).
• In ra các bước di chuyển khi đi đường tối ưu (vẫn in ra tọa độ của S dù không tính bước).

Example

10 15
S X X X X X X X X X O V Q X Q
O Q X X X O O V V X O O O X V
O O X X Q X X Q O X X X O X O
O O O O X X X O O O O O X X O
X Q X O O O X X O X X O Q X X
X O O O X X X V O O X O X X X
X O X X O O O O X X O V X X X
O O X O X O X O X O O X X X X
O X O O O O X O X O X X X X X
O O O Q O O O V X O O O O E X

55 44
1 1
2 1
3 1
4 1
4 2
4 3
4 4
5 4
6 4
6 3
6 2
7 2
8 2
8 1
9 1
10 1
10 2
10 3
9 3
9 4
9 5
9 6
8 6
7 6
7 7
7 8
6 8
6 9
5 9
4 9
4 10
4 11
4 12
5 12
6 12
7 12
7 11
8 11
8 10
9 10
10 10
10 11
10 12
10 13
10 14