Problem:
 Score : 500 points    Problem Statement Takahashi has decided to work on K days of his choice from the N days starting with tomorrow.  You are given an integer C and a string S . Takahashi will choose his workdays as follows:   After working for a day, he will refrain from working on the subsequent C days.  If the i -th character of S is x , he will not work on Day i , where Day 1 is tomorrow, Day 2 is the day after tomorrow, and so on.   Find all days on which Takahashi is bound to work.      Constraints  1 \leq N \leq 2 \times 10^5  1 \leq K \leq N  0 \leq C \leq N  The length of S is N .  Each character of S is o or x .  Takahashi can choose his workdays so that the conditions in Problem Statement are satisfied.         Input Input is given from Standard Input in the following format:  N  K  C  S       Output Print all days on which Takahashi is bound to work in ascending order, one per line.        Sample Input 1 11 3 2
ooxxxoxxxoo      Sample Output 1 6  Takahashi is going to work on 3 days out of the 11 days. After working for a day, he will refrain from working on the subsequent 2 days.  There are four possible choices for his workdays: Day 1,6,10 , Day 1,6,11 , Day 2,6,10 , and Day 2,6,11 .  Thus, he is bound to work on Day 6 .       Sample Input 2 5 2 3
ooxoo      Sample Output 2 1
5  There is only one possible choice for his workdays: Day 1,5 .       Sample Input 3 5 1 0
ooooo      Sample Output 3  There may be no days on which he is bound to work.       Sample Input 4 16 4 3
ooxxoxoxxxoxoxxo      Sample Output 4 11
16

Solution (Python):
class SegmentTree:
    """Segment Tree (Point Update & Range Query)
    Query
        1. update(i, val): update i-th value to val
        2. query(low, high): find f(value) in [low, high)
    Complexity
        time complexity: O(log n)
        space complexity: O(n)
    """

    def __init__(self, N, f, default):
        self.N = 1 << (N - 1).bit_length()
        self.default = default
        self.f = f
        self.segtree = [self.default] * ((self.N << 1) - 1)

    @classmethod
    def create_from_array(cls, arr, f, default):
        N = len(arr)
        self = cls(N, f, default)
        for i in range(N):
            self.segtree[self.N - 1 + i] = arr[i]

        for i in reversed(range(self.N - 1)):
            self.segtree[i] = self.f(
                self.segtree[(i << 1) + 1], self.segtree[(i << 1) + 2]
            )
        return self

    def update(self, i, val):
        i += self.N - 1
        self.segtree[i] = val
        while i > 0:
            i = (i - 1) >> 1
            self.segtree[i] = self.f(
                self.segtree[(i << 1) + 1], self.segtree[(i << 1) + 2]
            )

    def __getitem__(self, k):
        return self.segtree[self.N - 1 + k]

    def query(self, low, high):
        
        low, high = low + self.N, high + self.N
        left_ret, right_ret = self.default, self.default
        while low < high:
            if low & 1:
                left_ret = self.f(left_ret, self.segtree[low - 1])
                low += 1
            if high & 1:
                high -= 1
                right_ret = self.f(self.segtree[high - 1], right_ret)
            low, high = low >> 1, high >> 1
        return self.f(left_ret, right_ret)


def main() -> None:
    N, K, C = map(int, input().split())
    S = [1 if s == "o" else 0 for s in input()]
    left, right = [-1] * N, [-1] * N
    max_v = -1
    for i in range(N):
        if i - C - 1 >= 0:
            max_v = max(max_v, left[i - C - 1])
        if S[i] == 1:
            left[i] = max_v + 1
    max_v = -1
    for i in reversed(range(N)):
        if i + C + 1 <= N - 1:
            max_v = max(max_v, right[i + C + 1])
        if S[i] == 1:
            right[i] = max_v + 1
    work_day = [max(0, left[i] + right[i] + 1) for i in range(N)]
    
    if max(work_day) > K:
        return
    segt = SegmentTree.create_from_array(work_day, max, 0)
    ans = []
    for i in range(N):
        if work_day[i] < K:
            continue
        m = max(segt.query(max(0, i - C), i), segt.query(i+1, min(i + 1 + C, N)))
        if m >= K:
            continue
        
        
        
        ans.append(i + 1)
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()

