Palindrome Pairs

hard

1. Given an array of unique Strings.
2. return all pairs of indices (i, j) for which word[i]+word[j] is a palindrome.

Input Format

Input is managed for you

Output Format

Output is managed for you

Constraints

1. 1 &lt;= words.length &lt;= 5000
2. 0 &lt;= words[i].length &lt;= 300
3. words[i] consists of lower-case English letters.

Notice

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

Example

Input

5
abcd
dcba
lls
s
sssll

Output

[0, 1]
[1, 0]
[2, 4]
[3, 2]

Count Substrings That Differ By One Character

Next Greater Element To The Left