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 ≤ 10^5]，#cf_span[0 ≤ k ≤ 10^14]）。第二行给出 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 10^9]）。\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 ≤ 10^5]，#cf_span[0 ≤ k ≤ 10^14]）。第二行给出 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 10^9]）。在 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}]"}}]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of animals.
Let $ k \in \mathbb{Z}_{\geq 0} $ be the number of examinations the doctor will perform.
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 $.
**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 queue process:
- Initially, the queue is $ (1, 2, \dots, n) $.
- Each time an animal $ i $ is examined, $ a_i $ decreases by 1.
- If $ a_i > 0 $ after examination, animal $ i $ re-enters the end of the queue.
- If $ a_i = 0 $, the animal leaves permanently.
- The process stops after exactly $ k $ examinations.
If the total required examinations $ \sum_{i=1}^n a_i < k $, output `-1`.
Otherwise, output the sequence of animal IDs currently in the queue after $ k $ examinations, in order.
API Response (JSON)
{
"problem": {
"name": "D. 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": "CF84D"
},
"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 number of examinations the doctor will perform. \nLet $ A = (a_1, a_2, \\dots, a_n) $ b...",
"is_translate": false,
"language": "Formal"
}
]
}