example.log

2024-03-25 15:58:26.602 | INFO     | alpha_codium.gen.coding_competitor:solve_problem:120 - problem['name']: 1575_A. Another Sorting Problem
2024-03-25 15:58:26.626 | INFO     | alpha_codium.gen.coding_competitor:run:63 - Running code contests competitor, model gpt-3.5-turbo
2024-03-25 15:58:26.627 | INFO     | alpha_codium.gen.stages.run_self_reflect:run_self_reflect:18 - --reflection stage--
2024-03-25 15:58:26.645 | INFO     | alpha_codium.llm.ai_handler:chat_completion:88 - -----------------
2024-03-25 15:58:26.646 | INFO     | alpha_codium.llm.ai_handler:chat_completion:89 - Running inference ...
2024-03-25 15:58:26.647 | DEBUG    | alpha_codium.llm.ai_handler:chat_completion:90 - system:
The self-reflection must cover every aspect of the problem. Pay attention to small details and nuances in the problem description.
2024-03-25 15:58:26.648 | DEBUG    | alpha_codium.llm.ai_handler:chat_completion:91 - user:
You are given a code contest problem:

problem name: '1575_A. Another Sorting Problem'


problem description:
=====
Andi and Budi were given an assignment to tidy up their bookshelf of n books. Each book is represented by the book title — a string s_i numbered from 1 to n, each with length m. Andi really wants to sort the book lexicographically ascending, while Budi wants to sort it lexicographically descending.

Settling their fight, they decided to combine their idea and sort it asc-desc-endingly, where the odd-indexed characters will be compared ascendingly, and the even-indexed characters will be compared descendingly.

A string a occurs before a string b in asc-desc-ending order if and only if in the first position where a and b differ, the following holds:

  * if it is an odd position, the string a has a letter that appears earlier in the alphabet than the corresponding letter in b; 
  * if it is an even position, the string a has a letter that appears later in the alphabet than the corresponding letter in b. 

Input

The first line contains two integers n and m (1 ≤ n ⋅ m ≤ 10^6).

The i-th of the next n lines contains a string s_i consisting of m uppercase Latin letters — the book title. The strings are pairwise distinct.

Output

Output n integers — the indices of the strings after they are sorted asc-desc-endingly.

Example

Input


5 2
AA
AB
BB
BA
AZ


Output


5 2 1 3 4

Note

The following illustrates the first example.

<image>
=====


Given the code contest problem, you have two tasks:
1) Reflect on the problem, and describe it in your own words, in bullet points. Pay attention to small details, nuances, notes and examples in the problem description.
2) Explain how each provided example input leads to the corresponding output (in total 1 examples are provided).
Read carefully the problem description. Make sure the test explanations are consistent with them, and between themselves.
The explanation must coherently and logically lead from the input to the output. Be as specific as possible.

The output must be a YAML object equivalent to type $ProblemReflection, according to the following Pydantic definitions:
=====
Class InputOutput(BaseModel):
    input: str
    output: str
    explanation: str = Field(description="Short explanation how the test input leads to the test output.")


class ProblemReflection(BaseModel):
    self_reflection: str = Field(description="Describe the problem in your own words, in bullet points. Address the problem goals, inputs, outputs, rules, constraints, and other relevant details.")
    tests_explanations: list[InputOutput] = Field(max_items=1, description="List of explanations for each test case")
=====

Example YAML output:
```yaml
self_reflection:
- |
  ...
- |
  ...
tests_explanations:
- input: |
    ...
  output: |
    ..
  explanation: |
    ...
...
 ```


Answer:
```yaml
2024-03-25 15:58:35.176 | DEBUG    | alpha_codium.llm.ai_handler:chat_completion:134 - response:
```yaml
self_reflection:
- The problem involves sorting a list of book titles in a specific manner based on odd and even indices.
- Andi wants to sort the books lexicographically ascendingly, while Budi wants to sort them lexicographically descendingly.
- The combined sorting method involves comparing odd-indexed characters in ascending order and even-indexed characters in descending order.
- The input consists of the number of books, the length of each book title, and the book titles themselves.
- The output should be the indices of the book titles after sorting them using the specified method.

