Gleb is a famous competitive programming teacher from Innopolis. He is planning a trip to N programming camps in the nearest future. Each camp will be held in a different country. For each of them, Gleb needs to apply for a visa. For each of these trips Gleb knows three integers: the number of the first day of the trip s i , the length of the trip in days len i , and the number of days t i this country's consulate will take to process a visa application and stick a visa in a passport. Gleb has P ( 1 ≤ P ≤ 2 ) valid passports and is able to decide which visa he wants to put in which passport. For each trip, Gleb will have a flight to that country early in the morning of the day s i and will return back late in the evening of the day s i + len i - 1 . To apply for a visa on the day d , Gleb needs to be in Innopolis in the middle of this day. So he can't apply for a visa while he is on a trip, including the first and the last days. If a trip starts the next day after the end of the other one, Gleb can't apply for a visa between them as well. The earliest Gleb can apply for a visa is day 1. After applying for a visa of country i on day d , Gleb will get his passport back in the middle of the day d + t i . Consulates use delivery services, so Gleb can get his passport back even if he is not in Innopolis on this day. Gleb can apply for another visa on the same day he received his passport back, if he is in Innopolis this day. Gleb will not be able to start his trip on day s i if he doesn't has a passport with a visa for the corresponding country in the morning of day s i . In particular, the passport should not be in another country's consulate for visa processing. Help Gleb to decide which visas he needs to receive in which passport, and when he should apply for each visa. In the first line of the input there are two integers N ( 1 ≤ N ≤ 22 ) and P ( 1 ≤ P ≤ 2 )—the number of trips and the number of passports Gleb has, respectively. The next N lines describe Gl