Các trận không kích Berlin năm 1945 là giai đoạn tàn khốc và mang tính quyết định nhất nhằm phá hủy hoàn toàn trung tâm đầu não của Đức Quốc xã trong Chiến tranh Thế giới thứ hai. Vào đầu năm này, thủ đô Berlin trở thành mục tiêu oanh tạc với tần suất chưa từng có từ lực lượng Không quân Lục quân Mỹ và Không quân Hoàng gia Anh qua chiến thuật oanh tạc liên tục cả ngày lẫn đêm. Trong đó, trận oanh tạc ban ngày lớn nhất lịch sử vào ngày 3 tháng 2 năm 1945 do quân đội Mỹ thực hiện với gần 1.000 pháo đài bay B-17 đã trút xuống trung tâm thành phố gần 2.300 tấn bom, phá hủy khu vực chính phủ và khiến hàng ngàn người thiệt mạng. Tiếp đó, cuộc tấn công lớn cuối cùng của Mỹ vào ngày 18 tháng 3 năm 1945 với hơn 1.200 máy bay ném bom đã xóa sổ phần lớn các tổ hợp công nghiệp quân sự còn lại. Chiến dịch không kích khép lại bằng trận đánh đêm của không quân Anh từ ngày 20 đến ngày 21 tháng 4 năm 1945, ngay trước thời điểm pháo binh Liên Xô tiến sát và bao vây thành phố.

Chuỗi oanh tạc liên tục này đã để lại những hệ quả nặng nề và tác động sâu sắc đến cục diện chiến trường trên bộ. Toàn bộ cơ sở hạ tầng cốt lõi của Berlin bao gồm mạng lưới đường sắt, ga tàu điện ngầm, hệ thống điện nước và thông tin liên lạc bị sụp đổ hoàn toàn. Ngay cả các cơ quan đầu não quan trọng như Phủ Thủ tướng Đức hay mật thất ngầm của Adolf Hitler cũng rơi vào tình trạng hư hại nghiêm trọng và bị cô lập. Dù các tháp phòng không khổng lồ bằng bê tông cốt thép vẫn đứng vững để che chở cho dân thường, quân đội Đức tại đây đã hoàn toàn kiệt quệ do thiếu hụt nhiên liệu, đạn dược và không thể tổ chức tiếp tế hay điều động lực lượng. Những thiệt hại nặng nề từ trên không đã làm suy yếu tận gốc khả năng phòng thủ của thủ đô Đức, mở đường và tạo điều kiện thuận lợi cho Hồng quân Liên Xô dễ dàng công phá, làm chủ thành phố trong chiến dịch trên bộ diễn ra ngay sau đó, dẫn đến sự sụp đổ hoàn toàn của Đệ tam Đế chế vào tháng 5 năm 1945.

Một trong ba pháo đài phòng không bảo vệ Berlin:

Bạn được giao nhiệm vụ điều khiển một đơn vị vượt qua Berlin từ vị trí xuất phát \(S\) đến vị trí cần đến \(E\).
Thành phố được mô tả bởi một mạng lưới \(n \cdot m\). Mỗi ô có thể là:

• S: vị trí xuất phát.
• E: vị trí cần đến.
• O: khu vực có thể di chuyển.
• B: khu vực đang bị oanh tạc.
• R: tuyến đường sắt.
• X: khu vực bị phá hủy hoàn toàn, không thể đi qua.

Bạn có thể di chuyển sang một trong bốn ô kề cạnh. Không được di chuyển theo đường chéo và không được đi qua các ô X.
Trong suốt quá trình di chuyển, các cuộc oanh tạc vẫn tiếp tục diễn ra. Có \(K\) đợt oanh tạc, mỗi đợt được mô tả bởi:

• \(t\)
• \(x\)
• \(y\)
• \(r\)
• \(p\)

Tùy loại bom, các khu vực bị ảnh hưởng có thể chịu những mức thiệt hại khác nhau. Một khu vực có thể bị ảnh hưởng nhiều lần và có thể trở nên không thể đi qua.

Các tuyến đường sắt R cho phép di chuyển nhanh hơn đường bình thường, nhưng có thể bị phá hủy trong quá trình oanh tạc.
Trong thời điểm \(t\), bom ảnh hưởng đến tất cả các ô \((i, j)\) thỏa mãn:

• Tùy loại bom, các khu vực bị ảnh hưởng có thể chịu những mức thiệt hại khác nhau. Một khu vực có thể bị ảnh hưởng nhiều lần và có thể trở nên không thể đi qua.
• Các tuyến đường sắt R cho phép di chuyển nhanh hơn đường bình thường, nhưng có thể bị phá hủy trong quá trình oanh tạc.

Hãy tìm đường đi từ \(S\) đến \(E\) sao cho:

• Thời gian đến \(E\) là nhỏ nhất.
  • Nếu có nhiều đường cùng thời gian, chọn đường có số lần đi qua khu vực nguy hiểm nhỏ nhất.
  • Nếu vẫn bằng nhau, chọn đường có tổng thiệt hại nhỏ nhất.
  • Nếu vẫn bằng nhau, chọn đường có ít lần đứng yên nhất.

Input

• Dòng đầu tiên chứa hai số nguyên \(n, m\).
• \(n\) dòng tiếp theo mô tả bản đồ Berlin.
• Dòng tiếp theo chứa số nguyên \(K\).
• \(K\) dòng tiếp theo mô tả các đợt oanh tạc, mỗi dòng gồm:
  • \(t\) \(x\) \(y\) \(r\) \(p\)
• Dòng tiếp theo chứa số nguyên \(L\).
• \(L\) dòng tiếp theo mô tả các tuyến đường sắt hoặc đường hầm, mỗi dòng gồm:
  • \(x_1\)
  • \(y_1\)
  • \(x_2\)
  • \(y_2\)
  • \(t\)

Output

• Dòng đầu tiên in ra \(D, K\)
• Trong đó:
  • \(D\) là giá trị tối ưu của đường đi.
  • \(K\) là số bước di chuyển thực tế.
• Sau đó in ra toàn bộ các tọa độ của đường đi từ \(S\) đến \(E\).
• Mỗi dòng gồm hai số nguyên \(x\) \(y\).
• Tọa độ được đánh số từ \(1\).

Example

7 9
S O O X X X X X X
X O O O O B O X X
X X X X O B O O X
X X X X O R R O X
X X O O O X R E X
X X O B O O O O X
X X X X X X X X X
3
4 6 2 1 1
6 4 4 1 2
8 7 2 1 1
1
2 5 4 7 2

0 8
1 1
1 2
1 3
2 3
2 4
2 5
4 7
5 7
5 8