Humanity's Last Code Exam / 2023_B / Three Kinds of Dice

The Institute for Creative Product Combinations (ICPC) tries to find unusual and innovative ways to unite seemingly unrelated products or technologies, opening up new markets and creating new jobs. For instance, their most recent success was the “hairbachi,” a hair-dryer with a hibachi grill top attachment for preparing on-the-go hot meals. The company employs n teams of size 2 to research individual products, then members of the different teams get together to explore ways of combining products.

During the pandemic, the ICPC management organized everyone’s schedule in such a way that there were never more than n people in the office at the same time, and things ran so smoothly that they continued the process once things began to return to normal. Here is the scheme they used. Label the teams with integers 1 through n and the two people on the i-th team as (i,1) and (i,2) for each i from 1 to n. Each week, exactly one person from each team is allowed in the office, while the other has to stay away. The employees (i,1) and (i,2) know each other well and collaborate productively regardless of being isolated from each other, so members of the same team do not need to meet in person in the office. However, isolation between members from different teams is still a concern.

Each pair of teams i and j for i≠j has to collaborate occasionally. For a given number w of weeks and for fixed team members (i,a) and (j,b), let w₁<w₂<…<w_(k) be the weeks in which these two team members meet in the office. The isolation of those two people is the maximum of

{w₁,w₂−w₁,w₃−w₂,…,w_(k)−w_(k−1),w+1−w_(k)}

or infinity if those two people never meet. The isolation of the whole company is the maximum isolation across all choices of i,j,a, and b.

You have been tasked to find a weekly schedule that minimizes the isolation of the whole company over a given number w of weeks.

### Input

The input consists of a single line containing two integers n and w, where:

- 2≤n≤10⁴ is the number of teams.
- 1≤w≤52 is the number of weeks that need to be scheduled.

### Output

Output a line containing either:

- An integer representing the minimum isolation achievable for n teams, or
- The word "infinity" if no schedule guarantees that every pair of individuals on different teams can meet.

If the isolation is finite, it is followed by w lines representing a schedule that achieves this isolation. The j-th line of the schedule is a string of length n containing only the symbols 1 and 2, where the i-th symbol indicates which of the two members from team i comes into the office on week j.

### Sample Input and Output

#### Sample Input 1

The Institute for Creative Product Combinations (ICPC) tries to find unusual and innovative ways to unite seemingly unrelated products or technologies, opening up new markets and creating new jobs. For instance, their most recent success was the “hairbachi,” a hair-dryer with a hibachi grill top attachment for preparing on-the-go hot meals. The company employs \( n \) teams of size 2 to research individual products, then members of the different teams get together to explore ways of combining products.

During the pandemic, the ICPC management organized everyone’s schedule in such a way that there were never more than \( n \) people in the office at the same time, and things ran so smoothly that they continued the process once things began to return to normal. Here is the scheme they used. Label the teams with integers 1 through \( n \) and the two people on the \( i \)-th team as \((i, 1)\) and \((i, 2)\) for each \( i \) from 1 to \( n \). Each week, exactly one person from each team is allowed in the office, while the other has to stay away. The employees \((i, 1)\) and \((i, 2)\) know each other well and collaborate productively regardless of being isolated from each other, so members of the same team do not need to meet in person in the office. However, isolation between members from different teams is still a concern.

Each pair of teams \( i \) and \( j \) for \( i \neq j \) has to collaborate occasionally. For a given number \( w \) of weeks and for fixed team members \((i, a)\) and \((j, b)\), let \( w_1 < w_2 < \ldots < w_k \) be the weeks in which these two team members meet in the office. The isolation of those two people is the maximum of

\[
\{w_1, w_2 - w_1, w_3 - w_2, \ldots, w_k - w_{k-1}, w + 1 - w_k\}
\]

or infinity if those two people never meet. The isolation of the whole company is the maximum isolation across all choices of \( i, j, a, \) and \( b \).

You have been tasked to find a weekly schedule that minimizes the isolation of the whole company over a given number \( w \) of weeks.

### Input

The input consists of a single line containing two integers \( n \) and \( w \), where:

- \( 2 \leq n \leq 10^4 \) is the number of teams.
- \( 1 \leq w \leq 52 \) is the number of weeks that need to be scheduled.

### Output

Output a line containing either:

- An integer representing the minimum isolation achievable for \( n \) teams, or
- The word "infinity" if no schedule guarantees that every pair of individuals on different teams can meet.

If the isolation is finite, it is followed by \( w \) lines representing a schedule that achieves this isolation. The \( j \)-th line of the schedule is a string of length \( n \) containing only the symbols 1 and 2, where the \( i \)-th symbol indicates which of the two members from team \( i \) comes into the office on week \( j \).

### Sample Input and Output

#### Sample Input 1