Dota is a custom map in the famous game Warcraft 3. It's so interesting that many university students are fond of it. I am one of those happy guys.
Lich is one of the heroes that I would like to choose to use in the Dota game.He has the power to use frost to cause tremendous pain to his enemy. Lich is a murderer without a trace of warmth.
His most terrified skill is Chain Frost. When using it, Lich will release a jumping breath of frost that can bounce for a few times. Frost will randomly bounce back and forth between units that are within some range and cause some damage per hit.
When I use this heroes, I always want to know: can I kill the enemy hero by using this terminal skill. Through I am a computer science student, I am not very good at programing. So I turn to you, a talented ACM player.
Suppose Lich and the enemy hero (only one) stand in a two dimensional map. There are N people in the map. The first person is Lich and the last person is the enemy hero. Lich can use Chain Frost only once. The Chain Frost will first hit the one which has a distance no more than R from Lich and case D damage. Then the frost will randomly bounce back and forth between alive units (but not Lich himself) that are within R range and cause D damage per hit. The frost will not bounce more than K times. Notice that the frost must bounce from one unit to the other, or it will stop. Also, when the Chain Frost hits some person A, the next time it must bounce to the other alive person B, and the distance between A and B must be no more than R, or it will stop too.
Every one have a health point (HP), and when one's health point is no more than 0, he is defeated. And when the one is defeated he will be removed from the map and can't be hit by the frost any more.
The first line is the number of tests cases T (T<=1000). Each test case starts with a line, which contains 4 integers, N (N>=3), R, K (K>=1), D. Then N lines follow, each containing three integers, Xi, Yi, Hi (Xi, Yi, Hi <=30000). Xi and Yi are the x and y-coordinates of the people and Hi is his health point.
Print one line for each test case. If lich can defeat the enemy hero, print "YES"; otherwise, print "NO". Print one blank after each case.
3 3 1 6 100 0 0 1200 0 1 300 0 2 300 3 1 5 100 0 0 1200 0 1 300 0 2 300 3 1 6 100 0 0 1200 0 1 200 0 2 300
YES NO NO