English · Original
Chinese · Translation
Formal · Original
There are _n_ animals in the queue to Dr. Dolittle. When an animal comes into the office, the doctor examines him, gives prescriptions, appoints tests and may appoint extra examination. Doc knows all the forest animals perfectly well and therefore knows exactly that the animal number _i_ in the queue will have to visit his office exactly _a__i_ times. We will assume that an examination takes much more time than making tests and other extra procedures, and therefore we will assume that once an animal leaves the room, it immediately gets to the end of the queue to the doctor. Of course, if the animal has visited the doctor as many times as necessary, then it doesn't have to stand at the end of the queue and it immediately goes home.
Doctor plans to go home after receiving _k_ animals, and therefore what the queue will look like at that moment is important for him. Since the doctor works long hours and she can't get distracted like that after all, she asked you to figure it out.
## Input
The first line of input data contains two space-separated integers _n_ and _k_ (1 ≤ _n_ ≤ 105, 0 ≤ _k_ ≤ 1014). In the second line are given space-separated integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109).
Please do not use the _%lld_ specificator to read or write 64-bit numbers in C++. It is recommended to use _cin_, _cout_ streams (you can also use the _%I64d_ specificator).
## Output
If the doctor will overall carry out less than _k_ examinations, print a single number "-1" (without quotes). Otherwise, print the sequence of numbers — number of animals in the order in which they stand in the queue.
**Note that this sequence may be empty.** This case is present in pretests. You can just print nothing or print one "End of line"-character. Both will be accepted.
[samples]
## Note
In the first sample test:
* Before examination: {1, 2, 3}
* After the first examination: {2, 3}
* After the second examination: {3, 2}
* After the third examination: {2}
In the second sample test:
* Before examination: {1, 2, 3, 4, 5, 6, 7}
* After the first examination: {2, 3, 4, 5, 6, 7}
* After the second examination: {3, 4, 5, 6, 7, 2}
* After the third examination: {4, 5, 6, 7, 2, 3}
* After the fourth examination: {5, 6, 7, 2, 3}
* After the fifth examination: {6, 7, 2, 3, 5}
* After the sixth examination: {7, 2, 3, 5, 6}
* After the seventh examination: {2, 3, 5, 6}
* After the eighth examination: {3, 5, 6, 2}
* After the ninth examination: {5, 6, 2, 3}
* After the tenth examination: {6, 2, 3}
[{"iden":"statement","content":"有 #cf_span[n] 只动物在Dr. Dolittle的排队等候。当一只动物进入诊室时，医生会检查它、开处方、安排检查，也可能安排额外检查。医生非常熟悉森林里的所有动物，因此她确切知道队列中第 #cf_span[i] 只动物需要来她的诊室恰好 #cf_span[ai] 次。我们假设一次检查花费的时间远多于做测试或其他额外程序，因此一旦一只动物离开诊室，它会立即回到队列末尾。当然，如果某只动物已经就诊了所需次数，它就不必再排到队尾，而是直接回家。\n\n医生计划在接诊了 #cf_span[k] 只动物后回家，因此她关心那时队列的状况。由于医生工作时间很长，无法分心去计算，她请你帮忙算出这个队列。\n\n输入数据的第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 105]，#cf_span[0 ≤ k ≤ 1014]）。第二行给出用空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 109]）。\n\n请不要在 C++ 中使用 _%lld_ 标识符来读写 64 位整数。推荐使用 _cin_、_cout_ 流（你也可以使用 _%I64d_ 标识符）。\n\n如果医生总共进行的检查次数少于 #cf_span[k] 次，请输出单个数字 \"-1\"（不含引号）。否则，请输出一个序列——表示此时队列中动物的编号顺序。\n\n*注意：该序列可能为空。这种情况在预测试中存在。你只需什么都不输出，或输出一个“换行”字符即可，两者均被接受。"}},{"iden":"input","content":"输入的第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 105]，#cf_span[0 ≤ k ≤ 1014]）。第二行给出用空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 109]）。请不要在 C++ 中使用 _%lld_ 标识符来读写 64 位整数。推荐使用 _cin_、_cout_ 流（你也可以使用 _%I64d_ 标识符）。"},{"iden":"output","content":"如果医生总共进行的检查次数少于 #cf_span[k] 次，请输出单个数字 \"-1\"（不含引号）。否则，请输出一个序列——表示此时队列中动物的编号顺序。*注意：该序列可能为空。这种情况在预测试中存在。你只需什么都不输出，或输出一个“换行”字符即可，两者均被接受。"},{"iden":"examples","content":"输入\n3 3\n1 2 1\n输出\n2\n\n输入\n4 10\n3 3 2 1\n输出\n-1\n\n输入\n7 10\n1 3 3 1 2 3 1\n输出\n6 2 3 "},{"iden":"note","content":"在第一个样例中：\n\n检查前：#cf_span[{1, 2, 3}]\n第一次检查后：#cf_span[{2, 3}]\n第二次检查后：#cf_span[{3, 2}]\n第三次检查后：#cf_span[{2}]\n\n在第二个样例中：\n\n检查前：#cf_span[{1, 2, 3, 4, 5, 6, 7}]\n第一次检查后：#cf_span[{2, 3, 4, 5, 6, 7}]\n第二次检查后：#cf_span[{3, 4, 5, 6, 7, 2}]\n第三次检查后：#cf_span[{4, 5, 6, 7, 2, 3}]\n第四次检查后：#cf_span[{5, 6, 7, 2, 3}]\n第五次检查后：#cf_span[{6, 7, 2, 3, 5}]\n第六次检查后：#cf_span[{7, 2, 3, 5, 6}]\n第七次检查后：#cf_span[{2, 3, 5, 6}]\n第八次检查后：#cf_span[{3, 5, 6, 2}]\n第九次检查后：#cf_span[{5, 6, 2, 3}]\n第十次检查后：#cf_span[{6, 2, 3}]"},{"iden":"solution","content":""}]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of animals.
Let $ k \in \mathbb{Z}_{\geq 0} $ be the target number of examinations.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers, where $ a_i $ is the total number of required examinations for animal $ i $.
Let $ Q $ be the initial queue: $ Q = [1, 2, \dots, n] $.
Let $ r_i \in \mathbb{Z}^+ $ denote the remaining required examinations for animal $ i $, initialized as $ r_i = a_i $.
**Constraints**
1. $ 1 \leq n \leq 10^5 $
2. $ 0 \leq k \leq 10^{14} $
3. $ 1 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Simulate the process:
- While $ k > 0 $ and the total remaining examinations $ \sum_{i=1}^n r_i > 0 $:
- Dequeue the first animal $ i $ from $ Q $.
- Perform one examination: decrement $ r_i \leftarrow r_i - 1 $.
- If $ r_i > 0 $, enqueue $ i $ back at the end of $ Q $.
- Decrement $ k \leftarrow k - 1 $.
If $ k > 0 $ and $ \sum_{i=1}^n r_i = 0 $, output $-1$.
Otherwise, after exactly $ k $ examinations, output the current queue $ Q $ as a sequence of animal indices.
API Response (JSON)
{
"problem": {
"name": "B. Doctor",
"description": {
"content": "There are _n_ animals in the queue to Dr. Dolittle. When an animal comes into the office, the doctor examines him, gives prescriptions, appoints tests and may appoint extra examination. Doc knows all ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF83B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "There are _n_ animals in the queue to Dr. Dolittle. When an animal comes into the office, the doctor examines him, gives prescriptions, appoints tests and may appoint extra examination. Doc knows all ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"有 #cf_span[n] 只动物在Dr. Dolittle的排队等候。当一只动物进入诊室时，医生会检查它、开处方、安排检查，也可能安排额外检查。医生非常熟悉森林里的所有动物，因此她确切知道队列中第 #cf_span[i] 只动物需要来她的诊室恰好 #cf_span[ai] 次。我们假设一次检查花费的时间远多于做测试或其他额外程序，因...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of animals. \nLet $ k \\in \\mathbb{Z}_{\\geq 0} $ be the target number of examinations. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of p...",
"is_translate": false,
"language": "Formal"
}
]
}