Today, Marisa visited Alice at her house. Alice was busy assigning chores to her collection of n dolls, with n chores in total. She knows that if the ith doll perform the jth chore, the efficiency would be Ai,j. The efficiency of n dolls equal to the minimum efficiency among the dolls. A doll can be assigned at most 1 chore, and a chore can be assign at most 1 times.
However, Alice does not know the maximum efficiency possible. Therefore, she has asked Marisa for help, and Marisa is turning to you for assistance.
### Input
- The first line contains an integer n.
- The next n lines, the ith line contains n integers Ai,j.
### Output
- The first line print the maximum efficiency to complete n chores.
- The next n lines, the ith line is the chore to which doll i was assigned. If there are multiple ways to arrange chores, print any.
### Constraints
- 1≤n≤200.
- 1≤Ai,j≤109.
### Example
Input:
4944128781322836737
Output:
71234