Problem Background

Translated from Izborne Pripreme 2022 (Croatian IOI/CEOI Team Selection) D1T2. $\texttt{2s,0.5G}$.

SPJ link.

Problem Description

Circle wrote down non-negative integers $N, K, L$, and asked Flame to construct two binary sequences $S$ and $T$, satisfying:

• The lengths of $S$ and $T$ are both $N$;
• $S$ contains exactly $K$ ones, and $T$ contains exactly $L$ ones;
• $f(S, T)$ is the smallest among all possible $f(S, T)$.

The function $f(S, T)$ is defined as the maximum value of $\sum_{i=1}^{N} S_i \operatorname{and} T_i$ after any cyclic shift of $S$ and $T$, where $\operatorname{and}$ denotes the bitwise AND operation.

Please help Flame construct $S$ and $T$.

Input Format

A single line containing three integers $N, K, L$.

Output Format

The first line contains an integer $F$, representing the minimum value of $f(S, T)$;

The next two lines describe the sequences $S$ and $T$ respectively. Adjacent elements do not need to be separated by spaces.

If there are multiple solutions, any one of them is acceptable.

Sample Input and Output

Sample Input #1

6 4 3

Sample Output #1

2
011011
101010

Sample Input #2

5 2 0

Sample Output #2

0
01001
00000

Sample Input #3

10 7 6

Sample Output #3

5
1101100111
1110001101

Notes/Hints

For $100\%$ of the data, it is guaranteed that $1 \le N \le 5 \times 10^5$, and $0 \le K, L \le N$.

Scoring Method

If you answer $F$ correctly, you can get $20\%$ of the score;

On this basis, if your $S$ and $T$ meet the conditions, you will receive the remaining $80\%$ of the score.

If you only plan to answer the first question, you should also output two binary sequences that meet conditions 1 and 2, otherwise, the score is not guaranteed.

见题面 Input 部分

见题面 Output 部分