You suddenly find yourself on a very unique ~2~D grid with ~N~ rows and ~M~ columns! Each cell of this grid is either a road, or a swamp, and can only be traversed through by going up, down, left or right. Being the curious person you are, you have planned ~T~ potential trips to go on. However, on some of these trips, you may be forced to walk through a swamp!

Given a map of this grid, showing which sections are roads and which sections are swamps and the starting and ending points for ~T~ potential trips, can you figure out if these trips can be done without going through a swamp?

Input Specification

The first line will contain ~C~, the number of cases.

Each case will start off with three positive integers ~N~, ~M~, and ~T~, representing the number of rows, number of columns and number of trips, respectively.

The next ~N~ lines will each contain a string of ~M~ characters, each character being R or S, representing a road or a swamp.

The next ~T~ lines contain ~4~ integers each, ~r_s~, ~c_s~, ~r_e~, and ~c_e~, representing the starting row and column and the ending row and column for a potential trip.

Output Specification

For each case, if the trip can be made without traversing through a swamp, output safe, otherwise output alligator.

Subtasks

Subtask 1 [20%]

• ~1 \leq C \leq 100~
• ~1 \leq N, M \leq 20~
• ~1 \leq T \leq 100~

Subtask 2 [80%]

• ~1 \leq C \leq 20~
• ~1 \leq N, M \leq 1000~
• ~1 \leq T \leq 10^5~

Sample Input 1

2
6 5 3
RRSSR
RRSRR
SRRRS
RSSRR
SRRRS
RRSSR
1 5 6 1
4 1 1 1
2 4 6 5
2 2 1
RS
SR
1 1 2 2

Sample Output 1

safe
alligator
alligator
alligator