{"raw_statement":[{"iden":"statement","content":"Eulampius is preparing himself to the Very Important Programming Contest (VIPC). There is a lot of time before the contest, and Eulampius hopes to make headway in his problem solving skills.\n\nEulampius decided to train by taking part in practice contests. He made a list of n contests that will take place before VIPC. Each contest in the list is characterized by three parameters: the day di of the contest, the minimum skill li required to take part in the contest and the maximum skill hi that the participant can reach after taking part in the contest. \n\nThe participant skill becomes equal to hi if he starts taking part in the contest when he's fully rested. If his fatigue equals t by the beginning of the contest, then the participant skill becomes equal to hi - t after the contest, even if hi - t is negative or less than his skill before the contest.\n\nParticipating in a contest takes much energy, that's why Eulampius can take part in at most one contest during a day. Participating in a contest increases Eulampius' fatigue by Δ t (same for all contests).\n\nEach day Eulampius doesn't participate in any contest, his fatigue t becomes equal to ⌊ t / 2⌋ (divided by two rounded down).\n\nInitially, Eulampius' skill is s, and his fatigue t equals zero. Your task is to determine the maximum skill Eulampius can reach before VIPC, no matter what his fatigue will be.\n\nThe first line contains three integers n, s, Δ t (1 ≤ n ≤ 2·105,  0 ≤ s ≤ 106,  0 ≤ Δ t ≤ 104) — the number of contests, Eulampius' initial skill, the amount of fatigue added after a contest. \n\nEach of the next n lines contains three integers di, li, hi (1 ≤ di ≤ 106, 0 ≤ li < hi ≤ 106) — the day of the i-th contest, the minimum skill needed to take part in the i-th contest and the maximum skill that can be reached after taking part in the i-th contest. \n\nThe contests are ordered by their dates, so di ≤ di + 1 (i = 1, 2, ..., n - 1).\n\nIn the first line print two integers c and m — the maximum skill Eulampius can reach and the number of contests he needs to take part in.\n\nIn the second line print m space-separated integers — the indices of the contests in the order of participation. The contests are indexed starting from 1 in order of their appearance in the input.\n\nIf there are multiple solutions, print any of them.\n\nIn the first example the maximum skill that Eulampius can reach is 96: \n\n"},{"iden":"input","content":"The first line contains three integers n, s, Δ t (1 ≤ n ≤ 2·105,  0 ≤ s ≤ 106,  0 ≤ Δ t ≤ 104) — the number of contests, Eulampius' initial skill, the amount of fatigue added after a contest. Each of the next n lines contains three integers di, li, hi (1 ≤ di ≤ 106, 0 ≤ li < hi ≤ 106) — the day of the i-th contest, the minimum skill needed to take part in the i-th contest and the maximum skill that can be reached after taking part in the i-th contest. The contests are ordered by their dates, so di ≤ di + 1 (i = 1, 2, ..., n - 1)."},{"iden":"output","content":"In the first line print two integers c and m — the maximum skill Eulampius can reach and the number of contests he needs to take part in.In the second line print m space-separated integers — the indices of the contests in the order of participation. The contests are indexed starting from 1 in order of their appearance in the input.If there are multiple solutions, print any of them."},{"iden":"examples","content":"Input6 12 35 8 226 22 437 40 658 40 6510 63 10011 62 97Output96 41 2 4 6 Input4 5 31 5 102 5 153 15 464 10 42Output43 22 3 Input4 5 61 5 102 5 153 15 464 10 42Output41 21 4 "},{"iden":"note","content":"In the first example the maximum skill that Eulampius can reach is 96:   Eulampius' initial skill is 12 and his fatigue is 0.  On the day 5 he participates in the first contest. Now his skill is 22 - 0 = 22 and his fatigue is 0 + 3 = 3.  On the day 6 he participates in the second contest. Now his skill is 43 - 3 = 40 and his fatigue is 3 + 3 = 6.  On the day 7 he does not participate in any contest. His skill is still 40 and his fatigue is .  On the day 8 he participates in the fourth contest. Now his skill is 65 - 3 = 62 and his fatigue is 3 + 3 = 6.  On the day 9 he does not participate in any contest. His skill is still 62 and his fatigue is .  On the day 10 he does not participate in any contest. His skill is still 62 and his fatigue is .  On the day 11 he participates in the sixth contest. Now his skill is 97 - 1 = 96 and his fatigue is 1 + 3 = 4. "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ s \\in \\Sigma^* $ be the encrypted string, where $ \\Sigma = \\{a, b, \\dots, z\\} $ and $ 1 \\leq |s| \\leq 10^5 $.\n\n**Constraints**  \nAll characters of $ s $ are lowercase English letters.\n\n**Objective**  \nDecrypt $ s $ to recover the original string $ s' $, where the decryption algorithm is unspecified.","simple_statement":"Decrypt the string by shifting each letter back by 1 in the alphabet (a becomes z, b becomes a, c becomes b, etc.).","has_page_source":false}