Background

Ancient handwriting, ancient music, ancient history, the ancient $K_{1000}$—if no one cares, it will quietly fade away.

Problem Description

You are given an undirected complete graph with $n$ nodes. You need to label each edge with a digit from $0 \sim 9$, such that there does not exist any 3-cycle or 5-cycle in the graph where all edges on the cycle have the same digit.

Input Format

The input contains only one line with an integer $n$, representing the number of nodes in the graph.

Output Format

If no solution exists, output one line with an integer -1. Otherwise, output $(n-1)$ lines. On line $i$, output $(n-i)$ characters. The $j$-th character on line $i$ represents the label of edge $(i,i+j)$. If there are multiple solutions, output any one.

4

012
34
5

Hint

Constraints

For all testdata, $2 \le n \le 1000$.

Source

From the final round of the 2023 Tsinghua University Student Algorithm and Programming Contest and Collegiate Invitational (THUPC2023).

Resources such as the editorial can be found at https://github.com/THUSAAC/THUPC2023.

Translated by ChatGPT 5