Description

In this hotpot feast, there is one spicy rich-broth hotpot and $n$ types of food, each available in unlimited quantity. We number the foods from $1$ to $n$.

Each type takes a different amount of time to cook. The $i$-th type takes $s_i$ units of time to get cooked. This means if you put a food $i$ into the pot at time $T$, it will be cooked at time $T+s_i$, and thereafter it will remain cooked until it is taken out.

Yazid and YJQQQAQ have different tastes: YJQQQAQ thinks all foods are equally tasty; Yazid thinks no two types have the same tastiness, and, coincidentally, the smaller the id, the more Yazid likes it. Poor SkyDec cannot eat spicy food, so he can only help Yazid and YJQQQAQ cook.

The whole feast lasts $10^9$ units of time. Throughout the feast, besides chatting and laughing, the most important thing is of course eating. At any integer time, any one of the following $4$ types of events may occur. We use an integer $op$ between $0$ and $3$ to denote the event type:

• $0\ id$: SkyDec puts one food with id $id$ into the hotpot.
• $1$: Yazid searches the pot for a cooked food that he likes the most and takes one of that type. In particular, if there is no cooked food in the pot, Yazid will be angry.
• $2\ id$: YJQQQAQ searches the pot for food with id $id$:
  • If there is no such food in the pot, YJQQQAQ will be angry;
  • If there is a cooked one of that type, YJQQQAQ will take one and eat it;
  • If only uncooked ones of that type are in the pot, YJQQQAQ wants to know how much longer it will take for the one closest to being cooked (i.e., the one that has been in the pot the longest) to get cooked.
• $3\ l\ r$: The mouthwatering SkyDec wants to know how many cooked foods with ids in $[l,r]$ are currently in the pot.

Input Format

Read from standard input.

This problem contains multiple testcases. The first line contains a positive integer $T$, the number of testcases. Then for each testcase:

The first line contains a positive integer $n$, the number of food types.

The second line contains $n$ space-separated positive integers $s_1,s_2,\cdots,s_n$, the cooking time required for each type.

The third line contains a positive integer $Q$, the number of events.

Then follow $Q$ lines, each containing several space-separated nonnegative integers describing one event. Each line starts with two integers $t,op$, denoting the time the event occurs and the event type, respectively.

• If $op=0$ or $op=2$, then one positive integer $id$ follows, as described above;
• If $op=1$, then nothing else follows;
• If $op=3$, then two positive integers $l,r$ follow, as described above.

It is guaranteed that $t$ is strictly increasing in the order of input.

Output Format

For each operation with $op\neq 0$, output one line with the answer. For different values of $op$, output as follows:

• For $op=1$, if Yazid successfully takes a food, output the id of the food he takes; otherwise output $\text{``\texttt{Yazid is angry.}''}\!\!$.
• For $op=2$, if YJQQQAQ successfully takes a food, output $\!\!\text{``\texttt{Succeeded!}''}\!\!$; otherwise, if there is an uncooked food of that type in the pot, output how much longer it will take for the closest-to-cooked one of that type to get cooked; otherwise, output $\!\!\text{``\texttt{YJQQQAQ is angry.}''}\!$.
• For $op=3$, output the number of cooked foods in the pot whose ids are within the specified range.

1
2
1 100
10
1 0 2
2 0 1
3 2 1
4 2 2
5 2 1
200 0 1
201 3 1 2
202 1
203 1
204 1

Succeeded!
97
YJQQQAQ is angry.
2
1
2
Yazid is angry.

Hint

For all testdata, it is guaranteed that $T\leq 4$, $n\leq 100,000$, $Q\leq 500,000$, $1\leq s_i\leq 10^8$, $1\leq t\leq 10^9$, $op\in\{0, 1, 2, 3\}$, $1\leq id\leq n$, $1\leq l\leq r\leq n$. It is guaranteed that $t$ is strictly increasing in the order of input.

From CodePlus December 2017 Contest, proudly presented by the Student Algorithm and Programming Association, Department of Computer Science and Technology, Tsinghua University.

Credit: idea/Wang Yuzhong, problem setter/Wang Yuzhong, testers/Lü Shiqing, Yang Jingqin.

Git Repo: https://git.thusaac.org/publish/CodePlus201712

Thanks to Tencent for supporting this contest.

Translated by ChatGPT 5