#4157. 星际瘟疫

环网曾经是人类文明史上的奇迹，银河系中的无数星球被时空之门联系在一起，从此时间和空间不再是阻碍。一旦两个星球之间建立了时空联系，那么通过时空之门可以在一瞬间从一个星球到达另外一个星球。人类文明因此以前所未有的速度扩张到银河系的每个角落。

在被称为末日浩劫的上古事件中，人工智能消失了，而时空之门从此再也没有响应人类的呼唤。人类文明的n个星球中，如今只剩下k个尚有人类居住，而他们只能进行简单的实时通讯，再也不能互相访问。

更可怕的事情发生了，某个尚有人类居住的星球r上爆发了电子瘟疫。这种瘟疫大肆破坏人类的电子植入设备，几乎毁灭了r星。r星被毁灭之前传送过来的信息证实该电子瘟疫和上古人工智能的相似性将会允许它们通过部分上古时空之门。由于时空之门已经有几个世纪没人维护了，所以电子瘟疫利用时空之门进行的传送甚至不是双向的。

为了阻止电子瘟疫，人类决定使用他们剩余的总和为w的空间能量对环网中的某个星球进行空间打击（可以是r星）。空间打击可以让一个星球彻底消失。然而由于星球的参数不同，打击每个星球需要的空间能是不一样的。人类指挥官很想知道，人类能否打击某个星球使得电子瘟疫不能到达剩下的k-1个人类居住星，如果能的话，最小需要多少空间能。注意到如果电子瘟疫本来就不能到达剩下的k-1个人类居住星，那么就不需要打击了。

由于多重宇宙的存在，在不同宇宙中，k个人类居住点是不同的，为此，我们将对你进行多组询问。