Solution (Python):
n, k, c = map(int, input().split())
s = list(input())


dp1 = [0] * (n + 1)
for i in reversed(range(n)):
    j = min(i + c + 1, n)
    if s[i] == 'o':
        dp1[i] = max(dp1[j] + 1, dp1[i + 1])
    else:
        dp1[i] = max(dp1[j], dp1[i + 1])

dp2 = [0] * (n + 1)
for i in range(n):
    j = max(i - c - 1, -1)
    if s[i] == 'o':
        dp2[i] = max(dp2[j] + 1, dp2[i - 1])
    else:
        dp2[i] = max(dp2[j], dp2[i - 1])





def check(idx):
    if s[idx] == 'x':
        return False

    if dp1[idx + 1] + dp2[idx - 1] >= k:
        return False
    else:
        return True


for i in range(n):
    if check(i):
        print(i + 1)

Solution (Python):
from sys import exit, setrecursionlimit
setrecursionlimit(10**6)

def array2D(row, col ,val=0):
    return [[val]*col for i in range(row)]

n,k,c = map(int, input().split())
S = [True if i=='o' else False for i in input()]

if n == c:
    ANS = []
    if sum(S) == 1:
        for i in range(n):
            if S[i]:
                ANS.append(i+1)
    print(*ANS, sep='\n')
    exit()



left = [0]*n
right = [0]*n
c = c+1
if S[0]:
    left[0] = 1

for i in range(1, c):
    if S[i]:
        left[i] = 1
    left[i] = max(left[i], left[i-1])

for i in range(c, n):
    if S[i]:
        left[i] = left[i-c] + 1
    else:
        left[i] = left[i-1]
if S[-1]:
    right[-1] = 1
for i in range(n-c, n-1)[::-1]:
    if S[i]:
        right[i] = 1
    right[i] = max(right[i], right[i+1])
for i in range(n-c)[::-1]:
    if S[i]:
        right[i] = right[i+c] + 1
    else:
        right[i] = right[i+1]

ans = []
for i in range(n):
    if S[i]:
        tl = 0
        tr = 0
        if i>0:
            tl = left[i-1]
        if i<n-1:
            tr = right[i+1]
        if tl + tr < k:
            ans.append(i+1)

print(*ans, sep='\n')

Solution (Python):
import bisect

N, K, C = map(int, input().split())
S = input()[::-1]
indices = []
last_set = []
flag = True
pre = 0
for i, s in enumerate(S):
  if i > pre + C:
    flag = True
  if s == 'o':
    indices.append(N-i)
    if flag and K>0:
      last_set.append(N-i)
      K -= 1
      flag = False
      pre = i

ans = []
last_set = last_set[::-1]
indices = indices[::-1]
pre = -1000000
for day in last_set:
  i = bisect.bisect_left(indices, day)
  if i == 0:
    ans.append(day)
    pre = day
  else:
    ii = indices[i-1]
    if abs(ii - pre) <= C:
      ans.append(day)
      pre = day
    else:
      iii = bisect.bisect_left(indices, pre+C+1)
      if iii < N:
        pre = min(indices[iii], ii)
      else:
        pre = ii

for day in ans:
  print(day)

Solution (Python):
import sys

inf = float('inf')
n, k, c = map(int, sys.stdin.readline().split())
s = sys.stdin.readline().rstrip()

def main():
    dp_l = [[0] * 2 for _ in range(n + 2)]
    for i in range(n):
        dp_l[i+1][0] = max(dp_l[i][0], dp_l[i][1])
        if s[i] == 'o':
            if i + 1 - c < 0:
                dp_l[i+1][1] = 1 
            else:
                dp_l[i+1][1] = dp_l[i+1-c][0] + 1
    dp_r = [[0] * 2 for _ in range(n + 2)]
    for i in range(n, 0, -1):
        dp_r[i][0] = max(dp_r[i+1][0], dp_r[i+1][1])
        if s[i-1] == 'o':
            if i + c > n + 1:
                dp_r[i][1] = 1
            else:
                dp_r[i][1] = dp_r[i+c][0] + 1

    for i in range(1, n + 1):
        if s[i-1] == 'o':
            if dp_l[i][0] + dp_r[i][0] < k:
                print(i)

if __name__ ==  '__main__':
    main()

