ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5078: 牙医根纳季

内存限制：256 MB 时间限制：2 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：5 通过：1
提交提交记录统计Web Board

题目描述

A.牙医根纳季
每次测试的时间限制
1 秒
每个测试的内存限制
256 兆字节
输入
标准输入
输出
标准输出
根纳迪是伯兰最好的儿童牙医之一。今天，n个孩子与他约好了，他们在他的办公室前排队。
所有的孩子都喜欢在牙医的接待处大声哭泣。我们用从 1 到 n 的整数按照它们在行中的顺序枚举子项。每个孩子都与他的忠诚的价值有关。孩子们一个接一个地轮流进入办公室;每次排队的孩子都去看医生。
当根纳迪治疗第 i 个孩子的牙齿时，孩子正在用 vi 的音量哭泣。此时，行中第一个子项的置信度减去 v i 量，第二个子项的置信度减去值 v i-1，依此类推。排在孩子后面的孩子几乎听不到哭声，所以信心不变。
如果在任何时候，第j个孩子的信心小于零，他就会开始用dj的音量哭泣，然后离开队伍，跑向出口，而不去医生办公室。此时，行中第 j 个之后所有孩子的置信度降低 dj 的量。
所有这些事件都以某种顺序一个接一个地立即发生。有些哭泣可能会导致其他哭泣，引起连锁反应。一旦进入走廊，它就安静了，排在第一位的孩子进入医生办公室。
帮助牙医根纳迪确定他将治愈牙齿的孩子的数量。按时间顺序打印其编号。
输入
输入的第一行包含一个正整数 n （1≤n≤4000） - 该行中的孩子数。
接下来的n行包含三个整数，每个整数v i，d i，p i （1≤v i，d i，p i≤10 6） - 医生办公室的哭声量，大厅里的哭声量和第i个孩子的信心。
输出
在第一行中打印数字k-根纳迪将治愈牙齿的儿童人数。
在第二行中打印 k 个整数 - 将按递增顺序到达行尾的子项的数量。
例子
输入 
							
							

								5 
							


							

								4 2 2 
							


							

								4 1 2
							


							

								3 3 5 
							


							

								5 2 4
							


							

								5 1 2

输出 
							
							

								2 
							


							

								1 3
输入 
							

								 
							


							

								5 
							


							

								4 5 1 
							


							

								5 3 9
							


							

								2 1 8 
							


							

								4 1 2
							


							

								4 1 9
输出 
							
							

								4 
							


							

								1 2 4 5

注意
在第一个例子中，根纳迪首先在第 4 卷中治疗第一个会哭的孩子的牙齿。其余子项的置信度将分别等于 -2，1，3，1。因此，第二个孩子也以 1 的音量哭泣并跑向出口。其余子项的置信度将等于 0，2，0。然后第三个孩子会去办公室，用第 5 卷哭泣。其他孩子不忍心，大声哭着跑到出口。
在第二个样本中，首先第一个孩子进入办公室，他会用第 4 卷哭泣。其余孩子的置信度等于 5，-1，6，8。因此，第三个孩子会用 1 的音量哭泣并跑到出口。其余孩子的置信度将等于 5，5，7。之后，第二个孩子去办公室用5的音量哭泣。其余子项的置信度将等于 0，3。然后第四个孩子会走进办公室，用 2 的音量哭泣。正因为如此，第五个孩子的信心将是1，他将最后进入办公室。
Gennady the Dentist
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Gennady is one of the best child dentists in Berland. Today n children got an appointment with him, they lined up in front of his office.
All children love to cry loudly at the reception at the dentist. We enumerate the children with integers from 1 to n in the order they go in the line. Every child is associated with the value of his cofidence pi. The children take turns one after another to come into the office; each time the child that is the first in the line goes to the doctor.
While Gennady treats the teeth of the i-th child, the child is crying with the volume of vi. At that the confidence of the first child in the line is reduced by the amount of vi, the second one − by value vi-1, and so on. The children in the queue after the vi-th child almost do not hear the crying, so their confidence remains unchanged.
If at any point in time the confidence of the j-th child is less than zero, he begins to cry with the volume of dj and leaves the line, running towards the exit, without going to the doctor's office. At this the confidence of all the children after the j-th one in the line is reduced by the amount of dj.
All these events occur immediately one after the other in some order. Some cries may lead to other cries, causing a chain reaction. Once in the hallway it is quiet, the child, who is first in the line, goes into the doctor's office.
Help Gennady the Dentist to determine the numbers of kids, whose teeth he will cure. Print their numbers in the chronological order.
Input
The first line of the input contains a positive integer n (1≤n≤4000) − the number of kids in the line.
Next n lines contain three integers each vi,di,pi (1≤vi,di,pi≤106) − the volume of the cry in the doctor's office, the volume of the cry in the hall and the confidence of the i-th child.
Output
In the first line print number k − the number of children whose teeth Gennady will cure.
In the second line print k integers − the numbers of the children who will make it to the end of the line in the increasing order.
Examples
Input 
5
4 2 2
4 1 2
5 2 4
3 3 5
5 1 2
Output 
2
1 3
Input 
5
4 5 1
5 3 9
4 1 2
2 1 8
4 1 9
Output 
4
1 2 4 5
Note
In the first example, Gennady first treats the teeth of the first child who will cry with volume 4. The confidences of the remaining children will get equal to -2,1,3,1, respectively. Thus, the second child also cries at the volume of 1 and run to the exit. The confidence of the remaining children will be equal to 0,2,0. Then the third child will go to the office, and cry with volume 5. The other children won't bear this, and with a loud cry they will run to the exit.
In the second sample, first the first child goes into the office, he will cry with volume 4. The confidence of the remaining children will be equal to 5,-1,6,8. Thus, the third child will cry with the volume of 1 and run to the exit. The confidence of the remaining children will be equal to 5,5,7. After that, the second child goes to the office and cry with the volume of 5. The confidences of the remaining children will be equal to 0,3. Then the fourth child will go into the office and cry with the volume of 2. Because of this the confidence of the fifth child will be 1, and he will go into the office last.

输入格式

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

输出格式

2
1 3

输入样例 复制 

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

输出样例 复制 

4
1 2 4 5

分类标签