Description

定义全集 $U=\left\{x\in\mathbb{N^+}~|~x \leq n\right\}$。

有一个由 $m$ 个集合组成的序列 $S$。方便起见，我们称第 $i$ 个集合为 $S_i$。对于每一个集合 $S_i$，使用 $k_i$ 个区间 $\left[ l_{i,j}, r_{i,j} \right]$ 描述。具体地，$S_i = U \cap \left( \displaystyle\bigcup_{j=1}^{k_i} \left[ l_{i,j}, r_{i,j} \right] \right)$。

现你可以进行操作任意次，每次可以选择任意一个操作进行：

• 选择两个集合 $S_i,S_j$，将两者的并 $S_i \cup S_j$ 添加到序列末尾；
• 选择两个集合 $S_i,S_j$，将两者的交 $S_i \cap S_j$ 添加到序列末尾；
• 选择两个集合 $S_i,S_j$，将两者的对称差^[1] $S_i \oplus S_j$ 添加到序列末尾；
• 选择一个集合 $S_i$，将其补集 $\complement_U S_i$ 添加到序列末尾。

请你回答：你一共可以得到多少种元素个数为 $1$ 的集合？

Constraints and Subtasks

对于全部测试点，满足：

• $1 \leq n \leq 2\times10^6$
• $1 \leq m \leq 3\times10^6$
• $k_i \geq 0$
• $\displaystyle \sum_{i=1}^m k_i \leq 5\times10^6$
• $1 \leq l_{i,1} < r_{i,1} < l_{i,2} < r_{i,2} < \dots < l_{i,k_i} < r_{i,k_i} \leq n$
• 所有输入数字均为整数。

另外，还有一些测试点满足特殊要求。

Input

输入内容从标准输入中给出，格式如下：

$ \boxed{\begin{aligned} & n {\quad} m \\ & k_1 {\quad} l_{1,1} {\quad} r_{1,1} {\quad} l_{1,2} {\quad} r_{1,2} {\quad} \dots {\quad} l_{1,k_1} {\quad} r_{1,k_1} \\ & k_2 {\quad} l_{2,1} {\quad} r_{2,1} {\quad} l_{2,2} {\quad} r_{2,2} {\quad} \dots {\quad} l_{2,k_1} {\quad} r_{2,k_1} \\ & ~ \vdots \\ & k_m {\quad} l_{m,1} {\quad} r_{m,1} {\quad} l_{m,2} {\quad} r_{m,2} {\quad} \dots {\quad} l_{m,k_1} {\quad} r_{m,k_1} \end{aligned}} $

Output

输出一行，包含一个整数，表示问题的答案。

Samples

3 2
1 1 3
1 1 2

1