Description

Palindrome is a string that is identical to its reverse, like "level" or "aba".  Check whether a given string is a palindrome or not.

Input

The input consists of multiple lines. Each line contains a string. The length of each string is less than 100000.  The number of test case is less than 1000.

Output

For each test case, output "Yes" if it's a palindrome or "No" if it's not a palindrome in a line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

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

Description

After two months of dieting, Yanami Anna decided to reward herself. She signed up for a local district's big eater competition. This competition is different from regular big eater contests, with rules as follows:

There's a food map with N rows and M columns. Each spot on the map has a number showing the points for eating that food. You can only pick a square or rectangle area to eat from. The person with the highest score can win the championship prize.

 

Yanami hopes you can help her find the area with the highest total score. She needs your help to tell her where this area is by giving her top-left and bottom-right corner points: (X₁ , Y₁ ), (X₂ , Y₂). Don't worry if it seems like too much food - she'll be fine.

If there's more than one answer:

1. Pick the one with the smallest X_{1 .}
2. If X₁  is the same, choose the smaller Y_{1 .}
3. If both X₁  and Y₁  are the same, choose the smaller X_2.
4. If X₁ , Y₁ , and X₂ are all the same, choose the smaller Y_2.

 

In the sample test case, the green area represents the region with the highest total score.

The top-left and bottom-right corner points: (X₁ , Y₁ ), (X₂ , Y₂) are shown in the figure below.

Input

The first line contains N and M, representing the number of rows and columns of the map.

The following N lines represent the map, each containing M integers.

Constraints

• 1 ≤ N, M ≤ 150
• 1 ≤ i ≤ N
• 1 ≤ j ≤ M
• -10⁹ ≤ C_i,j ≤ 10⁹

​Subtasks

• Testcases 1 ~ 3: 1 ≤ N, M ≤ 10, -10⁵ ≤ C_i,j ≤ 10⁵
• Testcases 4 ~ 6: 1 ≤ N, M ≤ 100
• Testcases 7 ~ 8: No additional restrictions.

 

Output

The first line contains the top-left corner point: (X₁ , Y₁ ).

The second line contains the bottom-right corner point: (X₂ , Y₂).

 

Please remember to print "\n" at the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss