神犇用自己高深的编程技术实现了一个具有独立思维的人工智能，但这个人工智能学会了说谎。首先，神犇给出一个范围[1,n]，人工智能会在该范围内生成一个整数k，而后人工智能会给神犇m条描述，每条描述为一下三种之一：

1、1 x y：表示x \le k \le y；

2、2 x：表示x \le k \le n；

3、3 x：表示1 \le k \le x；

神犇调试后发现人工智能仅会在描述中对x,y的值说谎，现在他想纠正这个坏毛病，所以他首先要知道m条描述中最多有多少条是错误的，此时k可以有多少种取值？从而给人工智能增加一个随动阈值使得它不会轻易说谎。

第一行，两个整数，分别为n,m。

接下来m行，每行表示一个描述，其格式如题所述。

对于100%的数据：

1\le n \le 10^6；

1\le x \le y \le n；

1\le m \le 2×10^5。

共一行有由单个空格分隔的两个整数，分别表示最多有多少条错误描述、此时k有多少种取值。

注意：若指令全部正确，则题目应理解为错误指令最多0条，使得指令错误数达到0的k值有多少种？