Problem Brief

Palindromic Array Transformation

NEW GRADOA

SDE I

An array is called palindromic if it remains the same after reversing the order of its elements.

You have an array of strings arr. For each i, arr[i] consists of at least two characters. For each pair of consecutive elements arr[i] and arr[i + 1], you can:

Move the rightmost character of arr[i] to the leftmost position in arr[i + 1]. For instance, "abc" and "def" will become "ab" and "cdef". This operation can be applied only once to any pair of consecutive elements.

Move the leftmost character of arr[i + 1] to the rightmost position in arr[i]. For instance, "abc" and "def" will become "abcd" and "ef". Again, this operation can be applied only once to any pair of consecutive elements.

Do nothing to the pair of consecutive elements.

Is it possible to obtain a palindromic array from arr by performing these operations?

return 1 --> True
return 0 --> False

Return 1 if the given array can be turned into a palindromic array, otherwise return 0.

1Example 1

Input

arr = ["aa", "bab", "cde", "aba", "ab"]

Output

Explanation

Apply the second operation to "aa" and "bab". Apply the first operation to "aba" and "ab". This gives us the following array: ["aab", "ab", "cde", "ab", "aab"], which is palindromic.

2Example 2

Input

arr = ["palindrome"]

Output

Explanation

The given array is already palindromic, so no operations are needed.

3Example 3

Input

arr = ["aaaaaa", "aa"]

Output

Explanation

If moving two characters between two consecutive array elements was allowed, the array could have been made palindromic, but this is impossible given the actual rules.

Constraints

Limits and guarantees your solution can rely on.

1 ≤ arr.length ≤ 10^5
2 ≤ arr[i].length ≤ 10