Solution (Python):
n,k,c = map(int,input().split())
s = input()


def solve_shortest(s):

    sche = []
    t = 0
    day = 0
    for i,ch in enumerate(s):
        if (ch=="o") & (i>=t):
            sche += [i]
            t = i+c+1
            day += 1
        if day == k: break
    else:
        return
    
    return sche

sche1 = solve_shortest(s)
sche2 = solve_shortest(s[::-1])

ans = []
for x,y in zip(sche1,sche2[::-1]):
    if x+y == n-1:
        ans.append(x+1)
print("\n".join(map(str,ans)))

Solution (Python):
n,k,c=map(int,input().split())
S=list(input())
A=[]
B=[]
i=0
while i<n:
  if S[i]=="o":
    A.append(i)
    i=i+c+1
  else:
    i=i+1
i=n-1
while i>-1:
  if S[i]=="o":
    B.append(i)
    i=i-c-1
  else:
    i=i-1
if len(A)>k or len(B)>k:
  exit()
B.sort()
for i in range(k):
  if A[i]==B[i]:
    print(A[i]+1)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,K,C=map(int,input().split())
    S=list(map(int,input().replace('o','1').replace('x','0')))
    T=[0]*(N+1)
    for i in range(N):
        T[i+1]=T[i]+S[i]
    l0=[]
    l1=[]
    r0=-INF
    r1=-INF
    for i in range(N):
        if len(l0)<K and i>r0 and S[i]==1:
            l0.append(i)
            r0=i+C
        if len(l1)<K and i>r1 and S[N-1-i]==1:
            l1.append(N-1-i)
            r1=i+C
    l1.reverse()
    ans=[]
    for i in range(K):
        if l0[i]==l1[i]:
            if i==0 or i==K-1:
                ans.append(l0[i])
            else:
                q=T[l1[i+1]-C]-T[l0[i-1]+C+1]
                if l0[i-1]+C+1<l1[i+1]-C and q<2:
                    ans.append(l0[i])
    ans.sort()
    for x in ans:
        print(x+1)
    
    

if __name__ == '__main__':
    main()

Solution (Python):
n,k,c = map(int, input().split())
s = input()
ok = []
for i,x in enumerate(s):
    if x == "o":
        ok.append(i)

fast = []
pre = -10**10
for i,x in enumerate(s):
    if x == "o" and pre + c < i:
        fast.append(i+1)
        pre = i
    if len(fast) == k:
        break
late = []
pre = -10**10
for i,x in enumerate(s[::-1]):
    if x == "o" and pre + c < i:
        late.append(n-i)
        pre = i
    if len(late) == k:
        break
late = late[::-1]
for i in range(k):
    if fast[i] == late[i]:
        print(fast[i])

Solution (Python):
N, K, C = list(map(int, input().split()))
S = list(input())
o = "o"
x = "x"

W = [0] * N

if S[0] == o:
  W[0] = 1

for i in range(1, N):
  W[i] = W[i - 1]
  if S[i] == o:
    W[i] += 1

BDP = [0] * N
cnt = 0
if S[0] == o:
  BDP[0] = 1
  cnt = C
for i in range(1, N):
  BDP[i] = BDP[i - 1]
  if cnt != 0:
    cnt -= 1
    continue
  if S[i] == o:
    BDP[i] += + 1
    cnt = C

ADP = [0] * N
cnt = 0
if S[-1] == o:
  ADP[-1] = 1
  cnt = C
for i in range(N - 2, -1, -1):
  ADP[i] = ADP[i + 1]
  if cnt != 0:
    cnt -= 1
    continue
  if S[i] == o:
    ADP[i] += 1
    cnt = C

BDP = [0] + BDP

IM = [0] * (N + 2)
ans = 0
for i in range(C):
  if S[i] == x:
    continue
  if ADP[i] >= K:
    IM[max(-1, i - C) + 1] += 1
    IM[i + 1] -= 1
    IM[min(i + 1, N) + 1] += 1
    IM[min(i + C + 1, N) + 1] -= 1
for i in range(C, N - C):
  if S[i] == x:
    continue
  if BDP[i - C] + ADP[i] >= K:
    IM[max(-1, i - C) + 1] += 1
    IM[i + 1] -= 1
    IM[min(i + 1, N) + 1] += 1
    IM[min(i + C + 1, N) + 1] -= 1
