Lexicographical Numbers

medium

1. You are given a number.
2. You have to print all the numbers from 1 to n in lexicographical order.

Note -&gt; Check out the question video and write the recursive code as it is intended without 
               changing signature. The judge can't force you but intends you to teach a concept.

Input Format

A number

Output Format

Check the sample output and question video

Constraints

1 &lt;= n &lt;= 50000

Notice

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

Example

Input

Output

Magnets

Josephus Problem