题目描述
有一个长度为 $n$ 的数列，数列中每个数都是 $[0,p-1]$ 之间的整数。
小明不知道数列中每个数的值，所以向小红做了 $m$ 次询问。
每次小明会向小红询问一个区间 $[l,r]$ 中所有数的和对 $p$ 取模的结果。
问完所有问题后，小明发现小红的回答中似乎存在矛盾。
现在小明想找到最大的 $X$，满足小红的前 $X$ 次回答中不存在矛盾( $X$有可能等于 $m$)。
输入
第一行三个整数 $n,m,p$ 表示数列长度 $n$，询问个数 $m$ 和模数 $p$。
之后 $m$ 行， 每行三个整数 $l,r,k$， 表示小红回答区间 $[l,r]$ 中所有数的和对 $p$ 取模结果为$k$ 。
输出
输出最大的 $X$，满足小红的前 $X$ 次回答中不存在矛盾。
样例输入输出
输入#1
复制
10 5 2
1 2 0
3 4 1
5 6 0
1 6 0
7 10 1
提示
对于 $30\%$ 的数据，$1 \leq n,m \leq 10$，$p=2$。
对于 $60\%$ 的数据，$1 \leq n,m \leq 10^3$，$2 \leq p \leq 10^3$。
对于另外 $30\%$ 的数据，$1 \leq n,m \leq 10^6$，$p=2$。
对于 $100\%$ 的数据，$1 \leq n,m \leq 10^6$，$2 \leq p \leq 10^9$。
$p$ 不一定为质数，建议使用读入优化。