题目描述
一道树上统计与背包混合的题：输入是一棵 个结点的树，解题时要用到容量为 的树形背包状态，预处理之后还要回答 组询问，评测时限 秒。四位同学交来四份解法，按本章的计数方法，它们的运算次数分别是：
| 做法 | 思路 | 运算次数 |
|---|---|---|
| ① | 邻接表存树，一次后序遍历完成预处理 | 约 |
| ② | 不做预处理，每组询问都把整棵树重扫一遍 | 约 |
| ③ | 树形背包，容量维不裁剪，两维都枚举到 | 约 |
| ④ | 树形背包，容量维按子树规模裁剪 | 约 |
你不需要实现这四份解法，只需要代入每组数据的真实数值做判定：在每秒 次运算的约定下（见背景知识），运算次数不超过 （恰好相等也算）的做法能在时限内通过。注意 、 与 的大小关系随参数变化，互有胜负，不能只盯着 一个字母下结论。
给定 组数据，每组给出 ，请对每组输出能通过的做法。
输入格式
第一行一个整数 ，表示数据组数。
接下来 行，每行四个整数 ，分别表示时限（秒）、树的结点数、背包容量、询问组数。
输出格式
输出 行，每行一个字符串：能通过的做法编号按从小到大连写（例如做法①③④能通过，输出 134）；若没有做法能通过，输出 NONE。
样例
输入
5 1 1000000 1000 1000 1 100000 1000 10 9 1000000000 1000 1000 1 1000 1000 1000 1 1000000 1 1000
输出
1 124 NONE 124 134
样例解释（上限 ；✓ 表示运算次数 ）：
| 组 | ① | ② | ③ | ④ | 输出 | |
|---|---|---|---|---|---|---|
| 1 | ✓ | ✗ | ✗ | ✗ | 1 | |
| 2 | ✓ | ✓ | ✗ | ✓ 恰好相等 | 124 | |
| 3 | ✗ | ✗ | ✗ | ✗ | NONE | |
| 4 | ✓ | ✓ | ✗ | ✓ | 124 | |
| 5 | ✓ | ✗ | ✓ | ✓ | 134 |
第 5 组里 ，，做法③与④的运算次数相同。第 3 组四个做法全部超限，输出 NONE。
数据范围
对于 的数据，，，，，。
数据保证 ，所有乘积都在 64 位整数范围内。
本题共 个测试点，每个测试点 分；数据中包含运算次数恰好等于上限的卡线组、做法②比④快与④比②快的对比组，以及全部超限的组。
背景知识
评测机每秒约完成 次基本运算；时限 秒最多容纳 次运算，运算次数 算通过，恰好相等也算通过。本章对树形背包的计数结论：容量维裁剪后，每一对点只会在它们的最近公共祖先处被合并一次，总量再被容量上限截住，是 ；不裁剪、两维都枚举到 ，每个孩子合并要 ，总共 。判定时要把复杂度里的每个字母都代入这组数据的真实数值。