Submit | All submissions | Best solutions | Back to list |

## WPBB - B Nobel (professional) |

A scientist, aspiring to the Nobel Prize, made a series of n measurements and received all possible results from the set {1,2,3, ...,n-1,n}. The scientist knows that if he could only obtain s/k as a result, the Nobel Prize would be his. He decided to disregard all but k measurements, such that the average of the remaining ones is s/k. Help him with this task. The stakes are high as the scientist has offered to share the award.

**Multiple test cases**

The first line of the input contains Z ≤ 8000 - the number of test cases. Z descriptions of single test cases follow.

**Single test case**

The input contains one line with three space-separated integers n, s and k.

**Bounds**

Common: 1 ≤ k ≤ n ≤ 40000, 0 ≤ s ≤ 10^{9}.

**Output**

Basic: If there exist k different elements of the set {1,2,...,n} whose average is s/k, the only line of the output should contain the word YES. Otherwise, output NO.

Professional: The first row should be as in the basic version. Additionally, if the answer is YES, output a second line containing a binary string of length n (containing ones and zeroes, not separated by spaces). A 1 on position i in the string means that the measurement i should be retained by the scientist, 0 - that it should be disregarded.

**Sample input**

3 3 6 2 5 7 3 1 1 1

**Sample output for the professional version**

NIE TAK 11010 TAK 1

Added by: | gawry |

Date: | 2011-10-07 |

Time limit: | 0.100s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM64 |