← 返回题目列表

Codeforces · 119/C

C. 教育改革

中文机器翻译题面 查看原题

最近,柏林又进行了一项教育制度改革。其创新点如下:

现在一学年由 n 天组成。学生每天只学习 m 门科目中的一门,而且每门科目的学习时间不超过一天。第 i 个科目的课程结束后,学生将获得包含不少于 ai 且不多于 bi 练习的家庭作业。此外,每个主题都有一个特殊的属性,即复杂性(ci)。学校可以在满足以下条件的情况下制定自己的时间表:

- 时间表应包含按照复杂性严格增加的顺序排列的主题;
- 每天,除了第一天,任务应该包含比前一天多 k 倍的练习,或者比前一天多 k 的练习(更正式地说:让我们将第 i 天的家庭任务练习数量称为 xi,然后对于每个 i (1 < i ≤ n): xi = k + xi - 1 或xi = k·xi - 1 必须为真);
- 所有家庭任务中的练习总数应尽可能多。

所有限制均针对每所学校单独设置。

事实证明,在很多情况下,ai 和 bi 达到 1016(但是,由于伯兰州教育部长以爱半途而废而闻名,bi - ai 的值不会超过 100)。 Berland 256 学校也发生过这种情况。不过,你作为学校的校长,还得制定下一学年的时间表……

输入

第一行包含三个整数n、m、k(1≤n≤m≤50、1≤k≤100),分别代表一学年的天数、科目数和k参数。以下 m 行中的每一行都包含对主题的描述,作为三个整数 ai、bi、ci (1 ≤ ai ≤ bi ≤ 1016, bi - ai ≤ 100, 1 ≤ ci ≤ 100) — 相应地,对第 i 个主题的练习数量和第 i 个主题的复杂性进行了两个限制。不同的主题可以具有相同的复杂性。主题用 1 到 m 的整数编号。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位数字。最好使用 cin 流或 %I64d 指定器。

输出

如果不存在有效的解决方案,则打印单个单词“NO”(不带引号)。否则,第一行应包含单词“YES”(不带引号),接下来的 n 行应包含满足所有条件的任何时间表。第 i + 1 行应包含两个正整数:第 i 天要学习的科目编号和该科目的家庭作业练习数量。时间表应恰好包含 n 个科目。

示例

输入 #1

4 5 2
1 10 1
1 10 2
1 10 3
1 20 4
1 100 5

输出 #1

YES
2 8
3 10
4 20
5 40

输入 #2

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

输出 #2

NO