← 返回题目列表

Codeforces · 585/A

A. 牙医根纳迪

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

根纳迪是伯兰最好的儿童牙医之一。今天有n个孩子跟他预约了,他们在他的办公室门口排队。

所有孩子都喜欢在牙医接待处大声哭泣。我们按照子元素在行中的排列顺序枚举从 1 到 n 的整数。每个孩子都与他的置信度 pi 的值相关联。孩子们轮流来到办公室;每次都是排在第一位的孩子去看医生。

当根纳迪治疗第 i 个孩子的牙齿时,孩子正在以 vi 的音量哭泣。此时,队列中第一个孩子的置信度会减少 vi 的量,第二个孩子的置信度会减少 vi - 1 的值,依此类推。排在第六个孩子后面的孩子几乎听不到哭声,所以他们的信心没有改变。

如果在任何时间点,第 j 个孩子的置信度小于零,他就会开始用 dj 的音量哭泣,然后离开队伍,跑向出口,而不去医生办公室。此时,队列中第 j 个孩子之后的所有孩子的置信度都会减少 dj 的量。

所有这些事件按某种顺序一个接一个地发生。一些哭声可能会引发其他哭声,从而引发连锁反应。走廊里一片安静,排在第一位的孩子走进了医生的办公室。

帮助牙医根纳迪确定他将治愈哪些孩子的牙齿。按时间顺序打印出他们的编号。

输入

输入的第一行包含一个正整数 n (1 ≤ n ≤ 4000) — 该行中孩子的数量。

接下来的 n 行包含三个整数,每个 vi、di、pi (1 ≤ vi, di, pi ≤ 106) — 医生办公室中的哭声音量、大厅中的哭声音量以及第 i 个孩子的信心。

输出

在第一行打印数字 k — 根纳迪将治愈牙齿的儿童数量。

在第二行中打印 k 个整数 — 按升序排列到达行尾的孩子的数量。

示例

输入 #1

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

输出 #1

2
1 3

输入 #2

5
4 5 1
5 3 9
4 1 2
2 1 8
4 1 9

输出 #2

4
1 2 4 5

注意

在第一个示例中,Gennady 首先处理第一个会以音量 4 哭泣的孩子的牙齿。其余孩子的置信度将分别等于 - 2、1、3、1。于是,老二也听到1的音量哭了,跑向出口。剩下的孩子的置信度将等于0、2、0。然后第三个孩子会去办公室,用5号的声音哭。其他孩子不忍心,大声哭着跑向出口。

在第二个样本中,第一个孩子首先进入办公室,他会以音量 4 哭泣。其余孩子的置信度将等于 5, - 1, 6, 8。因此,第三个孩子将以 1 的音量哭泣,然后跑向出口。剩下的孩子的信心将等于 5, 5, 7。之后,第二个孩子去办公室,以 5 的音量哭泣。剩下的孩子的信心将等于 0, 3。然后,第四个孩子将进入办公室,以 2 的音量哭泣。因此,第五个孩子的信心将是 1,他将最后进入办公室。