No Change Required

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/FEB20/hindi/NOCHANGE.pdf), [Bengali](http://www.codechef.com/download/translated/FEB20/bengali/NOCHANGE.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/FEB20/mandarin/NOCHANGE.pdf), [Russian](http://www.codechef.com/download/translated/FEB20/russian/NOCHANGE.pdf), and [Vietnamese](http://www.codechef.com/download/translated/FEB20/vietnamese/NOCHANGE.pdf) as well. Chef lives in a country that uses coins of $N$ denominations. For each valid $i$, one coin of denomination $i$ is worth $D_i$ cents. A bus ticket, when bought from the driver, costs $P$ cents and can be paid for only with coins. Moreover, to save time, bus drivers never give back any change. Chef is wondering if it is possible that someone would have enough coins to buy a ticket, but would be forced to overpay for it (pay more than $P$ cents), or if it is always possible to pay exactly $P$ cents when it is possible to buy a ticket, regardless of the values of the coins the person buying the ticket has. If it is possible to be forced to overpay, please find any such example ― any multiset of coins such that in total, they are worth strictly more than $P$ cents, but if any coin is removed from this multiset, the total worth of the remaining coins is strictly smaller than $P$. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains two spaceseparated integers $N$ and $P$.  The second line contains $N$ spaceseparated integers $D_1, D_2, \dots, D_N$. ### Output For each test case:  If it is impossible for someone to be forced to overpay, print a single line containing the string `"NO"` (without quotes).  Otherwise, print a single line containing the string `"YES"`, followed by a space and $N$ spaceseparated integers $C_1, C_2, \ldots, C_N$ such that:  $0 \le C_i \le 10^9$ for each valid $i$  $P \lt S = \sum_{i=1}^N C_i \cdot D_i$  for each valid $i$, if $C_i \gt 0$, then $S  D_i \lt P$ ### Constraints  $1 \le T \le 10^4$  $1 \le N \le 10^3$  $1 \le P \le 10^9$  $1 \le D_1 \lt D_2 \lt \dots \lt D_N \leq 10^9$  the sum of $N$ over all test cases does not exceed $10^5$ ### Subtasks **Subtask #1 (8 points):**  $T \le 50$  $N \le 5$  $P \le 20$  $D_i \le 20$ for each valid $i$ **Subtask #2 (24 points):**  $P \le 10^3$  $D_i \le 10^3$ for each valid $i$  the sum of $N$ over all test cases does not exceed $10^4$ **Subtask #3 (68 points):** original constraints ### Example Input ``` 3 2 10 1 5 2 4 1 5 3 25 3 5 10 ``` ### Example Output ``` NO YES 0 1 YES 2 0 2 ``` ### Explanation **Example case 1:** No matter how many $5$cent coins and how many $1$cent coins a person has, if the total sum is at least $10$, they will always be able to pay precisely $10$ cents without requiring any change. **Example case 2:** If a person has a single $5$cent coin and nothing else, they will not be able to pay precisely $4$ cents and will be forced to overpay by giving away his only coin. **Example case 3:** If a person has two $3$cent coins, two $10$cent coins and no $5$cent coins, then the only way to pay $25$ cents is by giving away all the coins. They are worth $26$ cents in total, so this person is forced to overpay by $1$ cent.Author:  alex_2oo8 
Editorial  https://discuss.codechef.com/problems/NOCHANGE 
Tags  alex_2oo8, easy, feb20, math, observations, tmwilliamlin 
Date Added:  7012020 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions