P10256 高仿的 Migos

经过刻苦的训练，ZHY 终于成为了一名说唱歌手。但这天，说唱歌手 ZHY 看到了同行说唱组合 Migos 的作品，立刻意识到了自己的差距，于是他要学习 Migos 的说唱技巧，复刻 Migos 的成功。 经过数个日夜的研究，ZHY 最终挑选出了 $n$ 部 Migos 的说唱作品，依次编号为 $1,2,\dots,n$。他认为只要学习完这 $n$ 部作品，就可以成为更加优秀的说唱歌手。于是，他会从第 $1$ 部作品，按编号从小到大的顺序依次进行学习，学习完第 $n$ 部作品就结束学习。 不过，说唱歌手 ZHY 的学习方式很特殊。对于每部作品，他只会听 $1$ 分钟。这种学习方式的问题是，对于第 $i$ 部作品，他在投入 $1$ 分钟后，有可能学习成功，也有可能会失败，具体地，如果 ZHY 学习的是作品 $i$，那么在他花一分钟的时间进行学习后： - 有 $P_i$ 的概率，ZHY 学习成功了，那么他会接着去学习作品 $i+1$（当然如果 $i=n$ 就直接结束学习）。 - 有 $1-P_i$ 的概率，ZHY 学习失败了。不幸的是，ZHY 脑内的记忆还会因此产生混乱，导致他只会记住前 $x_i$ 部作品，即他必须从第 $x_i+1$ 部作品开始重新学习。 ZHY 在尝试了几次学习后，深受记忆混乱的困扰，于是向脑科学专家 YHZ 求助。经过脑科学专家 YHZ 的研究，他发现所有的 $x_i$ 有一定的规律。具体地，他发现有 $m$ 对自然数 $(l_i,r_i)$, 其中 $i=1,2\dots,m$，满足 $0\leq l_i

无

无

**本题使用捆绑测试。** | Subtask 编号 | $n$ | $m$ | $k$ | 特殊性质 |分值 | | :-----: | :-----: | :-----: | :-----: | :-----: | :-----: | | $0$ | $\le 300$ | $\le 300$ | $\le 300$ | 无 | $11$ | | $1$ | $\le 3000$ | $\le 3000$ | $\le 3000$ | 无 | $4$ | | $2$ | $\le 10^5$ | $\le 10^5$ | $\le 1$ | B | $5$ | | $3$ | $\le 10^5$ | $\le 10^5$ | $\le 1$ | 无 | $14$ | | $4$ | $\le 10^5$ | $=0$ | $\le 10^5$ | 无 | $19$ | | $5$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | A | $19$ | | $6$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | B | $8$ | | $7$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | C | $10$ | | $8$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | 无 | $10$ | 以下的“区间”均指 $[l_i,r_i]$。 特殊性质 A：保证对于 $\forall i \in [1,m]$，$r_i-l_i+1\le 5$。 特殊性质 B：保证这些区间两两的交 $\le 1$。即对于 $\forall i,j \in [1,m]$ 且 $i\ne j$，有 $r_i\le l_j$ 或 $r_j\le l_i$。 特殊性质 C：保证这些区间不存在包含关系。即对于 $\forall i,j \in [1,m]$ 且 $i\ne j$，有 $l_i>l_j$ 或 $r_i