题目描述

给你 $n$ 个区间 $I_i = [l_i,r_i]$（$1 \le l_i \le r_i \le n$）。定义 $f(I_1,I_2,\cdots,I_n)$ 为，有多少个 $\{1,2,\cdots,n\}$ 的排列 $p$ 满足 $\forall 1 \le i \le n,l_i \le p_i \le r_i$，对 $\Large \color{red} 2$ 取模。

给定初始的 $I_{1,2,\cdots,n}$。接下来有 $q$ 次操作，每次给定三个参数 $(x,y,z)$，将第 $x$ 个区间 $I_{x}$ 改成 $[y,z]$，问 $f(I_1,\cdots,I_n)$ 的值。注意，操作的影响是持久的，也就是这次修改会被保留到后续操作。

输入格式

第一行两个正整数 $n$，$q$。

接下来 $n$ 行，每行两个整数 $l_i,r_i$，表示初始的区间。

接下来 $q$ 行，每行三个正整数 $x,y,z$，表示一次修改。

输出格式

共 $q$ 行，每行一个整数，表示第 $i$ 次修改之后 $f(I_1,I_2,\cdots,I_n)$ 的值。

输入样例 #1

3 3
1 1
2 3
3 3
2 1 1
3 1 3
1 2 2

输出样例 #1

0
0
1

输入样例 #2

5 4
1 1
1 5
3 5
4 4
2 3
3 1 5
4 3 3
3 5 5
2 2 2

输出样例 #2

0
0
1
0

说明提示

对于所有的数据，$1 \le n,q \le 2 \times 10^5$，$1 \le l_i \le r_i \le n$，$1 \le y \le z \le n$。

本站补充：原套别：第 13 套 C 题。