暂无测试数据。

Notice

由于本题为交互题，请在Qingyu's OJ修复完成后，在Qingyu's OJ提交。

Background

众所周知，有些毒瘤数据结构（算法）对于蒟蒻很不友好。sqy就是一个蒟蒻，其对于所有的题目只会暴力枚举。这个问题使他在比赛中经常TLE，得不到高分，令他十分烦恼。

有一天，sqy去\(\tan \frac{\pi}{2}\)国，买了一个编程器。这个软件非常强大，可以自动生成一个数据结构，并且回答问题。不幸的是，sqy忘记了如何操作这台机器，因此他不知道编程器生成的是哪种数据结构（算法）。

我们假设有3类问题。每类问题，都有几种数据结构（算法）：

1. 查询问题: None (\(O(n^n)\))，SegmentTree（\(O(n\log n)\)），vEB Tree（\(O(n \log \log n)\)），ProgrammingForDataTree（\(O(1)\)）
2. 排序问题：StableBogoSort（\(O(n\times n!\)），BubbleSort（\(O(n^2)\)），QuickSort（\(O(n \log n)\)，可被卡），Sleep Sort（\(O(m)\)，\(m\)为数列中最大的数与最小的数的差，可被卡），ProgrammingForDataSort（\(O(1)\)）
3. 搜索问题：None（\(O(n^3)\)），Binary Search Tree（\(O(\log n)\)，可被卡），RedBlack Tree（\(O(\log n)\)），ProgrammingForDataTree（O(1)）

除了None以外，保证每种数据结构的时限均如其名，其特性也如其名。

SQY很想知道，这一次程序内部使用的是哪种数据结构（算法）、并且如何构造数据卡掉它。你能帮帮她吗？

Description

你的目标，是实现下面两个函数

std::string GetDataStructure(int cls, int(*f)(std::vector<int> v));
void HackDataStructure(int cls, std::string tag, int max, int time, int(*f)(std::vector<int> v));


GetDataStructure()

这个函数读入一个类型\(cls\)和函数指针\(f\)。\(f\)函数读入一个数列\(v\)。然后，它在内部完成第\(cls\)种工作（1 = 查询， 2 = 排序， 3 = 搜索），并返回它做这项工作所消耗的时间（单位：Nanoseconds）。你应该构造多个数据，让函数执行这个工作，并分析函数的时间复杂度，返回数据结构类型。

例如，你构造了两个排序任务，而且是一般的数据，不会卡任何算法/数据结构。复杂度为\(n = 1000, n=1000000\)，返回值分别是\(11, 22134\)，你就可以大致判断其为一个\(O(n \log n)\)的算法。由于常数项对于变化率均不起作用，你不需要担心常数的问题。同时，你必须注意你的数据对不同数据结构（算法）有不同的影响。如果这个函数超过了\(1.0 s\)还没有完成任务，则将强制结束并返回-1。

你的任务，是根据函数\(f\)的在不同规模下的时间，返回他是哪种数据结构。如"RedBlackTree"，"ProgrammingForData"。

HackDataStructure()

这个函数读入五个参数：\(cls\), \(tag\), \(max\), \(time\), \(f\)。
注意，你不必按照给定的参数名进行命名，因为这可能会触碰你所使用的语言的标准库关键字。为了解决这个问题，可以使用namespace。
1. cls，表示它完成的是第几类任务。如cls = 2表示它完成的是排序任务。
2. tag，表示它是这类任务的那种数据结构（算法），参考Background中的表格。如"QuickSort"，"RedBlackTree"。保证tag是用于完成cls的数据结构（算法）。
3. max，表示你构造的序列中的元素个数的最大值。
4. time，表示分配给\(f\)函数的时间。如果\(f\)函数超过了这个时间还没有完成任务，你将得到这个测试点的分数。
5. \(f\)，你用来调用的函数。
若你Hack成功，则返回-1.
同时，若你的Hack失败了，其会返回一个值，表示它用的时间。你可以用if语句判断出来，并自动判断是否扩大数据规模。你最多可调用的次数取决于测试点。
为什么不一次成功，直接构造一个卡满max的数据呢？原因如下：
1. 你所用的元素个数越少，测试点得分越高。你可以先生成一个不那么强力的数据，然后在根据返回值判断是否继续构造
2. 部分分值：如果你构造的数据的元素个数超出max，也可以获得一部分分数。

如何Debug

我们为您准备了一个模板，其中含有了几个测试数据结构和调用。你可以参考附加文件：[QINGYUOJ_2174]

Format

Input

你可以从标准读入中读取到有关这道题目的信息，详情见下。

Output

你不应该在标准输出中写入任何数据

Testing

我们一共有25个测试点。每个测试点只测试其中的一个函数，而且只调用一次。
需要注意的是，你的函数中调用\(f\)函数，所消耗的时间、占用的内存计算在你的限制以内。题目保证数据结构（算法）的效率足够高，且不会占用超过50%的内存。

我们会在标准输入中存留三个数字\(x, y, p\)。对于不同的函数，其作用也是不同的。

GetDataStructure()

\(x\)表示，你最多可以调用函数\(f\)的次数为\(x\)。如果\(x = -1\)，那么则表示你可以无限制调用函数。
\(y\)总是0，在这个函数中不起作用。
\(p\)表示这个测试点的时限（s）

HackDataStructure()

\(x\)表示，你最多可以调用函数\(f\)的次数为\(x\)。如果\(x = -1\)，那么则表示你可以无限制调用函数。
\(y\)的含义如下：
1. 如果你的函数TLE，则得0分
2. 如果你没有Hack掉，则得0分
3. 如果你Hack成功，但超出了maxn的限制\(t\)%,则只能得到\(A\times y^{-t^2}\)的分数。其中\(A\)为该测试点实际的分数
4. 如果你Hack成功，而且只是用了\(T\times maxn, 0 < T < 1\)个元素，则可额外获得\(A \times y^{-T-1}\)的分数。但是，你最多只能靠这种方法，在20个测试点中获得不超过10分。
\(p\)表示这个测试点的时限（s）