Description

Big Orange Cat (大橘) loves doing puzzles. He has n types of puzzles, and each puzzle i can be represented by a string A_i composed of all visible characters from the ASCII code.

Unfortunately, he messed up the puzzles. What a baganono... Now for each puzzle i, he has found some puzzle pieces, represented by a string B_i. You can choose any interval l_i, r_i, and select some puzzle pieces from B[li] to B[ri]. If it's possible to rearrange these pieces to form A_i, then this interval [l_i, r_i] is called a 'valid interval'.

Your task is to find a valid interval that meets the following conditions:

1. r_i - l_i is minimized
2. If there are multiple solutions for the first condition, find the one with the smallest l_i
3. If there are still multiple solutions after the above two conditions, find the one with the smallest r_i

After finding a valid interval that meets these conditions, tell Big Orange Cat which positions within this interval he should take puzzle pieces from to form A_i. However, there might be many ways to do this, and since Big Orange Cat is very lazy, please output the lexicographically smallest method. If there's no valid interval at all, output 'baganono'.

Important: The method for comparing the lexicographic order of two strings is as follows: Starting from the first position (leftmost), find the first character that differs. The string with the smaller character at that position is considered lexicographically smaller. For example, "abc" < "abd" because the first differing letter 'c' < 'd'.
BUT!!: The lexicographically smallest solution for this problem refers to the lexicographically smallest sequence of indices chosen. The comparison logic is similar to that used for characters, but instead applies to entire integers (e.g., [1, 2, 3] < [1, 3, 3], [1, 2, 3] < [1, 11, 111]).

Input

The first line of input contains an integer n. n represents the number of puzzle-instruction manual pairs.

The following n lines each contain two strings, A_i and B_i, separated by a space. They represent the i-th puzzle and instruction manual, respectively.

Constraints

• 1 ≤ n ≤ 500
• All strings are composed of uppercase and lowercase letters, and any visible symbols that can be represented by ASCII code (ASCII Codes 33 to 126)
• 1 ≤ | A_i | ≤ | B_i | ≤ 10000 (| S | represents the length of string S)

Subtasks

• Testcase 1: | A_i | = | B_i | ≤ 50, characters within A_i , B_i are arranged in ascending lexicographic order.
• Testcase 2: It is guaranteed that there is only one valid interval,  | A_i | ≤ | B_i | ≤ 50
• Testcases 3, 4: | A_i | ≤ | B_i | ≤ 50
• Testcase 5: | A_i | ≤ | B_i | ≤ 1000
• Testcase 6: No additional restrictions.

Output

 

Output the answer for each pair of A_i and B_i in sequence. The answer may have two possible situations:

1. If a valid interval is found and an answer is obtained:
   Output two lines:
   The first line contains two integers l_i and r_i, representing the optimal valid interval you found.
   The second line contains | A_i | integers, representing the positions of characters you need to take from the interval [B[li], B[ri]] to form A_i. Output these in ascending order (assuming the answer is x₁, x₂, x₃, ..., then x₁ < x₂ < x₃ < ...).
2. If no valid interval is found:
   Simply output "baganono" (without quotes)

Please remember to print "\n" at the end, and dont print space (" ") at the end of every line.

Explanation of sample I/O:

1. abc cczbb@aa: There are four valid intervals: [1, 7], [1, 8], [2, 7], [2, 8]. Among these, [2, 7] has the minimum distance, so this valid interval is chosen. Within this interval, there are two ways to form "abc": [2, 4, 7] and [2, 5, 7]. The former is lexicographically smaller, so output 2 4 7.
2. aaa aabc: There is no valid interval, so output baganono.
3. qwe qwe: There is only one valid interval and one method, so output 1 2 3.

Sample Input  Download

Sample Output  Download

Tags

Discuss