for i in range(min(N - C, C), N):
  if S[i] == x:
    continue
  if BDP[i - C] + 1 >= K:
    IM[max(-1, i - C) + 1] += 1
    IM[i + 1] -= 1
    IM[min(i + 1, N) + 1] += 1
    IM[min(i + C + 1, N) + 1] -= 1

for i in range(1, N + 2):
  IM[i] += IM[i - 1]

if BDP[-1] < K:
  exit()

if C == 0:
  if W[-1] == K:
    for i in range(N):
      if S[i] == o:
        print(i + 1)
  exit()

DP = [0] * (N + 1)
for i in range(N):
  k = 0
  k += BDP[i]
  if i + C < N:
    k += ADP[i + C]
  if k >= K:
    DP[max(i, -1)] += 1
    DP[min(i + C, N)] -= 1

for i in range(1, N + 1):
  DP[i] += DP[i - 1]

for i in range(1, N + 1):
  if S[i - 1] == o and IM[i] == 0 and DP[i - 1] == 0:
    print(i)

Solution (Python):

inf = float("inf")
N,K,C = map(int,input().split())
S = list(str(input()))

old = -inf
used = [-1 for _ in range(N)] 
count = 0
for i in range(N):
    if S[i] == "o":
        if i > old+C and count < K:
            old = i
            used[i] = 1
            count+=1
        else:
            used[i] = 0
            
ans = []
front = N-1

hatu = True
for i in range(N):
    I = N-(i+1)
    if used[I] == 1:
        
        flag = True
        if hatu:
            hatu = False
            rest = front-I
            for j in range(rest):
                if used[front-j-1] != -1:
                    front -= j+1
                    flag = False
                    break
        else:
            rest = front-I
            for j in range(rest):
                
                if used[front-j-1] != -1 and front-j-1+C < front:
                    front -= j+1
                    if front != I:
                        flag = False
                    break
        
        if flag:
            ans.append(I+1)
            front = I
        
            
    
ans.sort()                
for a in ans:
    print(a)

Solution (Python):
n, kk, c = [int(i) for i in input().split()]
c = c+1
s = input()
dp1 = []
j = -c
k = 0
for i in range(n):
    if s[i] != "x" and j + c <= i:
        k += 1
        j = i
    dp1.append([k, j])

dp2 = []
j = n-1+c
k = 0
for i in reversed(range(n)):
    if s[i] != "x" and j - c >= i:
        k += 1
        j = i
    dp2.append([k, j])
dp2.reverse()


for i in range(n):
    if s[i] == "x":
        continue
    a, b = dp1[i - 1] if i > 0 else[0, -c]
    b += c
    b = max(b, i+1)
    if b == i:
        b += 1
    if b < n:
        a += dp2[b][0]
    if a < kk:
        print(i+1)

Solution (Python):
n, k, c = map(int, input().split())
s = input()

chuncks = []
last_workday = -c-10
for i in range(n):
	if s[i] == 'o':
		if len(chuncks) > 0 and i - chuncks[-1][0] <= c:  
			chuncks[-1].append(i)
		else:
			chuncks.append([i])
		last_workday = i



l = len(chuncks)
for i in range(l):
	if i != 0:
		
		to_start = 0
		for j in range(len(chuncks[i])):
			if chuncks[i][j] <= chuncks[i-1][0] + c:
				to_start = j+1
		chuncks[i] = chuncks[i][to_start:]

for i in range(l-1, -1, -1):
	if i != l-1:
		
		to_finish = len(chuncks[i]) 
		for j in range(len(chuncks[i])-1, -1, -1):
			if chuncks[i][j] + c >= chuncks[i+1][-1]:
				to_finish = j
		chuncks[i] = chuncks[i][:to_finish]



l = 0
for item in chuncks:
	if len(item) > 0:
		l += 1 

if l > k:
	pass
else:
	for i in range(len(chuncks)):
		if len(chuncks[i]) == 1:
			print(chuncks[i][0]+1)

Solution (Python):
n,k,c=map(int, input().split())
s = input()
leftmost = []
cursor = 0
for _ in range(k):
    while s[cursor] == 'x':
        cursor += 1
    leftmost.append(cursor)
    cursor += c+1
