import sys class LazyMinSeg: """range-add / range-min + 最左の値<=0 探索""" def __init__(self, arr): n = len(arr) self.n = n log = 0 while (1 << log) < n: log += 1 self.log = log size = 1 << log self.size = size BIG = float('inf') self.d = [BIG] * (2 * size) self.lz = [0] * size for i in range(n): self.d[size + i] = arr[i] for i in range(size - 1, 0, -1): self.d[i] = min(self.d[2*i], self.d[2*i+1]) def _all_apply(self, k, f): self.d[k] += f if k < self.size: self.lz[k] += f def _push(self, k): v = self.lz[k] if v != 0: self._all_apply(2*k, v) self._all_apply(2*k+1, v) self.lz[k] = 0 def _update(self, k): self.d[k] = min(self.d[2*k], self.d[2*k+1]) def apply(self, l, r, f): # [l, r) に f を加算 if l >= r: return size = self.size; log = self.log l += size; r += size for i in range(log, 0, -1): if ((l >> i) << i) != l: self._push(l >> i) if ((r >> i) << i) != r: self._push((r-1) >> i) l2, r2 = l, r while l < r: if l & 1: self._all_apply(l, f); l += 1 if r & 1: r -= 1; self._all_apply(r, f) l >>= 1; r >>= 1 l, r = l2, r2 for i in range(1, log+1): if ((l >> i) << i) != l: self._update(l >> i) if ((r >> i) << i) != r: self._update((r-1) >> i) def first_le0(self, l, r): # [l, r) で値<=0 の最左 index(無ければ -1) if l >= r: return -1 size = self.size; log = self.log l += size; r += size for i in range(log, 0, -1): if ((l >> i) << i) != l: self._push(l >> i) if ((r >> i) << i) != r: self._push((r-1) >> i) left_segs = []; right_segs = [] ll, rr = l, r while ll < rr: if ll & 1: left_segs.append(ll); ll += 1 if rr & 1: rr -= 1; right_segs.append(rr) ll >>= 1; rr >>= 1 segs = left_segs + right_segs[::-1] for seg in segs: if self.d[seg] <= 0: node = seg while node < size: self._push(node) if self.d[2*node] <= 0: node = 2*node else: node = 2*node + 1 return node - size return -1 class MinSeg: """点更新 / 範囲最小(締切ごとの最小チーム番号)""" def __init__(self, n, INF): self.n = n sz = 1 while sz < n: sz <<= 1 self.sz = sz self.INF = INF self.t = [INF] * (2 * sz) def build(self, arr): for i in range(self.n): self.t[self.sz + i] = arr[i] for i in range(self.sz - 1, 0, -1): self.t[i] = min(self.t[2*i], self.t[2*i+1]) def update(self, pos, val): i = self.sz + pos self.t[i] = val i >>= 1 while i: self.t[i] = min(self.t[2*i], self.t[2*i+1]) i >>= 1 def query(self, l, r): # [l, r) 最小 res = self.INF l += self.sz; r += self.sz while l < r: if l & 1: res = min(res, self.t[l]); l += 1 if r & 1: r -= 1; res = min(res, self.t[r]) l >>= 1; r >>= 1 return res def solve(N, K, M, A): S = sum(A[1:]) if S % (N+1) != 0: return None T = S // (N+1) if T < 1: return None w = [0]*(N+1) for i in range(1, N+1): w[i] = A[i] - T if w[i] < 0: return None if w[M] < 1: # M は最終試合で勝つので前半含め1勝以上必要 return None if A[M] - 2 < K: # 最終試合開始前に M が ready return None c = w[:] c[M] -= 1 # 前半の勝利数 for i in range(1, N+1): if c[i] > K: # 締切 U_i>=1 が必要 return None E = T - 1 # 前半の試合数(位置 1..E) if E == 0: return [M] contrib = [0]*(E+2) groups = [[] for _ in range(K+2)] # 締切 d のチーム(番号昇順) Uof = [0]*(N+1) rem = [0]*(N+1) for i in range(1, N+1): if c[i] > 0: U = K + 1 - c[i] # 締切 Uof[i] = U rem[i] = c[i] groups[U].append(i) if U <= E: contrib[U] += c[i] # slack0[θ] = θ - g(θ) (g(θ)=締切<=θ のジョブ数) slack0 = [0]*E g = 0 for theta in range(1, E+1): g += contrib[theta] sl = theta - g slack0[theta-1] = sl if sl < 0: # Hall 条件違反 return None treeA = LazyMinSeg(slack0) INF_B = N + 1 leafB = [INF_B]*K for d in range(1, K+1): if groups[d]: leafB[d-1] = groups[d][0] treeB = MinSeg(K, INF_B) treeB.build(leafB) ptr = [0]*(K+2) ans = [] for t in range(1, E+1): # θ0 = t 以上で slack==0 となる最左(逼迫点)。無ければ K(制約なし) j = treeA.first_le0(t-1, E) # 葉 [t-1, E) theta0 = K if j == -1 else j + 1 # 締切 <= θ0 の残チームのうち最小番号 istar = treeB.query(0, theta0) if istar >= INF_B: return None # 起きないはず d_star = Uof[istar] rem[istar] -= 1 if rem[istar] == 0: ptr[d_star] += 1 gl = groups[d_star] nxt = gl[ptr[d_star]] if ptr[d_star] < len(gl) else INF_B treeB.update(d_star - 1, nxt) # 位置 t に締切 d_star のジョブを置くと、θ= t: treeA.apply(t-1, hi, -1) # 半開区間 [t-1, hi) ans.append(istar) ans.append(M) return ans def main(): data = sys.stdin.buffer.read().split() idx = 0 N = int(data[idx]); idx += 1 K = int(data[idx]); idx += 1 M = int(data[idx]); idx += 1 A = [0]*(N+1) for i in range(1, N+1): A[i] = int(data[idx]); idx += 1 res = solve(N, K, M, A) if res is None: sys.stdout.write("-1\n") else: sys.stdout.write(str(len(res)) + "\n") sys.stdout.write(" ".join(map(str, res)) + "\n") if __name__ == "__main__": main()