| BSUIR Open XII: Student Final |
|---|
| Finished |
A fairly successful entrepreneur decided to establish deliveries of his products to a star system with two inhabited planets. For this purpose, a teleportation chamber was installed on each planet. A similar chamber was also located on the enterprise's premises. The enterprise's chamber is capable of teleporting exactly one container of products to one of the planets in one unit of time. A switch is used to select to which planet the goods should be teleported.
The enterprise produces a total of $$$m$$$ types of products. You have been provided with a schedule of goods delivery, which consists of $$$n$$$ non-intersecting time intervals. During the $$$i$$$-th time interval, containers of a certain type of goods $$$t_i$$$ will be loaded into the teleportation chamber from the $$$l_i$$$-th unit of time to the $$$r_i$$$-th unit of time, inclusive. Since teleportation takes exactly one unit of time, exactly $$$r_i-l_i+1$$$ containers will be loaded during the $$$i$$$-th interval. Due to production peculiarities, the schedule cannot contain more than two time intervals with the delivery of containers of the same type of product.
Your task is to ensure that an equal number of containers of each type of product is delivered to each planet. Since frequent use of the switch can break the teleportation chamber, you are asked to make no more than $$$m$$$ switches.
The first line contains two integers $$$n$$$ and $$$m$$$ — the number of time intervals in the delivery schedule and the number of types of products, respectively.
The next $$$n$$$ lines contain three integers each: $$$t_i$$$, $$$l_i$$$, and $$$r_i$$$ — the type of product in the $$$i$$$-th time interval, as well as the start and end of the $$$i$$$-th time interval, respectively.
$$$$$$1 \le m \le n \le 10^5$$$$$$ $$$$$$1 \le t_i \le m$$$$$$ $$$$$$1 \le l_i \le r_i \le 10^9$$$$$$ $$$$$$r_i \lt l_{i+1}$$$$$$
In the first line, print "Yes" if it is possible to deliver an equal number of containers of each type of product using no more than $$$m$$$ switches.
If delivery is not possible, then in a single line, print "No".
In the second line, print the number $$$k$$$ ($$$0 \le k \le m$$$) — the number of switches.
In the last line, print $$$k$$$ integers $$$s_i$$$ ($$$1 \le s_i \le 10^9$$$, $$$s_i \lt s_{i+1}$$$) — the times when the switch needs to be used. If there are multiple possible answers, you can output any.
Note that the switch at time $$$x$$$ always occurs before the teleportation of goods at time $$$x$$$.
4 31 1 22 3 63 8 91 11 14
Yes 3 5 9 12
1 11 1 3
No
5 31 1 22 3 43 5 82 9 101 11 12
Yes 1 7
| Name |
|---|


