Sau khi Youtuber_TWK đã lấy được những phần quà thì NYC đã lấy các món quà đó giấu vào một mê cung tử thần. Sau khi giấu xong thì NYC đã nói đây sẽ là thử thách thứ 2. Trong mê cung tử thần ấy có một con quái vật luôn đi theo một tuyến nhất định trong mê cung. Youtuber_TWK phải đi tìm lại tất cả món quà đó mà không bị quái vật bắt được.

Yêu cầu

• Hãy giúp Youtuber_TWK tìm được con đường tối ưu giúp lấy tất cả món quà mà không bị quái vật bắt.

Lưu Ý: Vị trí xuất phát là [1 1] và đi đến E (E là điểm kết thúc của mê cung).

Input

• Cho \(n\) và \(m\) lần lượt là chiều dài và chiều rộng của mê cung (\(1 \le n, m \le 205\)).
• Nhập một mảng hai chiều là mê cung tử thần:
  • O: là đường đi.
  • X: là tường chắn.
• Cho \(Q\) là số bước của quái vật di chuyển trong mê cung (Khi quái vật đi hết tới cuối thì nó đi quay về vị trí bắt đầu của nó tạo thành chu kì kín, Youtuber_TWK có thể đi qua đường đi của quái vật miễn sao quái vật không nằm tại cùng vị trí với Youtuber_TWK) (\(2 \le Q \le 100\)).
• Trong \(Q\) dòng tiếp theo là các bước di chuyển của quái vật (trình tự này cố định).
• Cho \(K\) là số lượng món quà bị giấu (\(1 \le K \le 10\)).
• Trong \(K\) dòng tiếp theo là vị trí giấu của món quà (món quà không thể ở vị trí là tường chắn).

Output

• Số bước đi.
• Lần lượt các dòng còn lại sẽ là các bước di chuyển để tìm quà và tránh quái vật.

Example

5 9
OOOOOOOOO
XXOXXOXXO
XXOXXOXXO
XXOXXXXXO
XXXXXXXXE
7
1 7
1 8
1 9
2 9
1 9
1 8
1 7
3
4 3
1 5
3 6

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