John 有 $$$Q$$$ 连续 $$$2K$$$ 位数字 $$$[l_i, r_i]$$$ 的闭区间,每个区间有一个 16 位值 $$$v_i$$$。 ($$$0 \leq i < Q$$$)
John 想要实现一个函数 F,将 $$$2K$$$ 位数字映射到 16 位数字,从而将每个区间的输入映射到该区间的值。换句话说: $$$$$$F(x) = v_i, \; \textrm{对于每一个 } 0 \leq i < Q \; \textrm{,以及每个 } x \in [l_i, r_i]$$$$$$ F 的输出对于其他输入并不重要。
John 希望快速实现 F,因此他决定使用查找表。单个 $$$2K$$$ 位查找表太大,无法放入内存,因此 John 计划使用两个 K 位查找表:LSBTable 和 MSBTable。他的实现如下所示: $$$$$$ F(x) = \textrm{LSBTable}[\textrm{lowKBits}(x)] \; \& \; \textrm{MSBTable}[\textrm{highKBits}(x)]$$$$$$ 换句话说,它返回在 LSBTable 中查找 K 个最低有效位和在 MSBTable 中查找 K 个最高有效位的结果的“按位与”。
约翰需要你的帮助。给定 $$$K$$$、$$$Q$$$ 和 $$$Q$$$ 间隔 $$$[l_i, r_i]$$$ 和值 $$$v_i$$$,找到任何两个可以实现 F 的查找表或报告此类表不存在。
输入
第一行包含两个整数 $$$K$$$ 和 $$$Q$$$ ($$$ 1 <= K <= 16$$$, $$$1 <= Q <= 2\cdot 10^5$$$)。
接下来的 $$$Q$$$ 行包含三个整数 $$$l_i$$$、$$$r_i$$$ 和 $$$v_i$$$。 ($$$0 \leq l_i \leq r_i < 2^{2K}$$$,$$$0 \leq v_i < 2^{16}$$$)。
输出
在第一行,如果存在满足条件的两个表,则输出“可能”(不带引号);如果不存在,则输出“不可能”(不带引号)。
如果存在解决方案,则在接下来的 $$$2 \cdot 2^K$$$ 行中,您的程序应输出它找到的两个查找表(LSBTable 和 MSBTable)的所有值。当有多对满足条件的表时,您的程序可能会输出任何这样的对。
在 $$$1 + i$$$ 行上输出 $$$\textrm{LSBTable}[i]$$$。 ($$$0 \leq i < 2^K$$$, $$$0 \leq \textrm{LSBTable}[i] < 2^{16}$$$)。
在 $$$1 + 2^K + i$$$ 行上输出 $$$\textrm{MSBTable}[i]$$$。 ($$$0 \leq i < 2^K$$$, $$$0 \leq \textrm{MSBTable}[i] < 2^{16}$$$)。
示例
输入 #1
1 2 0 2 1 3 3 3
输出 #1
possible 1 3 1 3
输入 #2
2 4 4 5 3 6 7 2 0 3 0 12 13 1
输出 #2
possible 3 3 2 2 0 3 0 1
输入 #3
2 3 4 4 3 5 6 2 12 14 1
输出 #3
impossible
注意
闭区间 $$$[a, b]$$$ 包括 a 和 b。
在第一个示例中,表 $$$\textrm{LSBTable} = [1,3]$$$ 和 $$$\textrm{MSBTable} = [1,3]$$$ 满足条件: $$$F[0] = \textrm{LSBTable}[0] \& \textrm{MSBTable}[0] = 1 \& 1 = 1$$$, $$$F[1] = \textrm{LSBTable}[1] \& \textrm{MSBTable}[0] = 3 \& 1 = 1$$$, $$$F[2] = \textrm{LSBTable}[0] \& \textrm{MSBTable}[1] = 1 \& 3 = 1$$$, $$$F[3] = \textrm{LSBTable}[1] \& \textrm{MSBTable}[1] = 3 \& 3 = 3$$$。
在第二个示例中,表 $$$\textrm{LSBTable} = [3,3,2,2]$$$ 和 $$$\textrm{MSBTable} = [0,3,0,1]$$$ 满足所有条件。
在第三个示例中,没有两个查找表可以满足条件。