F-Alice, Bob and Play Game_牛客挑战赛50

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

牛牛的英文名叫 ${Alice}$ ，牛妹的英文名叫 ${Bob}$ ， ${Alice}$ 和 ${Bob}$ 故事从下面展开：

黑板上有个 ${n}$ 整数 ${a_1,a_2,...,a_n}$ ，初始时 ${\forall i\in[1,n],a_i=1}$ 。

${Alice}$ 和 ${Bob}$ 进行 ${q}$ 轮游戏，第 ${i}$ 轮游戏流程如下：
${Alice}$ 选择两个不同的整数 ${s,t}$ ，并令 ${x=a_{s}\oplus a_{t},y=a_{s}\& a_{t}}$ 。
${Bob}$ 做以下操作之一：
0.令 ${a_s=x,a_t=y}$
1.令 ${a_t=x,a_s=y}$

令 ${f_i}$ 为进行了 ${i}$ 轮游戏后 ${\sum\limits_{j=1}^na_j}$ 的值。
令序列 ${F=\{f_1,f_2,...,f_q\}}$ 。
${Alice}$ 想让 ${F}$ 的字典序尽可能的小， ${Bob}$ 想让 ${F}$ 的字典序尽可能的大。

${Bob}$ 很快意识到这是一个不公平的游戏，因为只要 ${Alice}$ 足够聪明，一定会有 ${f_i=max(1,n-i)}$ 。于是 ${Bob}$ 启用了时之魔法，预测了 ${Alice}$ 在每轮会选择的整数对。

但是 ${Bob}$ 很快又意识到，只要 ${Alice}$ 足够聪明， ${Alice}$ 的操作策略会根据 ${Bob}$ 操作的策略发生改变，仍然会有 ${f_i=max(1,n-i)}$ 。这将可能导致 ${Alice}$ 每轮选择的整数对和 ${Bob}$ 预测的整数对不一样。而 ${Bob}$ 的预测是不可以失效的，因为一旦 ${Bob}$ 的预测失效，时空将会发生扭曲，这会造成非常严重的后果。因此， ${Bob}$ 又使用了馄饨赤光魔法使得 ${Alice}$ 在进行 ${q}$ 轮游戏时智商下降。

确切地说， ${Bob}$ 知道 ${Alice}$ 在第 ${i}$ 轮游戏一定会选择整数对 ${s_i,t_i}$ 。

且Bob需要保证如下条件：

在第 ${i-1(0\le i<q)}$ 轮游戏结束后，满足 ${a_{s_i}+a_{t_i}\ge 1}$ 。

${Bob}$ 想知道在他保证条件的基础上字典序最大的 ${F}$ 序列是什么样子，此外，他还想知道他的操作序列。

输入描述:

第一行两个整数。
接下来行每行两个整数。

输出描述:

第一行个整数。
第二行一个长度为的串，表示第轮游戏进行的操作。
有多种合法的操作序列只需要输出任意一种即可。

示例1

输入

复制

输出

复制

5 4 4 4 4
00100

题目描述

输入描述:

输出描述:

输入

输出

备注: