Description

Madeline comes to a shrine. It is covered in dust, and it is surrounded by strange symbols whose meaning is unclear.

With Madeline’s strong observation skills, she discovers that these symbols actually correspond to dash sequences. Dashing in a certain order is like entering a password. Only by entering a specific password can she light up the shrine and obtain the Crystal Heart.

Many years later, when Madeline recalls her climbing journey, she no longer remembers what the password was. She only remembers that the password length is $3$, and each position of the password has $n$ possible values. She also knows that for the password she enters, as long as any two positions match the standard password, she can light up the shrine and obtain the Crystal Heart.

Today, Madeline returns to the shrine again. She wants to use the minimum number of password attempts to guarantee that she can obtain the Crystal Heart. Can you help her?

Input Format

The first line contains an integer $n$, indicating how many possible values there are for each position of the password.

Output Format

The first line outputs an integer $k$, indicating the number of password attempts in your plan.

The next $k$ lines output the password for each attempt.

2

8
1 1 1
1 1 2
1 2 1
1 2 2
2 1 1
2 1 2
2 2 1
2 2 2

Hint

The sample is not an optimal solution; it is only an example of the output.

You must output a plan, otherwise you may encounter unknown errors.

There are three test points:

• Test point $1$ ($10$ pts): $n=2$.
• Test point $2$ ($20$ pts): $n=100$.
• Test point $3$ ($70$ pts): $n=1000$.

For each dataset, we use the following scoring method:

• If $k > 5000000$, your output is too large, and you will not get any score.

• Otherwise:

  • If the plan you provide cannot guarantee lighting up the shrine, or the plan itself is incorrect, then it is scored as follows:

    • If $k$ is less than the minimum number of attempts, you get $0$ points.

    • Otherwise, if $k$ equals the minimum number of attempts, you get $10\%$ of the score for this test point.

    • Otherwise, if your $k$ is $q$ times the minimum number of attempts, you will get $\frac{1}{10*q}$ of the score for this test point.

  • Otherwise, if your plan can guarantee lighting up the shrine, it is scored as follows:

    • First, you get a base score of $10\%$.

    • Then, let the minimum number of attempts be $p$. You will get the following additional score:

      • If $k=p$, you will get an additional $90\%$.

      • If $p<k<=1.5p$, you will get an additional $50+\frac{1.5p-k}{0.5p}*40\%$.

      • If $1.5p<k<=2p$, you will get an additional $20+\frac{2p-k}{0.5p}*30\%$.

      • If $k>2p$, you will not get any additional score.

Input Format

The first line contains an integer $n$, indicating how many possible values there are for each position of the password.

Output Format

The first line outputs an integer $k$, indicating the number of password attempts in your plan.

The next $k$ lines output the password for each attempt.

Hint

The sample is not an optimal solution; it is only an example of the output.

You must output a plan, otherwise you may encounter unknown errors.

There are three test points:

• Test point $1$ ($10$ pts): $n=2$.
• Test point $2$ ($20$ pts): $n=100$.
• Test point $3$ ($70$ pts): $n=1000$.

For each dataset, we use the following scoring method:

• If $k > 5000000$, your output is too large, and you will not get any score.

• Otherwise:

  • If the plan you provide cannot guarantee lighting up the shrine, or the plan itself is incorrect, then it is scored as follows:

    • If $k$ is less than the minimum number of attempts, you get $0$ points.

    • Otherwise, if $k$ equals the minimum number of attempts, you get $10\%$ of the score for this test point.

    • Otherwise, if your $k$ is $q$ times the minimum number of attempts, you will get $\frac{1}{10*q}$ of the score for this test point.

  • Otherwise, if your plan can guarantee lighting up the shrine, it is scored as follows:

    • First, you get a base score of $10\%$.

    • Then, let the minimum number of attempts be $p$. You will get the following additional score:

      • If $k=p$, you will get an additional $90\%$.

      • If $p<k<=1.5p$, you will get an additional $50+\frac{1.5p-k}{0.5p}*40\%$.

      • If $1.5p<k<=2p$, you will get an additional $20+\frac{2p-k}{0.5p}*30\%$.

      • If $k>2p$, you will not get any additional score.

Translated by ChatGPT 5