CF1012F Passports

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

In the first line of the input there are two integers $ N $ ( $ 1

If it is impossible to get all visas on time, just print "NO" (quotes for clarity). Otherwise, print "YES" and $ N $ lines describing trips. For each trip, first print number of the passport Gleb should put this country's visa in, and then print number of the day he should apply for it. Print trips in the same order as they appear in the input. Days are numbered from 1, starting with tomorrow—the first day you can apply for a visa. Passports are numbered from 1 to $ P $ . If there are several possible answers, print any of them.

Examples with answer "YES" are depicted below. Each cell of the stripe represents a single day. Rectangles represent trips, each trip starts in the morning and ends in the evening. Rectangles with angled corners represent visa applications. Each application starts in the middle of a day and ends $ t_{i} $ days after. The trip and the visa application for the same country have the same color. In examples with two passports, visa applications and trips depicted above the time stripe are made using the first passport, visa applications and trips depicted below the time stripe are made using the second passport. Example 1: Example 2: Example 3: