Find Palindrome Pairs

Given a list of words, find all unique pairs of indices ( (i, j) ) such that the concatenation of words[i] and words[j] forms a palindrome. A string is considered a palindrome if it reads the same forwards and backwards. For example, if the list of words is ["bat", "tab", "cat"], then the valid pairs are ( (0, 1) ) and ( (1, 0) ) because "bat"+"tab" and "tab"+"bat" are palindromes. Read the words from standard input (stdin) and output each valid pair on a new line in the format 'i j', sorted in ascending order (first by i then by j). If no such pairs exist, output nothing.

inputFormat

The first line contains an integer ( n ), the number of words. Each of the following ( n ) lines contains a single word.

outputFormat

For each valid pair ( (i, j) ) where the concatenation of words[i] and words[j] is a palindrome, output a line with two integers separated by a space. The pairs must be sorted in ascending order first by ( i ) then by ( j ). If there are no valid pairs, output nothing.## sample

3
bat
tab
cat

0 1
1 0