tests_explanations:
- input: |
    5 2
    AA
    AB
    BB
    BA
    AZ
  output: |
    5 2 1 3 4
  explanation: |
    In this example, we have 5 book titles with a length of 2 characters each.
    After sorting them asc-desc-endingly:
    - Comparing based on odd indices (1st character):
      - AZ (5th) comes before AA (1st).
      - AB (2nd) comes before BA (4th).
      - AA (1st) comes before BB (3rd).
      - BB (3rd) comes before BA (4th).
      - BA (4th) comes before AZ (5th).
    - Comparing based on even indices (2nd character):
      - AZ (5th) comes before AB (2nd).
      - AB (2nd) comes before AA (1st).
      - AA (1st) comes before BA (4th).
      - BA (4th) comes before BB (3rd).
      - BB (3rd) comes before AZ (5th).
    Therefore, the sorted indices are 5 2 1 3 4.
```
2024-03-25 15:58:35.176 | INFO     | alpha_codium.llm.ai_handler:chat_completion:135 - done
2024-03-25 15:58:35.177 | INFO     | alpha_codium.llm.ai_handler:chat_completion:136 - -----------------
2024-03-25 15:58:35.179 | INFO     | alpha_codium.gen.stages.run_generate_possible_solutions:run_generate_possible_solutions:18 - --generate possible solutions stage--
2024-03-25 15:58:35.187 | INFO     | alpha_codium.llm.ai_handler:chat_completion:88 - -----------------
2024-03-25 15:58:35.188 | INFO     | alpha_codium.llm.ai_handler:chat_completion:89 - Running inference ...
2024-03-25 15:58:35.188 | DEBUG    | alpha_codium.llm.ai_handler:chat_completion:90 - system:
Pay attention to small details and nuances in the problem description.
2024-03-25 15:58:35.189 | DEBUG    | alpha_codium.llm.ai_handler:chat_completion:91 - user:
You are given a code contest problem, and a self-reflection on the problem:

problem description:
=====
Andi and Budi were given an assignment to tidy up their bookshelf of n books. Each book is represented by the book title — a string s_i numbered from 1 to n, each with length m. Andi really wants to sort the book lexicographically ascending, while Budi wants to sort it lexicographically descending.

Settling their fight, they decided to combine their idea and sort it asc-desc-endingly, where the odd-indexed characters will be compared ascendingly, and the even-indexed characters will be compared descendingly.

A string a occurs before a string b in asc-desc-ending order if and only if in the first position where a and b differ, the following holds:

  * if it is an odd position, the string a has a letter that appears earlier in the alphabet than the corresponding letter in b; 
  * if it is an even position, the string a has a letter that appears later in the alphabet than the corresponding letter in b. 

Input

The first line contains two integers n and m (1 ≤ n ⋅ m ≤ 10^6).

The i-th of the next n lines contains a string s_i consisting of m uppercase Latin letters — the book title. The strings are pairwise distinct.

Output

Output n integers — the indices of the strings after they are sorted asc-desc-endingly.

Example

Input


5 2
AA
AB
BB
BA
AZ


Output


5 2 1 3 4

Note

The following illustrates the first example.

<image>
=====


self-reflection on the problem:
============
- The problem involves sorting a list of book titles in a specific manner based on odd and even indices.
- Andi wants to sort the books lexicographically ascendingly, while Budi wants to sort them lexicographically descendingly.
- The combined sorting method involves comparing odd-indexed characters in ascending order and even-indexed characters in descending order.
- The input consists of the number of books, the length of each book title, and the book titles themselves.
- The output should be the indices of the book titles after sorting them using the specified method.
============


Here are also explanations for the problem test cases:
============
- input: |
    5 2
    AA
    AB
    BB
    BA
    AZ
  output: |
    5 2 1 3 4
  explanation: |
    In this example, we have 5 book titles with a length of 2 characters each.
    After sorting them asc-desc-endingly:
    - Comparing based on odd indices (1st character):
      - AZ (5th) comes before AA (1st).
      - AB (2nd) comes before BA (4th).
      - AA (1st) comes before BB (3rd).
      - BB (3rd) comes before BA (4th).
      - BA (4th) comes before AZ (5th).
    - Comparing based on even indices (2nd character):
      - AZ (5th) comes before AB (2nd).
      - AB (2nd) comes before AA (1st).
      - AA (1st) comes before BA (4th).
      - BA (4th) comes before BB (3rd).
      - BB (3rd) comes before AZ (5th).
    Therefore, the sorted indices are 5 2 1 3 4.
============


Your goal is to come up with possible solutions to the code contest problem.

Guidelines:
- Make sure each solution fully addresses the problem goals, constraints, examples, and notes.
- Each solution must have reasonable runtime and memory complexity - less than three seconds on a modern computer, given the problem constraints for large inputs.
- Double-check the solutions. Each possible solution must be able to generalize to additional test cases, not just the ones provided in the problem description.

The output must be a YAML object equivalent to type $ProblemSolutions, according to the following Pydantic definitions:
======
class Solution(BaseModel):
    name: str = Field(description="The name of the solution")
    content: str = Field(description="A description of the solution")
    why_it_works: str = Field(description="Shortly explain why this solution correctly solves the problem. Be specific and detailed regarding the problem rules and goals.")
    labels: List[str] = Field(description="A list of labels for the solution. For example (partial list): binary search, dynamic programming, trees, combinatorics, dfs, bfs, graphs, greedy, math, data structures, geometry, number theory, two pointers, simulation, direct approach, probabilities, ...")
    complexity: str = Field(description="The complexity of the solution")


class $ProblemSolutions(BaseModel):
    possible_solutions: List[Solution] = Field(max_items=3, description="A list of possible solutions to the problem. Make sure each solution fully addresses the problem rules and goals.")
======


Example YAML output:
```yaml
possible_solutions:
- name: |
    ...
  content: |
    ...
  why_it_works: |
    ...
  labels:
  - ...
  - ...
  complexity: |
    ...
 ```

Answer:
```yaml
2024-03-25 15:58:49.196 | DEBUG    | alpha_codium.llm.ai_handler:chat_completion:134 - response:
```yaml
possible_solutions:
- name: "Custom Sorting Function"
  content: |
    1. Define a custom sorting function that implements the specified sorting criteria.
    2. Use the custom sorting function to sort the book titles based on odd and even indices.
    3. Return the indices of the sorted book titles.
  why_it_works: |
    This solution works because it directly addresses the problem requirements by implementing a custom sorting function that compares odd-indexed characters in ascending order and even-indexed characters in descending order. By applying this custom sorting function, we can correctly sort the book titles as per the specified criteria.
  labels:
  - sorting
  - custom function
  complexity: "O(n * m * log(n))"

- name: "Multi-Key Sorting"
  content: |
    1. Create a list of tuples where each tuple contains the book title, its index, and a modified version of the title for sorting.
    2. Modify the title by separating odd and even characters and reversing the even characters.
    3. Sort the list of tuples based on the modified title.
    4. Extract and return the indices of the sorted book titles.
  why_it_works: |
    This solution works by utilizing multi-key sorting to handle the different comparison requirements for odd and even indices. By creating a modified version of the book titles for sorting, we can achieve the desired asc-desc-ending order effectively.
  labels:
  - sorting
  - multi-key
  complexity: "O(n * m * log(n))"

- name: "Counting Sort with Custom Comparator"
  content: |
    1. Implement a counting sort algorithm with a custom comparator function that compares odd and even characters differently.
    2. Use the custom comparator to sort the book titles based on the specified criteria.
    3. Return the indices of the sorted book titles.
  why_it_works: |
    This solution leverages counting sort with a custom comparator to efficiently sort the book titles according to the specified asc-desc-ending order. By utilizing a custom comparator, we can handle the unique comparison requirements for odd and even indices while maintaining a reasonable runtime complexity.
  labels:
  - sorting
  - counting sort
  complexity: "O(n * m)"
```
2024-03-25 15:58:49.196 | INFO     | alpha_codium.llm.ai_handler:chat_completion:135 - done
2024-03-25 15:58:49.196 | INFO     | alpha_codium.llm.ai_handler:chat_completion:136 - -----------------
2024-03-25 15:58:49.201 | INFO     | alpha_codium.gen.stages.run_choose_best_solution:run_choose_best_solution:15 - --choose best solution stage--
2024-03-25 15:58:49.207 | INFO     | alpha_codium.llm.ai_handler:chat_completion:88 - -----------------
2024-03-25 15:58:49.207 | INFO     | alpha_codium.llm.ai_handler:chat_completion:89 - Running inference ...
2024-03-25 15:58:49.207 | DEBUG    | alpha_codium.llm.ai_handler:chat_completion:90 - system:

