Scrambling Words with No Fixed Positions

You are given a list of words. For each word, you must generate a scrambled version in which no character remains in its original position. In other words, if the original word is represented as a sequence \(w_0w_1\cdots w_{n-1}\), then the scrambled word \(s_0s_1\cdots s_{n-1}\) must satisfy \(s_i \neq w_i\) for every index \(i\). If such a scrambling (or derangement) is impossible for a particular word, output the word unchanged.

Note: A word with all identical characters or a word for which no valid derangement exists should be output without any changes.

The input also includes a pattern string which is not used in the logic and can be ignored.

Example:

Input:
1
apple
pattern
Possible Output:
plepa

</p>

The solution should be implemented such that input is read from standard input (stdin) and the result is printed to standard output (stdout). The use of LaTeX in formulas is demonstrated above.

inputFormat

The first line of input contains an integer \(n\) representing the number of words.

The next \(n\) lines each contain a word consisting of lowercase letters.

The final line contains a pattern string which should be read but is not used in processing.

outputFormat

Output \(n\) lines, each line containing the scrambled version of the corresponding input word, such that for each word \(w\) and its scrambled version \(s\), \(s_i \neq w_i\) for all valid indices \(i\), if a valid scrambling exists. Otherwise, output the original word.

## sample

1
apple
pattern

plepa

</p>