E. talle3 el string lak ab bashiiiir
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Mocha, a playful cat from Harat Al-Daba3, loved playing games. One day, he came across a famous cat named Basboos and wanted to challenge him to a game. However, he couldn't think of a suitable game.

Mocha and Basboos decided to play by each picking a random string. Mocha chose $$$s$$$, and Basboos chose $$$t$$$. The winner would be the one with the lexicographically smaller string.

Abu Bashir overheard their game and wanted to help Mocha win. He came up with an idea: he would generate a third string $$$k$$$ and insert it anywhere within $$$s$$$ and anywhere within $$$t$$$.

More formally, Abu Bashir wants to create two strings $$$s'$$$ and $$$t'$$$ such that $$$s' \lt t'$$$ by inserting $$$k$$$ somewhere into $$$s$$$ and somewhere into $$$t$$$, respectively.

Can you help Abu Bashir find a valid string $$$k$$$ that ensures Mocha's victory, or determine if it's impossible?

Simply speaking, the lexicographical order is the order in which words are listed in a dictionary. $$$^{\text{∗}}$$$

$$$^{\text{∗}}$$$ We say that string $$$a$$$ is lexicographically smaller than string $$$b$$$ if and only if one of the following holds:

  • $$$a$$$ is a prefix of $$$b$$$, but $$$a \neq b$$$.
  • in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

A formal definition is as follows: string $$$p$$$ is lexicographically smaller than string $$$q$$$ if there exists a position $$$i$$$ such that $$$p_i \lt q_i$$$, and for all $$$j \lt i$$$, $$$p_j = q_j$$$.

If no such $$$i$$$ exists, then $$$p$$$ is lexicographically smaller than $$$q$$$ if the length of $$$p$$$ is less than the length of $$$q$$$. For example, $$$abdc \lt abe$$$ and $$$abc \lt abcd$$$, where we write $$$p \lt q$$$ if $$$p$$$ is lexicographically smaller than $$$q$$$.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases.

For each test case you are given two lines containing strings $$$s$$$ and $$$t$$$ respectively $$$(1 \le |s| , |t| \le 10^5)$$$ — $$$|s|$$$ denotes the length of $$$s$$$ and $$$|t|$$$ denotes the length of $$$t$$$.

The string is guaranteed to have only small letters without numbers.

It is guaranteed that the sum of lengths of all strings $$$s$$$ and $$$t$$$ in the input doesn't exceed $$$2\cdot10^5$$$.

Output

For each test case if there is a valid solution print two lines, in the first line print the generated string $$$k$$$ ($$$1 \le |k| \le |s| + |t|$$$), and in the second line print two integers $$$i$$$ ($$$0 \le i \le |s|$$$) which indicates how many characters in string $$$s$$$ will be before string $$$k$$$ and $$$j$$$ ($$$0 \le j \le |t|$$$) which indicates how many characters in string $$$t$$$ will be before string $$$k$$$. If there are multiple solutions, print any of them.

Or say that it impossible by printing $$$-1$$$

Note

In the second test case, the resulted strings are $$$s$$$ = "appl$$${\color{red}{entytaleggg}}$$$epie", $$$t$$$ = "mo$$${\color{red}{entytaleggg}}$$$onthemoon"