2024-03-25 15:58:49.208 | DEBUG    | alpha_codium.llm.ai_handler:chat_completion:91 - user:
You are given a code contest problem, and a self-reflection on the problem:


problem description:
=======
Andi and Budi were given an assignment to tidy up their bookshelf of n books. Each book is represented by the book title — a string s_i numbered from 1 to n, each with length m. Andi really wants to sort the book lexicographically ascending, while Budi wants to sort it lexicographically descending.

Settling their fight, they decided to combine their idea and sort it asc-desc-endingly, where the odd-indexed characters will be compared ascendingly, and the even-indexed characters will be compared descendingly.

A string a occurs before a string b in asc-desc-ending order if and only if in the first position where a and b differ, the following holds:

  * if it is an odd position, the string a has a letter that appears earlier in the alphabet than the corresponding letter in b; 
  * if it is an even position, the string a has a letter that appears later in the alphabet than the corresponding letter in b. 

Input

The first line contains two integers n and m (1 ≤ n ⋅ m ≤ 10^6).

The i-th of the next n lines contains a string s_i consisting of m uppercase Latin letters — the book title. The strings are pairwise distinct.

Output

Output n integers — the indices of the strings after they are sorted asc-desc-endingly.

Example

Input


5 2
AA
AB
BB
BA
AZ