rightmost = []
cursor = n-1
for _ in range(k):
    while s[cursor] == 'x':
        cursor -= 1
    rightmost.append(cursor)
    cursor -= c+1
rightmost.reverse()
for l, r in zip(leftmost, rightmost):
    if l == r:
        print(l+1)

Solution (Python):
N, K, C = map(int, input().split())
S = list(input())

left = [None] * N
right = [None] * N

cnt = 0
penalty = 0
for idx in range(N):
    if S[idx] == 'o' and penalty == 0:
        left[idx] = cnt
        cnt += 1
        penalty = C + 1
    
    if cnt >= K: continue
    penalty = max(0, penalty - 1)

cnt = 0
penalty = 0
for idx_inv in range(N):
    idx = N - 1 - idx_inv
    if S[idx] == 'o' and penalty == 0:
        right[idx] = K - 1 - cnt
        cnt += 1
        penalty = C + 1
    
    if cnt >= K: continue
    penalty = max(0, penalty - 1)




for idx in range(N):
    if left[idx] != None and right[idx] != None and left[idx] == right[idx]:
        print(idx + 1)

Solution (Python):
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n,k,c = l_in()
S = s_in()


i = 0
left = set()

while i < n:
    if S[i] == 'o':
        left.add(i)
        i += 1+c
    else:
        i += 1

i = n-1
right = set()

while i >= 0:
    if S[i] == 'o':
        right.add(i)
        i -= 1+c
    else:
        i -= 1

if len(left) == k and len(right) == k:
    for i in sorted(list(left.intersection(right))):
        print(i+1)

Solution (Python):
N,K,C = map(int,input().split())
S = input()
dp1 = [0]*N
dp2 = [0]*N

c = 0
if S[0]=='o':
    dp1[0] = 1
    c = C
for i in range(N-1):
    if c==0 and S[i+1]=='o':
        dp1[i+1] = dp1[i]+1
        c = C
    else:
        c = max(0,c-1)
        dp1[i+1] = dp1[i]

c = 0
if S[-1]=='o':
    dp2[-1] = 1
    c = C
for i in range(N-2,-1,-1):
    if c==0 and S[i]=='o':
        dp2[i] = dp2[i+1]+1
        c = C
    else:
        c = max(0,c-1)
        dp2[i] = dp2[i+1]

ans = []
for i in range(N):
    if i==0 or dp1[i]-dp1[i-1]==1:
        if i==N-1 or dp2[i]-dp2[i+1]==1:
            ans.append(i+1)
if dp1[-1]>K:
    ans = []

for i in ans:
    print(i)

Solution (Python):
import sys
n, k, c = map(int, input().split())
s = input()
front = [0 for _ in range(n)]
back = [0 for _ in range(n)]

rm = -10**6
cur = 0
for i in range(n):
	if s[i] == "o" and i - rm > c:
		cur += 1
		front[i] = cur
		rm = i

if cur > k:
	sys.exit()

lm = 10**6
cur = k+1
for i in range(n-1, -1, -1):
	if s[i] == "o" and lm - i > c:
		cur -= 1
		back[i] = cur
		lm = i

for i in range(n):
	if front[i] > 0 and front[i] == back[i]:
		print(i+1)

Solution (Python):
class RangeMinimumQuery:
    def __init__(self, n, F=min, e=float("inf"), fill=None):
        self.n0 = 2**(n-1).bit_length()
        self.F = F
        self.e = e
        if fill is None:
            fill = e
        self.data = [fill]*(2*self.n0)

    def construct(self, a):
        for i, x in enumerate(a):
            self.data[i+self.n0-1] = x
        for i in range(self.n0-2, -1, -1):
            self.data[i] = self.F(self.data[2*i+1], self.data[2*i+2])

    def query(self, l,r):
        l += self.n0
        r += self.n0
        res = self.e
        while l < r:
            if r&1:
                r -= 1
                res = self.F(res, self.data[r-1])
            if l&1:
                res = self.F(res, self.data[l-1])
                l += 1
            l >>=1
            r >>=1
        return res

    def update(self, i, x):
        i += self.n0-1
        self.data[i] = x
        while i:
            i = ~-i//2
            self.data[i] = self.F(self.data[2*i+1], self.data[2*i+2])


