题目背景

CCD 仍然喜欢异或，尤其喜欢在一个序列上玩游戏，但是由于 CCD 不够聪明，无法解出序列上的问题，这次他找到了你，寻求你的帮助。

题目描述

你需要构造一个长度为 $n$ 的 01 序列 $A$。

这个序列要满足 $m$ 个限制。每个限制都形如二元组 $(l,r)$，表示从 $A_l$ 到 $A_r$ 的异或和需要等于 $1$。

你需要输出满足所有限制的构造方案数对 $998244353$ 取模的结果，并构造方案中字典序最小的 $A$。

输入格式

第一行输入两个整数 $n,m$。

接下来 $m$ 行，每行输入两个整数 $l,r$，表示一个限制。

输出格式

第一行输出满足所有限制的构造方案数对 $998244353$ 取模的结果。

如果方案数不为 $0$，请在第二行输出一个 01 串，表示构造方案中字典序最小的 $A$。

5 0

32
00000

3 3
1 2
2 3
1 3

1
010

2 3
1 1
2 2
1 2

0

提示

本题采用捆绑测试。

$$\def\arraystretch{1.2} \begin{array}{|c|c|c|c|} \hline \begin{array}{c} \tt{subtask}\\\hline 1\\\hline 2\\\hline 3\\\hline 4\\\hline \end{array} & \begin{array}{c} n,m\\\hline \le 10^6\\\hline \le 20\\\hline \le 5\times10^3\\\hline \le 10^6\\\hline \end{array} & \begin{array}{c} \textrm{特殊性质}\\\hline m=0\\\hline \\ \textrm{无}\\ \\\hline \end{array} & \begin{array}{c} \tt{pts}\\\hline 5\\\hline 15\\\hline 30\\\hline 50\\\hline \end{array} \\\hline \end{array}$$

对于所有数据，$\forall 1\le i \le m,1 \le l_i \le r_i \le n$。