Output


5 2 1 3 4

Note

The following illustrates the first example.

<image>
=======


self-reflection on the problem:
=======
- The problem involves sorting a list of book titles in a specific manner based on odd and even indices.
- Andi wants to sort the books lexicographically ascendingly, while Budi wants to sort them lexicographically descendingly.
- The combined sorting method involves comparing odd-indexed characters in ascending order and even-indexed characters in descending order.
- The input consists of the number of books, the length of each book title, and the book titles themselves.
- The output should be the indices of the book titles after sorting them using the specified method.
=======


Here is a list of 3 possible solutions to the problem:
=======
- name: "Custom Sorting Function"
  content: |
    1. Define a custom sorting function that implements the specified sorting criteria.
    2. Use the custom sorting function to sort the book titles based on odd and even indices.
    3. Return the indices of the sorted book titles.
  why_it_works: |
    This solution works because it directly addresses the problem requirements by implementing a custom sorting function that compares odd-indexed characters in ascending order and even-indexed characters in descending order. By applying this custom sorting function, we can correctly sort the book titles as per the specified criteria.
  labels:
  - sorting
  - custom function
  complexity: "O(n * m * log(n))"

- name: "Multi-Key Sorting"
  content: |
    1. Create a list of tuples where each tuple contains the book title, its index, and a modified version of the title for sorting.
    2. Modify the title by separating odd and even characters and reversing the even characters.
    3. Sort the list of tuples based on the modified title.
    4. Extract and return the indices of the sorted book titles.
  why_it_works: |
    This solution works by utilizing multi-key sorting to handle the different comparison requirements for odd and even indices. By creating a modified version of the book titles for sorting, we can achieve the desired asc-desc-ending order effectively.
  labels:
  - sorting
  - multi-key
  complexity: "O(n * m * log(n))"

- name: "Counting Sort with Custom Comparator"
  content: |
    1. Implement a counting sort algorithm with a custom comparator function that compares odd and even characters differently.
    2. Use the custom comparator to sort the book titles based on the specified criteria.
    3. Return the indices of the sorted book titles.
  why_it_works: |
    This solution leverages counting sort with a custom comparator to efficiently sort the book titles according to the specified asc-desc-ending order. By utilizing a custom comparator, we can handle the unique comparison requirements for odd and even indices while maintaining a reasonable runtime complexity.
  labels:
  - sorting
  - counting sort
  complexity: "O(n * m)"
```
=======


Using the inputs above, your goal is to choose the best solution to the code contest problem.
Don't just pick the most efficient solution. The main consideration is that the solution can fully solve the problem in a simple and robust manner.
Make sure the chosen solution has a reasonable runtime - less than three seconds on a modern computer, given the problem constraints regarding large inputs.

The output must be a YAML object equivalent to type $ProblemSolution, according to the following Pydantic definitions:
=======
class Test(BaseModel):
    input: str
    output: str

class ProblemSolution(BaseModel):
    name: str = Field(description="The name of the best solution")
    content: str = Field(description="The content of the best solution")
    why: str = Field(description="Shortly explain why is this the best solution")
    flow: List[str] = Field(description="Describe of the flow of the solution, in bullet points")
    problem_tests: List[Test] = Field("List the input-output examples that are provided in the problem description.")
    input_output_examples_flow: List[str] = Field(description="Describe, in bullet points, how the proposed flow will lead to getting the expected output for the provided input examples")
=======


Example YAML output:
```yaml
name: |
  ...
content: |
  ...
why: |
  ...
flow:
- |
  ...
- |
  ...
...
problem_tests:
- input: |
    ...
  output: |
    ...
input_output_examples_flow:
- |
  ...
- |
  ...
```

Each YAML output MUST be after a newline, indented, with block scalar indicator ('|').

Answer:
```yaml