Largest Squares

Given a rectangular grid of characters, find the location of the largest square which contains only characters from a given set. For example given the following grid, and the set of characters {'a', 'b'}, the location (2, 3) is the corner of the largest square (with side length 3) which contains only the characters from the set. Given the location (1, 2) the length of a side of the largest square is 3.

abbbaaaaaa
abbbaaaaaa
abbbaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaccaaaaaa
aaccaaaaaa

Input

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set starts with a line containing two integers, R and C, separated by a space, with 1 ≤ R ≤ 1,000,000 and 1 ≤ C ≤ 1,000,000, representing the number of rows and columns, respectively, in the grid for this data set. This is followed by Q, the number of characters that specify the location of non-empty cells in the grid, with 0 ≤ Q ≤ 100,000. The Q lines that follow each contain three items, R, C and V, separated by a space, where 0 ≤ R < R, 0 ≤ C < C, and V is a single character from the set {a,b,c,...,z}, indicating that row R and column C of the grid contains character V. All other characters in the grid are considered blank. No location will be specified more than once.

Output

For each data set, output R C S on a single line, separated by spaces, where R and C are the row and column number of the top left corner of the largest square containing only identical characters, and S is the length of a side of that square. If more than one such square exists, pick the one with the smallest value of R. If there is still a tie, pick the one with the smallest value of C. Every data set will have an answer with S ≥ 1.

#10908Largest Squares

Input

Output