13043번 - Containers and Reagents 스페셜 저지다국어

Peter has got a new task from his Chemistry teacher. He must pour various reagents to containers. Peter has n containers and m reagents. For each container there are two constraints min_i and max_i — the total minimum and maximum volume of reagents that can be poured to the i-th container, in milliliters. Additionally there are values c_i and p_i for the i-th container that specify that reagent c_i must occupy at least p_i percent of liquid volume in the i-th container. Peter has v_i milliliters of the i-th reagent. Peter must pour reagents to containers in such way that all constraints were satisfied: the i-th container had one or more reagents with the total volume from min_i to max_i, and reagent c_i occupied at least p_i percent of volume in it. All reagents must be completely poured to containers. There are no chemical reactions and volume of reagents doesn't change.

Help Peter to complete the task, or find out that it is impossible.

For example, let us consider the first test case from sample input. One possible correct solution is the following:

• Pour 3 milliliters of the first reagent, and 2 milliliters of the second reagent to the first container.
• Pour 4 milliliters of the third reagent, and 1 milliliter of the second reagent to the second container.
• Pour 3 milliliters of the fourth reagent, and 1 milliliter of the second reagent ot the third container.

All constraints for mini and maxi are satisfied, and the percentage constraints are also satisfied: the first container has 3 / 5 = 60% of the first reagent, the second container has 4 / 5 = 80% of the third reagent, the third container has 3 / 4 = 75% ≥ 70% of the fourth reagent. All reagents are completely poured to the contaners, so all requirements are satisfied.

Input data contains several test cases. The first line contains an integer t — the number of test cases (1 ≤ t ≤ 100). Description of test cases follows.

Each test case starts with a line that contains two integers: n and m (1 ≤ n, m ≤ 10⁵) — the number of containers and the number of reagents.

The i-th of the following n lines contains four integers: min_i, max_i, c_i, p_i (1 ≤ min_i ≤ max_i ≤ 10⁵, 1 ≤ c_i ≤ m, 1 ≤ p_i ≤ 100) — the minimum and maximum volume of liquid in the i-th container, the number of the reagent and the required percentage for the i-th container.

The next line contains m integers v_i — the volume of the i-th reagent Peter has (1 ≤ v_i ≤ 10⁵).

It is guaranteed that the sum of values of n and the sum of values of m for all test cases in one input data doesn't exceed 10⁵.

For each test case output the answer.

If there is a solution, print "YES", and then n lines. The i-th of these lines must describe the i-th container. It must start with k — the number of different reagents in the i-th container, followed by k pairs of integer id and real number v — the number of the reagent and its volume that must be poured to the i-th container. If there are several possible solutions, output any one.

If there is no solution, output "NO".

The answer will be considered correct if all constraints are satisfied with absolute or relative error not exceeding 10^-6.