Palindromic Concatenation Pairs

You are given a 0-indexed array words of distinct strings.

Return every ordered pair of indices (i, j) with i != j such that the concatenation words[i] + words[j] is a palindrome, as a 2-D array sorted in ascending order: by i first, then by j. This ordering makes the answer unique.

Examples

Example 1

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[2,4],[3,2]]
Explanation: The palindromic concatenations are "abcddcba", "dcbaabcd", "llssssll" and "slls".

Example 2

Input: words = ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: "battab" and "tabbat" are palindromes.

Example 3

Input: words = ["a",""]
Output: [[0,1],[1,0]]
Explanation: The empty string concatenated with "a" in either order gives "a".