#P1575. Time Exceeded Limit

Time Exceeded Limit

Description

众所周知,在算法竞赛中,不仅要求选手提交的程序能够正确考虑所有可能的分支情况并计算出答案,还要求选手的程序足够高效。因此,所有的题目都有时间复杂度和空间复杂度的约束。

Orange正在教实验室的新成员计算程序的时间复杂度。理论上,程序的时间复杂度取决于程序中被执行次数的最多的那条语句被执行的次数。C++编写的程序最多能在1s内执行 3×1083 \times 10^8 条语句。而Java和Python的速度分别比C++慢3倍和20倍,这意味着Java和Python在1s内最多只能执行 10810^81.5×1071.5 \times 10^7 条语句

目前大部分情况下,算法竞赛的题目均按照C++语言的运行速度设置时间限制。此外,以C++为基准,Java语言的限制会比C++额外多出一倍,Python额外多出4倍,即Java有2倍的评测时间,python有5倍

很显然,大部分情况下,时间复杂度瓶颈主要源自嵌套循环。现在,Orange决定考考你,给出提交代码的语言,嵌套循环的层数,以及每层循环的执行次数,请你判断这条提交能否顺利通过评测,取得AC。

Format

Input

输入包含多组测试数据,第一行为一个整数 TT,表示Orange的询问次数。

每个询问共由2行组成,第一行为一个字符串 ss 和2个整数 nntt,表示这条提交使用的语言,代码中嵌套最深的循环的深度和提交的题目以C++语言为标准的时间限制(以秒为单位)。第二行为 nn 个整数 cic_i,表示第 ii 层循环的执行次数。

数据范围

T104T \le 10^4

$s \in \{\text{"c++"},\text{"python"},\text{"java"}\}$

1n101 \le n \le 10

1t101 \le t \le 10

数据保证单次询问中:i=1nci1018\prod_{i=1}^n c_i \le 10^{18}

Output

对于每次询问,输出一行,如果其时间复杂度能够通过评测,即执行次数不超过提交语言的限制,则输出Accepted,否则输出Time Exceeded Limit

Samples

3
c++ 2 1
100000 100000
python 1 1
100000000
java 3 1
10000 10000 2
Time Exceeded Limit
Time Exceeded Limit
Accepted

Note

对于第一组提交,其嵌套了2层循环,因此执行的语句次数为 105×105=101010^5 \times 10^5 = 10^{10},而c++语言最多在1s内只能执行 3×1083 \times 10^8 条语句,因此本次提交会超时。

对于第二组提交,其只有1层循环,因此执行的语句次数为10810^8次,而python语言的限制为c++的5倍,其在限制的1s内最多执行 $5 \times 1.5 \times 10^7 = 7.5 \times 10^7 \le 10^8$,本次提交会超时。

对于第三组提交,其共嵌套了3层循环,执行次数为 2×1082 \times 10^8,由于时间限制有2×12 \times 1s,而java每1s可以执行10810^8条指令,刚好可以执行完成,因此本次提交通过。