n,k,c = map(int, input().split())
s = input()
f = [1]*n
for i in range(n):
    if s[i] == "x":
        f[i] = 0

foward = RangeMinimumQuery(n, max, 0)
for i in range(n):
    if f[i]:
        j = i-(c+1)
        s = foward.query(0,j+1)
        foward.update(i, s+1)

backward = RangeMinimumQuery(n, max, 0)
for i in reversed(range(n)):
    if f[i]:
        j = i+(c+1)
        s = backward.query(j,n)
        backward.update(i, s+1)

first = [-1]*(n+10)

ans = []
for i in range(n):
    if f[i] == 0:
        continue
    left = foward.query(0, i)
    if left == 0:
        l = i+1
    else:
        l = max(i+1, first[left]+c+1)
    if l >= n:
        right = 0
    else:
        right = backward.query(l,n)
    if left + right < k:
        ans.append(i+1)
    cur = foward.query(i,i+1)

    if first[cur] == -1:
        first[cur] = i

if len(ans):
    print(*ans, sep="\n")

Solution (Python):
N,K,C=map(int,input().split())
S=input()
l=[None]*N
c=0
t=0
while c<K:
    if S[t]=="o":
        l[t]=c
        c+=1
        t+=C+1
    else:
        t+=1
t=N-1
a=[]
while c:
    if S[t]=="o":
        c-=1
        if c==l[t]:
            a.append(t+1)
        t-=C+1
    else:
        t-=1
print(*a[::-1],sep="\n")

Solution (Python):
n,k,c = map(int, input().split())
s = input()

ans = [0] * n

p = 0
lasto = - c - 1

for i in range(n):
    if p == k:
        break
    if s[i] == "o":
        if i > lasto + c:
            ans[i] += 1
            p += 1
            lasto = i

s = s[::-1]
p = 0
lasto = - c - 1

q = 0

for i in range(n):
    if s[i] == "o":
        if i > lasto + c:
            ans[n - 1 - i] += 1
            p += 1
            lasto = i
            if p > k:
                q = 1
                break

if q == 0:
    for i in range(n):
        if ans[i] == 2:
            print(i + 1)

Solution (Python):
n, k, c = map(int, input().split())
s = input()
i = 0
l = [0] * (n + 1)
r = [0] * (n + 1)
while i < n:
    if s[i] == 'o':
        l[i + 1] = 1
        i += c
    i += 1
i = n - 1
while i >= 0:
    if s[i] == 'o':
        r[i] = 1
        i -= c
    i -= 1
for i in range(n):
    l[i + 1] += l[i]
    r[n - i - 1] += r[n - i]
for i in range(n):
    if l[i] + r[i + 1] < k:
        print(i + 1)

Solution (Python):
n, k, c = map(int, input().split())
s = input()

left = [0] * (n+1)
right = [0] * (n+1)

for i in range(1, n+1):
    if s[i-1] == 'o':
        if i - 1 - c >= 0:
            left[i] = max(left[i-1], left[i-1-c] + 1)
        else:
            left[i] = 1
    else:
        left[i] = left[i-1]

for i in reversed(range(n)):
    if s[i] == 'o':
        if i + 1 + c < n:
            right[i] = max(right[i+1], right[i+1+c] + 1)
        else:
            right[i] = 1
    else:
        right[i] = right[i+1]

l = 0
r = 0

end = False
ans = []
for i in range(n):
    if left[l] > 0:
        r = max(r, l+c, i+1)
    else:
        r = max(r, i+1)
    r = min(r, n)
    while r <= n and left[l] + right[r] < k and l <= i:
        l += 1
        r = max(r, l+c-1)
    if l > i:
        ans.append(i+1)
    if r > n:
        if left[i] < k:
            ans.append(i+1)

for x in ans:
    print(x)

Solution (Python):
n,k,c = map(int,input().split())
c += 1
a = input()
b = a[::-1]
form = [0]
lat = [0]
for i in range(n):
  if a[i] == 'x':
    form.append(form[-1])
  else:
    try:
      form.append(max(form[-c]+1,form[-1]))
    except:
      form.append(1)
  if b[i] == 'x':
    lat.append(lat[-1])
  else:
    try:
      lat.append(max(lat[-c]+1,lat[-1]))
    except:
      lat.append(1)
