Google OA-8 2024

Problem Description

You have an infinitely long array initialized with zeros. You are given two integers, N and K, and for the next N lines, you will receive three integers L, R, and X. This indicates that you need to add X to every element in the array from index L to R (inclusive).

Your task is to identify a subsequence from this array that satisfies the following conditions:

1. The subsequence should be of maximum length.
2. It should be the smallest lexicographically.
3. The subsequence must form an increasing sequence of the form ([Z, Z+K, Z+2*K,...., Z+(L-1)*K]) for some value Z and length L.

Notes:
Remember that a sequence (A = [A_1, A_2,...., A_L]) is considered lexicographically smaller than a sequence (B = [B_1, B_2,...., B_L]) if there exists an index i such that (A_j = B_j) for all (j < i) and (A_i < B_i).

Output Format

Print the first integer which is the length of the subsequence and then the elements of the subsequence in the same line.

Constraints
1 <= N, K <= 2*10^5
1<=L<R <= 10^9
1< X <= 10^9

Sample Input:
4 2
1 3 1
2 4 2
5 6 3
5 5 1

Sample Output:
2 1 3