CF1423I.Lookup Tables

John has $Q$ closed intervals of consecutive $2K$-bit numbers $[l_i, r_i]$ and one 16-bit value $v_i$ for each interval. ($0 \leq i \lt Q$)

John wants to implement a function F that maps $2K$-bit numbers to 16-bit numbers in such a way that inputs from each interval are mapped to that interval's value. In other words: $$F(x) = v_i, \; \textrm{for every } 0 \leq i \lt Q \; \textrm{, and every } x \in [l_i, r_i]$$ The output of F for other inputs is unimportant.

John wants to make his implementation of F fast so he has decided to use lookup tables. A single $2K$-bit lookup table would be too large to fit in memory, so instead John plans to use two K-bit lookup tables, LSBTable and MSBTable. His implementation will look like this: $$ F(x) = \textrm{LSBTable}[\textrm{lowKBits}(x)] \; \& \; \textrm{MSBTable}[\textrm{highKBits}(x)]$$ In other words it returns the "bitwise and" of results of looking up the K least significant bits in LSBTable and the K most significant bits in MSBTable.

John needs your help. Given $K$, $Q$ and $Q$ intervals $[l_i, r_i]$ and values $v_i$, find any two lookup tables which can implement F or report that such tables don't exist.

约翰有 $Q$ 个闭区间 $[l_i, r_i]$，每个区间由连续的 $2K$ 位整数构成，并为每个区间配有一个 16 位值 $v_i$（其中 $0 \leq i < Q$）。

约翰希望实现一个函数 $F$，该函数将 $2K$ 位整数映射为 16 位整数，使得每个区间内的所有输入均被映射到对应区间的值 $v_i$。换言之：

F(x) = v\_i, \; \textrm{对每个 } 0 \leq i < Q \; \textrm{及每个 } x \in \[l\_i, r\_i\]

对于其他输入，$F$ 的输出值无关紧要。

为使 $F$ 的实现尽可能高效，约翰决定采用查表法（lookup tables）。但单个 $2K$ 位的查找表过大，无法装入内存；因此他计划使用两个 $K$ 位查找表：LSBTable 和 MSBTable。其实现方式如下：

F(x) = \textrm{LSBTable}\[\textrm{lowKBits}(x)\] \; \& \; \textrm{MSBTable}\[\textrm{highKBits}(x)\]

即：先提取 $x$ 的最低 $K$ 位（记为 $\textrm{lowKBits}(x)$）并在 LSBTable 中查表，再提取 $x$ 的最高 $K$ 位（记为 $\textrm{highKBits}(x)$）并在 MSBTable 中查表，最后对两个查表结果执行按位与（bitwise AND）操作并返回结果。

约翰需要你的帮助：给定 $K$、$Q$，以及 $Q$ 个区间 $[l_i, r_i]$ 和对应值 $v_i$，请找出任意一对满足要求的查找表 LSBTable 和 MSBTable；若不存在这样的查找表，则报告无解。

The first line contains two integers $K$ and $Q$ ($ 1 \lt = K \lt = 16$, $1 \lt = Q \lt = 2\cdot 10^5$).

Each of the next $Q$ lines contains three integers $l_i$, $r_i$ and $v_i$. ( $0 \leq l_i \leq r_i \lt 2^{2K}$, $0 \leq v_i \lt 2^{16}$).

第一行包含两个整数 $K$ 和 $Q$（$ 1 \leq K \leq 16$，$1 \leq Q \leq 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}$）。

On the first line output "possible" (without quotes) if two tables satisfying the conditions exist, or "impossible" (without quotes) if they don't exist.

If a solution exists, in the next $2 \cdot 2^K$ lines your program should output all values of the two lookup tables (LSBTable and MSBTable) it found. When there are multiple pairs of tables satisfying the conditions, your program may output any such pair.

On lines $1 + i$ output $\textrm{LSBTable}[i]$. ($0 \leq i \lt 2^K$, $0 \leq \textrm{LSBTable}[i] \lt 2^{16}$).

On lines $1 + 2^K + i$ output $\textrm{MSBTable}[i]$. ($0 \leq i \lt 2^K$, $0 \leq \textrm{MSBTable}[i] \lt 2^{16}$).

第一行输出“possible”（不带引号），表示存在满足条件的两张查找表；若不存在，则输出“impossible”（不带引号）。

若解存在，则在接下来的 $2 \cdot 2^K$ 行中，你的程序应输出所找到的两张查找表（LSBTable 和 MSBTable）的所有值。当存在多对满足条件的表格时，你的程序可输出其中任意一对。

第 $1 + i$ 行输出 $\textrm{LSBTable}[i]$。（$0 \leq i \lt 2^K$，且 $0 \leq \textrm{LSBTable}[i] \lt 2^{16}$）

第 $1 + 2^K + i$ 行输出 $\textrm{MSBTable}[i]$。（$0 \leq i \lt 2^K$，且 $0 \leq \textrm{MSBTable}[i] \lt 2^{16}$）

A closed interval $[a, b]$ includes both a and b.

In the first sample, tables $\textrm{LSBTable} = [1,3]$ and $\textrm{MSBTable} = [1,3]$ satisfy the conditions: $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$.

In the second sample, tables $\textrm{LSBTable} = [3,3,2,2]$ and $\textrm{MSBTable} = [0,3,0,1]$ satisfy all the conditions.

In the third sample there are no two lookup tables which can satisfy the conditions.

闭区间 $[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]$ 满足所有条件。

在第三个样例中，不存在两个查找表能够满足条件。