form.append(form[-1])
lat.append(lat[-1])
lat.reverse()



for i in range(n):
  if form[i] + lat[i+2] == k-1:
    print(i+1)

Solution (Python):

from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    n, k, c = [int(s) for s in input().strip().split()]
    s = input().strip()

    if c == 0:
        if s.count("o") == k:
            for i in range(n):
                if s[i] == "o":
                    print(i + 1)
        return

    prefix, suffix = [0] * n, [0] * n
    for i in range(n):
        if s[i] == "o":
            prefix[i] = 1 + (prefix[i - c - 1] if i - c - 1 >= 0 else 0)
        else:
            prefix[i] = prefix[i - 1] if i - 1 >= 0 else 0
    for i in range(n - 1, -1, -1):
        if s[i] == "o":
            suffix[i] = 1 + (suffix[i + c + 1] if i + c + 1 < n else 0)
        else:
            suffix[i] = suffix[i + 1] if i + 1 < n else 0
    
    cont = 0
    for i in range(-c + 1, n):
        ok = (prefix[i - 1] if i - 1 >= 0 else 0) + (suffix[i + c] if i + c < n else 0) >= k
        if ok:
            cont = 0
        else:
            cont += 1
            if cont >= c:
                print(i + 1)




BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")



if __name__ == "__main__":
    main()

Solution (Python):
def main():
    N, K, C = map( int, input().split())
    S = input()
    T = [False]*N
    ANS = [1]*N
    for i in range(N):
        if S[i] == "o":
            T[i] = True
        else:
            ANS[i] = 0
    F = []
    i = 0
    now = 0
    D = [False]*N
    k = 0
    while i < N and k < K:
        if T[i]:
            F.append(i)
            D[i] = True
            i += C+1
            k += 1
        else:
            i += 1
    for i in range(N):
        if not D[i]:
            ANS[i] = 0
    
    end = N-1
    for i in range(N-1,-1,-1):
        if T[i]:
            end = i
            break
    for m in F[::-1]:
        
        if m < end:
            ANS[m] = 0
        if end == 0:
            break
        for j in range(end-C-1,-1,-1):
            
            if T[j]:
                end = j
                break

    print("\n".join( map( str, [ i+1 for i in range(N) if ANS[i] == 1])))
            
    
if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N, K, C = map( int, input().split())
    S = input()
    T = [False]*N
    ANS = [1]*N
    for i in range(N):
        if S[i] == "o":
            T[i] = True
        else:
            ANS[i] = 0
    F = []
    i = 0
    now = 0
    D = [False]*N
    k = 0
    while i < N and k < K:
        if T[i]:
            F.append(i)
            D[i] = True
            i += C+1
            k += 1
        else:
            i += 1
    for i in range(N):
        if not D[i]:
            ANS[i] = 0
    
    end = N-1
    for i in range(N-1,-1,-1):
        if T[i]:
            end = i
            break
    for m in F[::-1]:
        
        if m < end:
            ANS[m] = 0
        if end == 0:
            break
        for j in range(end-C-1,-1,-1):
            
            if T[j]:
                end = j
                break

    print("\n".join( map( str, [ i+1 for i in range(N) if ANS[i] == 1])))
            
    
if __name__ == '__main__':
    main()

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,k,c = map(int,input().split())
s = input()

if n == 1:
  print(1)
  exit()

dp1 = [0] * (n+1)
dp2 = [0] * (n+1)

now = 10 ** 7;count = 0
for i in range(n-1,-1,-1):
  if s[i] == "o" and i + c < now:
    count += 1; now = i
    dp1[i] = (i,count)
  elif i == n-1:dp1[i] = (inf,0)
  else:
    dp1[i] = dp1[i+1]

now = - 10 ** 7;count = 0
for i in range(n):
  if s[i] == "o" and now + c < i:
    count += 1; now = i
    dp2[i] = (i,count)
  elif i == 0:dp2[i] = (-inf,0)
  else:
    dp2[i] = dp2[i-1]


if dp1[1][1] < k:print(1)
for i in range(1,n-1):
  index0,count0 = dp1[i+1]
  if index0 - c >= 0:
    count0 += dp2[min(index0-c,i-1)][1]
  if count0 < k:
    print(i+1)
if dp2[n-2][1] < k:print(n)

