Sort Matrix Anti-Diagonals by Their Letter Sequences

Problem Given an n x n character matrix where each cell contains a lowercase English letter. Consider all anti-diagonals going from bottom-left to top-right, i.e. all diagonals satisfying row + col = k. There are 2n - 1 such diagonals. In this problem, the index of a diagonal is defined as k, where: k = row + col 0 <= k <= 2n - 2 The string of a diagonal is formed by reading its characters from bottom-left to top-right, meaning row decreases while col increases Sort all diagonals lexicographically by their corresponding strings, and output the sorted sequence of diagonal indices. If two diagonal strings are identical, the smaller index should come first. Input Format The first line contains an integer n. The next n lines each contain a string of length n, representing one row of the matrix. Output Format Print 2n - 1 integers: the diagonal indices after sorting by their diagonal strings. Separate integers with one space. Constraints 1 <= n <= 1000 All matrix characters are lowercase English letters 'a' to 'z' The total number of characters is n^2 Example Input: 2 za by Output: 1 2 0 Explanation: Index 0: "z" Index 1: "ba" Index 2: "y" Sorted lexicographically: "ba", "y", "z", so the answer is 1 2 0. Example Input 2 za by Output 1 2 0