Minimizing Isolation in ICPC Team Office Schedules

The Institute for Creative Product Combinations (ICPC) is organizing a weekly schedule for n teams (each with 2 members) so that in each of w weeks exactly one member per team is in the office. Although team members within the same team can collaborate remotely, every pair of employees from different teams must eventually meet in person. For any fixed pair of teams i and j (i ≠ j) and fixed members from each team (denoted as (i, a) and (j, b), where a, b ∈ {1,2}), let the weeks in which they both are in the office be

\[ w_1, w_2, \ldots, w_k \quad (1 \le w_1 < w_2 < \cdots < w_k \le w)\]

The isolation between these two people is defined as \[ \max\{w_1,\,w_2-w_1,\,w_3-w_2,\,\ldots,\,w_k-w_{k-1},\,w+1-w_k\}\]

(with the convention that if they never meet, the isolation is infinity). The isolation of the whole company is the maximum isolation over all choices of teams and members. Your task is to produce a weekly schedule (i.e. assign each team which member goes to the office each week) that minimizes the isolation of the whole company.

Note: To ensure that every ordered pair (a, b) with a, b ∈ {1, 2} for any two distinct teams appears at least once in the schedule, the schedule must be designed so that for every pair of teams:

• There is at least one week when both send member 1 (i.e. meeting (1,1)).
• There is at least one week when both send member 2 (i.e. meeting (2,2)).
• There is at least one week when the first sends 1 and the second sends 2 (i.e. meeting (1,2)).
• There is at least one week when the first sends 2 and the second sends 1 (i.e. meeting (2,1)).

It can be shown that one way to guarantee these conditions is to assign to each team a binary schedule of length 2*(L+1), where L = \lceil log_2(n) \rceil, constructed as follows:

1. For each team i (1 ≤ i ≤ n), consider the binary representation of i-1 using exactly L bits. Prepend a '1' to this binary string to obtain a bit string of length L+1. (This extra bit ensures that no two teams are complete complements.)
2. For each bit in the string (say the k-th bit):
   • If the bit is 1, then assign '1' in week 2k-1 and '2' in week 2k.
   • If the bit is 0, then assign '2' in week 2k-1 and '1' in week 2k.
3. If w is larger than 2*(L+1), repeat the block periodically and truncate to w weeks.

The overall schedule is expressed in w lines (weeks), each containing a string of length n where the j-th character indicates which member of team j goes to the office that week ('1' or '2').

inputFormat

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

• n (n ≥ 2) is the number of teams.
• w (w ≥ 1) is the number of weeks.

You may assume that w is sufficiently large to allow a schedule that meets the meeting requirements.

outputFormat

Output exactly w lines. The i-th line (1-indexed) should be a string of length n. The j-th character of this string is either '1' or '2', indicating which member of team j is scheduled to be in the office during week i.

sample

2 4

12
21
21
12