Woburn Challenge 2018-19 Round 1 - Senior Division

~N~ ~(1 \le N \le 300\,000)~ students are filing into H.S. High School's popular French class, one after another. The classroom has a whopping ~10^6~ desks, all arranged in a single row and numbered ~1 \dots 10^6~ from left to right. The ~i~-th student to arrive has a social standing of ~S_i~ ~(1 \le S_i \le 10^6)~, and will sit at desk ~D_i~ ~(1 \le D_i \le 10^6)~. All ~N~ students have distinct social standings and will sit at distinct desks.

Even though the students love learning French, they sometimes still get distracted by their phones and stop paying attention in class. Furthermore, this issue is exasperated by the effects of peer pressure! If the ~i~-th student were to start using their phone, all students with smaller social standings who are sitting no further than ~R_i~ ~(1 \le R_i \le 10^6)~ desks away from the ~i~-th student will also start doing so ~(~in other words, each student ~j~ such that ~S_j < S_i~ and ~D_i - R_i \le D_j \le D_i + R_i)~. As a result of those students using their phones, even more students may in turn start using their phones, and so on.

When one or more students are present in the classroom, the "volatility" of that set of students is defined as the minimum number of students who would need to initially start using their phones by themselves, such that all of the students currently present would end up using their phones.

As the students file in, the French teacher wants to keep track of the volatility of her class, to give her an idea of what she'll be in for. So, after each student ~i~ sits down, the teacher is interested in the volatility of the students present so far ~(~students ~1 \le i)~. Please help her compute this list of ~N~ volatilities.

Subtasks

In test cases worth 8/40 of the points, ~N \le 10~.
In test cases worth another 6/40 of the points, ~N \le 300~.
In test cases worth another 8/40 of the points, ~N \le 3\,000~.

Input Specification

The first line of input consists of a single integer, ~N~.
~N~ lines follow, the ~i~-th of which consists of three space-separated integers, ~S_i~, ~D_i~, and ~R_i~, for ~i = 1 \dots N~.

Output Specification

Output ~N~ lines, the ~i~-th of which should consist of a single integer, the volatility after the first ~i~ students have arrived, for ~i = 1 \dots N~.

Sample Input

8
14 5 1
8 6 3
12 1 3
19 8 2
21 7 3
10 11 1
3 10 6
13 9 10

Sample Output

1
1
2
3
2
3
3
1

Sample Explanation

After the first student arrives, it would be necessary for just them to start using their phone, resulting in a volatility of ~1~.

After the second student arrives, it would still only be necessary for student ~1~ to start using their phone, as that would also cause student ~2~ to also use their phone. Therefore, the volatility of these two students is still ~1~.

After the third student arrives, it would be necessary for at least two of the three students to start using their phones (students ~1~ and ~3~). Therefore, the volatility of these three students is ~2~.

Once all students are present, they would all end up using their phones if only student ~5~ initially decided to use their phone. Therefore, the volatility of all ~8~ students is ~1~.