Trong cuộc thi "Lập trình tự động 2023", mỗi đội tham gia sẽ chuẩn bị một robot và đặt trên địa hình là một vùng hình chữ nhật có \(m\) hàng, \(n\) cột. Nhiệm vụ của robot là sau khi thả vào ô xuất phát, nó cần tránh những ô chướng ngại vật và tìm đường về ô đích trong thời gian ngắn nhất.

Robot của các đội sẽ được quét địa hình và thực hiện tính toán trước trong \(1\) giây. Các thành viên trong đội GURI GURU viết chương trình đọc địa hình tạo thành một bản đồ dạng bảng. Các ô trên bảng được đánh số từ \(1\) tới \(m*n\) theo hướng trái sang phải, trên xuống dưới; kí hiệu \(0\) là ô trống, \(1\) là ô chướng ngại vật. Họ muốn thuật toán tìm đường của GIRU - tên robot của đội - xác định được một số đường ngắn nhất mà rẽ càng ít càng tốt. Cụ thể hơn, trước khi sử dụng thuật toán BFS tìm đường từ ô \(x\) tới ô \(y\), giả sử không có chướng ngại vật thì robot di chuyển tới đích cần ít nhất \(\delta\) bước, thuật toán sẽ tìm một đường tới đích \(y\) trong đúng \(\delta\) bước mà GIRU rẽ không quá hai lần. Chỉ khi không tồn tại đường đi như vậy GIRU mới chạy thuật toán BFS.

Giả sử bạn là một thành viên trong đội GURI GURU, hãy giúp họ lập trình một thuật toán tìm đường cho robot GIRU.

Đầu vào

Dòng đầu tiên chứa ba số nguyên \(m, n, q\) \((1 \le m, n \le 1000, 1 \le q \le 100000)\) lần lượt là số hàng, số cột của bản đồ và số truy vấn.

\(m\) dòng tiếp theo, mỗi dòng gồm \(n\) số \(0\) hoặc \(1\) đặc tả một hàng của bản đồ.

\(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x, y\) \((1 \le x, y \le m*n, x \neq y)\) lần lượt là vị trí ô bắt đầu và vị trí ô đích của Robot.

Không có chướng ngại vật ở ô bắt đầu và ô đích.

Đầu ra

\(q\) dòng, mỗi dòng là câu trả lời của một truy vấn, xuất ra \(FAST\) nếu có đường đi thỏa mãn đề bài, trong trường hợp còn lại xuất ra \(BFS\).

Subtask

\(30\%\) số test có \(1 \le m, n, q \le 100\).

\(30\%\) số test có \(1 \le m, n, q \le 1000\).

Ví dụ

Đầu vào:

5 5 5
1 0 0 0 1
0 1 0 1 0
0 0 1 0 0
0 1 0 1 0 
1 0 0 0 1
2 4
6 12
6 24
10 14
10 20

Đầu ra:

FAST
FAST
BFS
FAST
FAST