Solution (Python):
import sys
from bisect import bisect_right as br
input = sys.stdin.readline
N, K, C = map(int, input().split())
S = list(input())[: -1]
e = [-1] * N
os = []
for i in range(N):
  if S[i] == "o": os.append(i)
for i in range(N):
  if S[i] == "o":
    j = br(os, i + C)
    if j == len(os): continue
    e[i] = os[j]

dp = [0] * N
for i in range(N - 1, -1, -1):
  if e[i] != -1:
    dp[i] = dp[e[i]] + 1
  else: dp[i] += S[i] == "o"
if max(dp) > K:
  print()
  exit(0)
l = []
r = []
ls = 0
rs = 0
for i in range(N):
  if S[i] == "o":
    ls = i
    break
l.append(ls)

for i in range(N - 1, -1, -1):
  if dp[i] == K:
    rs = i
    break
r.append(rs)

for i in range(ls, N):
  if S[i] == "x": continue
  if l[-1] + C < i: l.append(i)
for i in range(rs, N):
  if S[i] == "x": continue
  if r[-1] + C < i: r.append(i)
  elif dp[r[-1]] == dp[i]: r[-1] = i
res = set(l) & set(r)
for r in sorted(res):
  print(r + 1)

Solution (Python):
N,K,C = map(int, input().split())
S = list(input())

memo = [0]*N
f = 0
for i in range(N-1, max(-1, N-C-2), -1):
    if S[i] == "o":
        f = 1
        break
if f == 1:
    for i in range(N-1, max(-1, N-C-2), -1):
        memo[i] = 1
for i in range(max(-1, N-C-2), -1, -1):
    if S[i] == "o":
        memo[i] = memo[i+C+1]+1
    else:
        memo[i] = memo[i+1]

m2 = [0]*N
cnt = 0
i = 0
while i < N:
    if S[i] == "o":
        cnt += 1
        m2[i] = cnt
        i += C+1
    else:
        i += 1
m2[0] = (m2[0], 0)
for i in range(1, N):
    if m2[i] == 0:
        m2[i] = m2[i-1]
    else:
        m2[i] = (m2[i], i)

ans = []
for i in range(1, N-1):
    if S[i] == "x":
        continue
    if m2[i-1][1]+C+1 >= N:
        if m2[i-1][0] < K:
            ans.append(i+1)
    elif m2[i-1][0] + memo[max(m2[i-1][1]+C+1, i+1)] < K:
        ans.append(i+1)

if N > 1:
    if m2[-2][0] < K and S[-1] == "o":
        ans.append(N)
    if memo[1] < K and S[0] == "o":
        ans.append(1)
elif S[0] == "o" and K > 0:
    ans.append(1)
ans.sort()
for a in ans:
    print(a)

Solution (Python):
N, K, C = map(int, input().split())
S = input()

if N == 1:
    print(1)
    exit()

before = [[0] * 2 for _ in range(N)]
if S[0] == 'o':
    before[0] = [1, C]
for i in range(1, N):
    before[i] = list(before[i-1])
    if S[i] == 'o' and i > before[i-1][1]:
        before[i][0] += 1
        before[i][1] = i + C

after = [0] * N
end = N
if S[-1] == 'o':
    after[-1] = 1
    end = N - 1 - C
for i in range(N-1)[::-1]:
    after[i] = after[i+1]
    if S[i] == 'o' and i < end:
        after[i] += 1
        end = i - C

if after[1] < K:
    print(1)
for i in range(1, N-1):
    d, s = before[i-1]
    if s < N:
        d += after[max(i+1, s)]
    if d < K:
        print(i + 1)
if before[-2][0] < K:
    print(N)

Solution (Python):
n, k, c = map(int, input().split())
s = input()
sub = []
key = -1
for i in range(n):
  if s[i] == "o" and (key == -1 or key+c+1 <= i):
    sub.append(i+1)
    key = i
  if len(sub) == k:
    break

sub2 = []
key = -1
for i in range(n-1, -1, -1):
  if s[i] == "o" and (key == -1 or key-c-1 >= i):
    sub2.append(i+1)
    key = i
  if len(sub2) == k:
    break

sub2.reverse()
ans = []
for i in range(k):
  if sub[i] == sub2[i]:
    ans.append(sub[i])

for value in ans:
  print(value)