English · Original
Chinese · Translation
Formal · Original
_n_ children are standing in a circle and playing a game. Children's numbers in clockwise order form a permutation _a_1, _a_2, ..., _a__n_ of length _n_. It is an integer sequence such that each integer from 1 to _n_ appears exactly once in it.
The game consists of _m_ steps. On each step the current leader with index _i_ counts out _a__i_ people in clockwise order, starting from the next person. The last one to be pointed at by the leader becomes the new leader.
You are given numbers _l_1, _l_2, ..., _l__m_ — indices of leaders in the beginning of each step. Child with number _l_1 is the first leader in the game.
Write a program which will restore a possible permutation _a_1, _a_2, ..., _a__n_. If there are multiple solutions then print any of them. If there is no solution then print _\-1_.
## Input
The first line contains two integer numbers _n_, _m_ (1 ≤ _n_, _m_ ≤ 100).
The second line contains _m_ integer numbers _l_1, _l_2, ..., _l__m_ (1 ≤ _l__i_ ≤ _n_) — indices of leaders in the beginning of each step.
## Output
Print such permutation of _n_ numbers _a_1, _a_2, ..., _a__n_ that leaders in the game will be exactly _l_1, _l_2, ..., _l__m_ if all the rules are followed. If there are multiple solutions print any of them.
If there is no permutation which satisfies all described conditions print _\-1_.
[samples]
## Note
Let's follow leadership in the first example:
* Child 2 starts.
* Leadership goes from 2 to 2 + _a_2 = 3.
* Leadership goes from 3 to 3 + _a_3 = 5. As it's greater than 4, it's going in a circle to 1.
* Leadership goes from 1 to 1 + _a_1 = 4.
* Leadership goes from 4 to 4 + _a_4 = 8. Thus in circle it still remains at 4.
#cf_span[n] 个孩子站成一个圈玩游戏。孩子们按顺时针方向的编号构成一个长度为 #cf_span[n] 的排列 #cf_span[a1, a2, ..., an]，即一个整数序列，其中从 #cf_span[1] 到 #cf_span[n] 的每个整数恰好出现一次。
游戏共进行 #cf_span[m] 步。每一步中，当前领队（编号为 #cf_span[i]）从下一个人开始，顺时针数出 #cf_span[ai] 个人。最后一个被点到的孩子成为新的领队。
给定数字 #cf_span[l1, l2, ..., lm] —— 每一步开始时的领队编号。编号为 #cf_span[l1] 的孩子是游戏中的第一个领队。
请编写一个程序，恢复一个可能的排列 #cf_span[a1, a2, ..., an]。如果有多个解，请输出任意一个；如果没有解，请输出 _-1_。
第一行包含两个整数 #cf_span[n], #cf_span[m]（#cf_span[1 ≤ n, m ≤ 100]）。
第二行包含 #cf_span[m] 个整数 #cf_span[l1, l2, ..., lm]（#cf_span[1 ≤ li ≤ n]）—— 每一步开始时的领队编号。
请输出一个 #cf_span[n] 个数的排列 #cf_span[a1, a2, ..., an]，使得按照所有规则进行游戏时，领队序列恰好为 #cf_span[l1, l2, ..., lm]。如果有多个解，请输出任意一个。
如果没有满足所有条件的排列，请输出 _-1_。
让我们追踪第一个例子中的领队变化：
## Input
第一行包含两个整数 #cf_span[n], #cf_span[m]（#cf_span[1 ≤ n, m ≤ 100]）。第二行包含 #cf_span[m] 个整数 #cf_span[l1, l2, ..., lm]（#cf_span[1 ≤ li ≤ n]）—— 每一步开始时的领队编号。
## Output
请输出一个 #cf_span[n] 个数的排列 #cf_span[a1, a2, ..., an]，使得按照所有规则进行游戏时，领队序列恰好为 #cf_span[l1, l2, ..., lm]。如果有多个解，请输出任意一个。如果没有满足所有条件的排列，请输出 _-1_。
[samples]
## Note
让我们追踪第一个例子中的领队变化：
孩子 #cf_span[2] 开始。领队从 #cf_span[2] 变为 #cf_span[2 + a2 = 3]。
领队从 #cf_span[3] 变为 #cf_span[3 + a3 = 5]。由于该值大于 #cf_span[4]，因此绕圈后变为 #cf_span[1]。
领队从 #cf_span[1] 变为 #cf_span[1 + a1 = 4]。
领队从 #cf_span[4] 变为 #cf_span[4 + a4 = 8]，因此在圈中仍停留在 #cf_span[4]。
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ with $ 1 \leq n, m \leq 100 $.
Let $ L = (l_1, l_2, \dots, l_m) $ be the sequence of leader indices, where $ l_k \in \{1, \dots, n\} $.
Let $ A = (a_1, a_2, \dots, a_n) $ be a permutation of $ \{1, 2, \dots, n\} $, where $ a_i $ is the count value for child $ i $.
**Constraints**
1. For each step $ k \in \{1, \dots, m-1\} $, starting from leader $ l_k $, counting $ a_{l_k} $ children in clockwise order (starting from the next child) must land exactly on $ l_{k+1} $.
2. The counting is performed on a circle of $ n $ children; positions are indexed modulo $ n $, with 1-based indexing.
3. $ A $ must be a permutation of $ \{1, 2, \dots, n\} $.
**Objective**
Find any permutation $ A $ satisfying:
For all $ k \in \{1, \dots, m-1\} $,
$$
l_{k+1} \equiv l_k + a_{l_k} \pmod{n}, \quad \text{with adjustment for 1-based indexing}
$$
More precisely:
Let $ p_k $ be the position of leader $ l_k $. The next leader is:
$$
l_{k+1} = \left( l_k + a_{l_k} - 1 \right) \bmod n + 1
$$
If no such permutation exists, output $-1$.
API Response (JSON)
{
"problem": {
"name": "B. Permutation Game",
"description": {
"content": "_n_ children are standing in a circle and playing a game. Children's numbers in clockwise order form a permutation _a_1, _a_2, ..., _a__n_ of length _n_. It is an integer sequence such that each integ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF818B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "_n_ children are standing in a circle and playing a game. Children's numbers in clockwise order form a permutation _a_1, _a_2, ..., _a__n_ of length _n_. It is an integer sequence such that each integ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "#cf_span[n] 个孩子站成一个圈玩游戏。孩子们按顺时针方向的编号构成一个长度为 #cf_span[n] 的排列 #cf_span[a1, a2, ..., an]，即一个整数序列，其中从 #cf_span[1] 到 #cf_span[n] 的每个整数恰好出现一次。\n\n游戏共进行 #cf_span[m] 步。每一步中，当前领队（编号为 #cf_span[i]）从下一个人开始，顺时针数出 #c...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, m \\leq 100 $. \nLet $ L = (l_1, l_2, \\dots, l_m) $ be the sequence of leader indices, where $ l_k \\in \\{1, \\dots, n\\} $. \nLet $ A = (a...",
"is_translate": false,
"language": "Formal"
}
]
}