A6442. 「CodePlus 2017 12 月赛」火锅盛宴

> SkyDec 和 YJQQQAQ 都是 Yazid 的好朋友。他们都非常喜欢吃火锅。有一天，他们聚在一起，享受一场火锅盛宴。


在这场火锅盛宴中，有一个麻辣浓汤锅底的火锅和 $n$ 种食物，每种食物数量都是无限的。我们用 $1$ 至 $n$ 将这些食材编号。

每种食物煮熟所需要的时间不同，第$i$种食物煮熟需要 $s_i$ 单位时间。这表示如果你在第 $T$ 个时刻将一个食物 $i$ 下到火锅里，那么它会在第 $T+s_i$ 个时刻被煮熟，并且此后一直会延续被煮熟的状态，直到它被拿走为止。

Yazid 和 YJQQQAQ 的口味不同：YJQQQAQ 觉得所有食物的好吃程度都是相同的；而 Yazid 则觉得没有两种食材的好吃程度是相同的，并且，巧合的是，编号越小的食物 Yazid 越喜欢吃。可怜的 S kyDec由于不能吃辣，所以只能帮 Yazid 和 YJQQQAQ 煮食物。

整个火锅盛宴持续 $10^9$ 单位时间。在整个盛宴中，三位好朋友除了谈笑风生之外，最重要的事当然就是吃东西了。在任意整数时刻，都有可能发生下列 $4$ 种事件中的任意一种，我们用 $0$ 至 $3$ 之间的整数 $op$ 描述事件类型：

* 0 id：表示 SkyDec 往火锅里下了一个编号为$id$的食物。
* 1：Yazid在锅内搜寻熟了的**且**最喜欢吃的食物，并拿走**一个**这种食物。特别地，如果锅里没有熟了的食物，那么 Yazid 会很愤怒。
* 2 id：YJQQQAQ 在锅内搜寻编号为 $id$ 的食物：如果锅里不存在该种食物，则 YJQQQAQ 会很愤怒；如果锅里存在熟了的该食物，则 YJQQQAQ 会取走**一个**并食用；如果锅里只有未煮熟的该种食物，那么 YJQQQAQ 会希望知道最接近煮熟的该种食物（即锅内存在时间最长的该种食物）还需要多少时间被煮熟。
* 3 l r：馋涎欲滴的 SkyDec 想知道，锅里编号在 $[l,r]$ 之间的**且**熟了的食物总共有多少个。

整个火锅晚宴中共发生了 $Q$ 个事件，且没有任意两个事件在同一时刻发生。

他们的好朋友 Flvze 想知道这场火锅晚宴中发生的所有事，所以请你告诉她。

从标准输入读入数据。

本题包含多组数据，输入的第一行为一个正整数 $T$，表示数据组数。接下来依次描述每组数据，对于每组数据：

第一行一个正整数 $n$，表示食物的种类数。

第二行 $n$ 个用空格隔开的正整数 $s_1,s_2,\dots,s_n$，描述每种食物煮熟需要的时间。

第三行一个正整数 $Q$，表示事件的数目。

接下来 $Q$ 行，每行若干个用空格隔开的非负整数，描述一个事件。先是两个整数 $t,op$，分别表示发生事件的时间以及事件的类型。如果 $op=0$ 或 $op=2$，则接下来 $1$ 个正整数 $id$，意义见「题目描述」；如果 $op=1$，则接下来没有其他数；如果 $op=3$，则接下来 $2$ 个正整数 $l,r$，意义见「题目描述」。

我们保证 $t$ 按输入顺序**严格**递增。

我们保证 $1\leq t\leq 10^9$，$0\leq op\leq 3$，$1\leq id\leq n$，$1\leq l\leq r\leq n$。

输出到标准输出。

对于每个 $op\neq 0$ 的操作，输出一行表示答案。对于不同的$op$，需要输出的内容如下：

* 对于 $op=1$，如果 Yazid 成功取走食物，则输出他取走食物的编号；否则输出 "Yazid is angry."（不含引号，下同）。
* 对于 $op=2$，如果 YJQQQAQ 成功取走食物，则输出 "Succeeded!"；否则，如果锅里有未煮熟的该类食物，输出最接近煮熟的该种食物还需要多少时间被煮熟；否则，输出 "YJQQQAQ is angry."。
* 对于 $op=3$，输出锅内编号在指定范围内的熟食的数量。

## 子任务





<!-- BEGIN: Migrated markdown table -->

| 测试点编号 | $n\leq$ | $Q\leq$ | 特殊约定 | 测试点分值 |
|-|-|-|-|-|
| 1 | $500$ | $1000$ | 无 | 8 |
| 2-3 | $10$ | $300,000$ | 无 | 6 |
| 4-5 | $100,000$ | $300,000$ | 所有 $s_i=1$ | 8 |
| 6-7 | $100,000$ | $300,000$ | 所有 $s_i$ 都相同 | 11 |
| 8-9 | $100,000$ | $300,000$ | $op\neq 3$ | 7 |
| 10-11 | $100,000$ | $300,000$ | 无 | 12 |
| 12-13 | $100,000$ | $500,000$ | 无 | 2 |

<!-- Migrated from original HTML table:
<table class="ui celled center aligned table"><thead><tr><th rowspan="1">测试点编号</th><th rowspan="1">$n\leq$ </th><th rowspan="1">$Q\leq$ </th><th rowspan="1">特殊约定</th><th rowspan="1">测试点分值</th></tr></thead><tbody><tr><td rowspan="1">1</td><td rowspan="1">$500$ </td><td rowspan="1">$1000$ </td><td rowspan="1">无</td><td rowspan="1">8</td></tr><tr><td rowspan="1">2-3</td><td rowspan="1">$10$ </td><td rowspan="5">$300,000$ </td><td rowspan="1">无</td><td rowspan="1">6</td></tr><tr><td rowspan="1">4-5</td><td rowspan="5">$100,000$ </td><td rowspan="1">所有 $s_i=1$ </td><td rowspan="1">8</td></tr><tr><td rowspan="1">6-7</td><td rowspan="1">所有 $s_i$ 都相同</td><td rowspan="1">11</td></tr><tr><td rowspan="1">8-9</td><td rowspan="1">$op\neq 3$ </td><td rowspan="1">7</td></tr><tr><td rowspan="1">10-11</td><td rowspan="2">无</td><td rowspan="1">12</td></tr><tr><td rowspan="1">12-13</td><td rowspan="1">$500,000$ </td><td rowspan="1">2</td></tr></tbody></table>
-->

<!-- END: Migrated markdown table -->

对于所有数据，保证 $T\leq 4$，保证 $n\leq 100,000$，$Q\leq 500,000$，$1\leq s_i\leq 10^8$。

<hr style='color: #ddd; margin-bottom: 1em'>

来自 CodePlus 2017 12 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit：idea/王聿中　命题/王聿中　验题/吕时清，杨景钦
Git Repo：https://git.thusaac.org/publish/CodePlus201712
感谢腾讯公司对此次比赛的支持。