Palindrome Pairs Finder

Given a list of words, your task is to find all pairs of distinct words such that the concatenation of the two words forms a palindrome. A palindrome is defined as a string that reads the same forwards and backwards. Formally, for indices \(i\) and \(j\) (with \(i \neq j\)), if the string word_i + word_j is a palindrome then the pair \((i, j)\) is a valid answer (using 1-based indexing).

If one or more valid pairs exist, output each pair in the order they are found, one pair per line, with the two indices separated by a space. If no valid pairs exist, output the string No palindrome pairs found.

inputFormat

The first line of input contains a single integer \(N\) representing the number of words. The following \(N\) lines each contain one word.

outputFormat

If there are palindrome pairs, output each pair on a separate line in the format "i j" (without quotes), where \(i\) and \(j\) are the 1-based indices of the words forming the palindrome when concatenated. If there is no valid pair, output No palindrome pairs found.

4
bat
tab
cat
tac

1 2
2 1
3 4
4 3