QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100
[+2]
Statistics

题目描述

寒冬将至,FIS滑雪世界杯正在火热进行,选手们将参加本赛季中的举办的若干场比赛,以获取积分获得奥运会资格。作为滑雪比赛的忠实观众,小 Z 自然不打算错过任何一场比赛。

在小 Z 的世界中,世界杯的赛制与现实有较大的不同:本赛季共有 m 个比赛日,将依次举行 m 场比赛,有 n 名选手参加,第 i 名选手在之前的赛季中已经有了 wi 的积分,由于身体原因,会在第 li 个比赛日抵达比赛现场,第 ri 个比赛日离开,参加第 liri 场比赛。每场比赛如果有至少一人参加,就会在这些选手间进行竞争,选出唯一的胜者,胜者将获得 1 点积分。

特别地,为了保证公平,不让一些选手参与过多的比赛,对于任意两名选手 i,j,如果 ij 先抵达现场,则不能比 j 更晚离开。即 1i,jnli<ljrirj

不幸的是,小 Z 最喜欢的一名选手 UFT 由于身体原因将缺席本赛季所有的比赛(UFT 不算在那 n 名选手中,可以看作共有 n+1 名选手进行排名),小 Z 想知道 UFT 还有没有出线晋级奥运会的理论可能。UFT 在以往的赛季中获得了积分 v,由于不确定奥运会名额的数量,小 Z 想向你询问本赛季结束后所有的不同积分情况中,UFT 的排名最高为多少(定义一名选手的排名为分数比他高的选手数量 +1),设这个最小值为 mn,你需要输出 n+1mn 的大小(即分数不高于 v 的选手数量)。由于积分相同需要考虑选手历史战绩,所以小 Z 还想要额外知道:所以可以达到的,满足 UFT 排名为 mn 的不同最终积分情况中,积分不高于 UFT 的选手集合有多少种不同的可能。答案关于 109+7 取模。

输入格式

第一行四个整数 n,m,v,tpn,m,v 参见题目描述, tp 为询问类型满足 tp{0,1},当 tp=0 时你只需要输出第一问答案,tp=1 时则需要输出两问的答案。

接下来 n 行,第 i 行三个正整数 wi,li,ri

输出格式

一行一个或两个整数表示答案,答案之间用空格隔开。

样例数据

input

7 7 2 1
1 1 1
1 2 3
2 3 4
1 4 4
2 4 5
1 5 6
2 5 7

output

5 2

样例解释

可能 1:比赛胜者依次为 1,2,3,3,7,7,7,选手 1,2,4,5,6 分数 2

可能 2:比赛胜者依次为 1,2,2,4,7,7,7,选手 1,3,4,5,6 分数 2

数据规模与约定

对于所有测试数据,有 1n,m2×105,0wi,v1×109,1lirim,0tp1。 且 1i,jn,ij,若 li<ljrirj

subtask 1(5%): n,m8

subtask 2(5%): n,m15

subtask 3(20%): n,m20

subtask 4(10%): n,m2000,tp=0

subtask 5(20%): tp=0

subtask 6(20%): n,m2000

subtask 7(20%): 无特殊限制。

时间限制:1s

空间限制:256MB