#include using namespace std; const int INF = 1000000000; // ================================================== // Range-add range-min lazy segment tree // ================================================== struct RangeAddRangeMinLazySegTree { int n, size, logn; vector min_value, lazy_add; RangeAddRangeMinLazySegTree() : n(0), size(1), logn(0) {} RangeAddRangeMinLazySegTree(const vector& initial_values) { init(initial_values); } void init(const vector& initial_values) { n = (int)initial_values.size(); size = 1; logn = 0; while (size < n) { size <<= 1; logn++; } min_value.assign(2 * size, INF); lazy_add.assign(size, 0); for (int i = 0; i < n; i++) { min_value[size + i] = initial_values[i]; } for (int i = size - 1; i >= 1; i--) { pull(i); } } void pull(int node) { min_value[node] = min(min_value[node * 2], min_value[node * 2 + 1]); } void apply_to_node(int node, int add_value) { min_value[node] += add_value; if (node < size) lazy_add[node] += add_value; } void push(int node) { if (lazy_add[node] != 0) { apply_to_node(node * 2, lazy_add[node]); apply_to_node(node * 2 + 1, lazy_add[node]); lazy_add[node] = 0; } } void range_add(int left, int right, int add_value) { if (left >= right) return; left += size; right += size; for (int h = logn; h >= 1; h--) { if (((left >> h) << h) != left) push(left >> h); if (((right >> h) << h) != right) push((right - 1) >> h); } int original_left = left; int original_right = right; while (left < right) { if (left & 1) apply_to_node(left++, add_value); if (right & 1) apply_to_node(--right, add_value); left >>= 1; right >>= 1; } left = original_left; right = original_right; for (int h = 1; h <= logn; h++) { if (((left >> h) << h) != left) pull(left >> h); if (((right >> h) << h) != right) pull((right - 1) >> h); } } int all_min() const { return min_value[1]; } template int max_right(int left, Predicate pred) { if (left == n) return n; left += size; for (int h = logn; h >= 1; h--) { push(left >> h); } int current_min = INF; do { while ((left & 1) == 0) left >>= 1; int next_min = min(current_min, min_value[left]); if (!pred(next_min)) { while (left < size) { push(left); left *= 2; int candidate_min = min(current_min, min_value[left]); if (pred(candidate_min)) { current_min = candidate_min; left++; } } return left - size; } current_min = next_min; left++; } while ((left & -left) != left); return n; } }; // ================================================== // Point-set range-min segment tree // ================================================== struct PointSetRangeMinSegTree { int n, size; vector min_value; PointSetRangeMinSegTree() : n(0), size(1) {} PointSetRangeMinSegTree(const vector& initial_values) { init(initial_values); } void init(const vector& initial_values) { n = (int)initial_values.size(); size = 1; while (size < n) size <<= 1; min_value.assign(2 * size, INF); for (int i = 0; i < n; i++) { min_value[size + i] = initial_values[i]; } for (int i = size - 1; i >= 1; i--) { min_value[i] = min(min_value[i * 2], min_value[i * 2 + 1]); } } void set_value(int index, int value) { index += size; min_value[index] = value; while (index >>= 1) { min_value[index] = min(min_value[index * 2], min_value[index * 2 + 1]); } } int all_min() const { return min_value[1]; } template int max_right(int left, Predicate pred) { if (left == n) return n; left += size; int current_min = INF; do { while ((left & 1) == 0) left >>= 1; int next_min = min(current_min, min_value[left]); if (!pred(next_min)) { while (left < size) { left *= 2; int candidate_min = min(current_min, min_value[left]); if (pred(candidate_min)) { current_min = candidate_min; left++; } } return left - size; } current_min = next_min; left++; } while ((left & -left) != left); return n; } }; bool simulate(int N, int K, int M, const vector& A, const vector& seq) { int T = (int)seq.size(); vector win(N + 1, 0); for (int t = 1; t <= T; t++) { int c = seq[t - 1]; if (c < 1 || c > N) return false; int before = (t - 1) + win[c]; if (t < T) { if (before >= K) return false; } else { if (c != M) return false; if (before < K) return false; } win[c]++; } for (int i = 1; i <= N; i++) { if (T + win[i] != A[i]) return false; } return true; } vector solve_fast(int N, int K, int M, const vector& A) { long long S = 0; for (int i = 1; i <= N; i++) S += A[i]; if (S % (N + 1) != 0) return {}; long long T_ll = S / (N + 1); if (T_ll < 1) return {}; int T = (int)T_ll; vector W(N + 1); for (int i = 1; i <= N; i++) { W[i] = A[i] - T; if (W[i] < 0) return {}; } if (W[M] < 1) return {}; if (A[M] - 2 < K) return {}; int m = T - 1; vector B(N + 1, 0), rem(N + 1, 0); vector deadline(N + 1, INF); vector deadline_count(max(1, m) + 1, 0); int sumB = 0; for (int i = 1; i <= N; i++) { int b = W[i] - (i == M ? 1 : 0); if (b < 0) return {}; B[i] = b; rem[i] = b; sumB += b; if (b > 0) { int d = K + 1 - b; if (d < 1) return {}; int effective_deadline = min(d, m); deadline[i] = effective_deadline; deadline_count[effective_deadline] += b; } } assert(sumB == m); if (m == 0) return vector{M}; vector slack_initial(m + 1, INF); int required_until_now = 0; for (int time = 1; time <= m; time++) { required_until_now += deadline_count[time]; int slack = time - required_until_now; if (slack < 0) return {}; slack_initial[time] = slack; } assert(required_until_now == m); RangeAddRangeMinLazySegTree slack_tree(slack_initial); vector team_initial(N + 1, INF); for (int team = 1; team <= N; team++) { if (rem[team] > 0) team_initial[team] = deadline[team]; } PointSetRangeMinSegTree team_tree(team_initial); vector answer; answer.reserve(T); for (int position = 1; position <= m; position++) { if (team_tree.all_min() < position) return {}; int first_zero_position = slack_tree.max_right(position, [](int min_slack) { return min_slack > 0; }); int limit = first_zero_position; int chosen_team = team_tree.max_right(1, [&](int min_deadline) { return min_deadline > limit; }); if (chosen_team == N + 1) return {}; answer.push_back(chosen_team); if (position < deadline[chosen_team]) { slack_tree.range_add(position, deadline[chosen_team], -1); } rem[chosen_team]--; if (rem[chosen_team] == 0) { team_tree.set_value(chosen_team, INF); } } answer.push_back(M); return answer; } string encode_state(int pos, const vector& rem) { string s = to_string(pos); s.push_back(':'); for (int i = 1; i < (int)rem.size(); i++) { s += to_string(rem[i]); s.push_back(','); } return s; } bool brute_can_finish_dfs( int N, int K, int M, int m, int pos, vector& rem, unordered_set& memo ) { if (pos == m + 1) { for (int i = 1; i <= N; i++) { if (rem[i] != 0) return false; } return true; } string key = encode_state(pos, rem); if (memo.count(key)) return false; for (int c = 1; c <= N; c++) { if (rem[c] == 0) continue; int already_won = 0; for (int i = 1; i < pos; i++) { } int before_wins = 0; // before_wins = initial_rem[c] - rem[c] is needed, // so this DFS version uses a caller-side remaining-only test below instead. } memo.insert(key); return false; } bool brute_can_finish_by_simulation( int N, int K, int M, const vector& A, const vector& prefix, const vector& B ) { long long S = 0; for (int i = 1; i <= N; i++) S += A[i]; int T = (int)(S / (N + 1)); int m = T - 1; vector used(N + 1, 0); for (int x : prefix) used[x]++; for (int i = 1; i <= N; i++) { if (used[i] > B[i]) return false; } vector rem(N + 1); for (int i = 1; i <= N; i++) rem[i] = B[i] - used[i]; unordered_set memo; function dfs = [&](int pos) -> bool { if (pos == m + 1) { vector seq = prefix; seq.push_back(M); return simulate(N, K, M, A, seq); } string key = encode_state(pos, rem); if (memo.count(key)) return false; for (int c = 1; c <= N; c++) { if (rem[c] == 0) continue; rem[c]--; vector seq = prefix; int filled = (int)prefix.size(); // This DFS is only for tiny T, so rebuild the partial sequence from external recursion is awkward. rem[c]++; } memo.insert(key); return false; }; return false; } bool brute_suffix_possible( int N, int K, int M, const vector& A, const vector& current ) { long long S = 0; for (int i = 1; i <= N; i++) S += A[i]; if (S % (N + 1) != 0) return false; int T = (int)(S / (N + 1)); int m = T - 1; if ((int)current.size() > m) return false; vector W(N + 1); for (int i = 1; i <= N; i++) { W[i] = A[i] - T; if (W[i] < 0) return false; } if (W[M] < 1) return false; if (A[M] - 2 < K) return false; vector B(N + 1); for (int i = 1; i <= N; i++) { B[i] = W[i] - (i == M ? 1 : 0); if (B[i] < 0) return false; } vector used(N + 1, 0); for (int c : current) { if (c < 1 || c > N) return false; used[c]++; if (used[c] > B[c]) return false; } vector partial_win(N + 1, 0); for (int t = 1; t <= (int)current.size(); t++) { int c = current[t - 1]; int before = (t - 1) + partial_win[c]; if (before >= K) return false; partial_win[c]++; } vector rem = B; for (int i = 1; i <= N; i++) rem[i] -= used[i]; unordered_set memo; function&)> dfs = [&](vector& seq) -> bool { int pos = (int)seq.size() + 1; if (pos == m + 1) { vector full = seq; full.push_back(M); return simulate(N, K, M, A, full); } string key = encode_state(pos, rem); if (memo.count(key)) return false; for (int c = 1; c <= N; c++) { if (rem[c] == 0) continue; seq.push_back(c); rem[c]--; int before = (pos - 1); int wins_before = 0; for (int x : seq) { if (x == c) wins_before++; } wins_before--; before += wins_before; if (before < K && dfs(seq)) return true; rem[c]++; seq.pop_back(); } memo.insert(key); return false; }; vector seq = current; return dfs(seq); } vector solve_bruteforce(int N, int K, int M, const vector& A) { long long S = 0; for (int i = 1; i <= N; i++) S += A[i]; if (S % (N + 1) != 0) return {}; int T = (int)(S / (N + 1)); if (T < 1) return {}; int m = T - 1; vector ans; ans.reserve(T); for (int pos = 1; pos <= m; pos++) { bool found = false; for (int c = 1; c <= N; c++) { ans.push_back(c); if (brute_suffix_possible(N, K, M, A, ans)) { found = true; break; } ans.pop_back(); } if (!found) return {}; } ans.push_back(M); if (!simulate(N, K, M, A, ans)) return {}; return ans; } int main() { int N, K, M; cin >> N >> K; cin >> M; vector A(N + 1); for (int i = 1; i <= N; i++) cin >> A[i]; long long S = 0; for (int i = 1; i <= N; i++) S += A[i]; int T_est = -1; if (S % (N + 1) == 0) T_est = (int)(S / (N + 1)); vector ans; const int BRUTE_N_LIMIT = 8; const int BRUTE_T_LIMIT = 10; if (T_est >= 0 && N <= BRUTE_N_LIMIT && T_est <= BRUTE_T_LIMIT) { ans = solve_bruteforce(N, K, M, A); } else { ans = solve_fast(N, K, M, A); } if (ans.empty()) { cout << -1 << '\n'; return 0; } cout << ans.size() << '\n'; for (int i = 0; i < (int)ans.size(); i++) { if (i) cout << ' '; cout << ans[i]; } cout << '\n'; return 0; }