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):
N, K, C = map(int, input().split())
S = list(input())


dp1 = [10**6] * K
dp2 = [0] * K

i = 0
dp_ind = 0
while i < N:
    if S[i] == "o":
        dp1[dp_ind] = i
        dp_ind += 1
        if dp_ind == K:
            break
        i += C + 1
        continue
    i += 1

i = N - 1
dp_ind = K - 1
while i >= 0:
    if S[i] == "o":
        dp2[dp_ind] = i
        dp_ind -= 1
        if dp_ind == -1:
            break
        i -= C + 1
        continue
    i -= 1
for a, b in zip(dp1, dp2):
    if a == b:
        print(a+1)

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


count = 0
i = 0
ansleft = set()
while i < n:
    if s[i] == "o":
        ansleft.add(i+1)
        i += c+1
        count += 1
    else:
        i += 1

if count >= k+1:
    sys.exit()


ansright = set()
s = s[::-1]
i = 0
while i < n:
    if s[i] == "o":
        ansright.add(n-i)
        i += c+1
    else:
        i += 1

ans = ansright&ansleft
ans = list(ans)
ans.sort()
for i in ans:
    print(i)

Solution (Python):
from bisect import *
from collections import *

N, K, C = map(int, input().split())
S = input()
T = [i for i, x in enumerate(S, 1) if x == 'o']
sl = deque()
sr = deque()
i = 0
while len(sl) < K:
    sl.append(T[i])
    i = bisect_right(T, T[i]+C)
i = len(T)-1
while len(sr) < K:
    sr.appendleft(T[i])
    i = bisect_left(T, T[i]-C)-1
for x, y in zip(sl, sr):
    if x == y:
        print(x)

Solution (Python):
n,k,c=map(int,input().split())
s="?"+input()
fwd=set()
now=1
while now<=n:
	if s[now]=="o":
		fwd.add(now)
		now+=c+1
	else:
		now+=1
bwd=set()
now=n
while now>=1:
	if s[now]=="o":
		bwd.add(now)
		now-=c+1
	else:
		now-=1
if len(fwd)==k:
	print(*sorted(list(fwd&bwd)),sep="\n")
else:
	exit()

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,k,c = LI()
s = input()
l,r = [0]*k, [0]*k
i = 0
cnt = 0
while i < n:
    if s[i] == 'o':
        if cnt >= k:
            quit()
        l[cnt] = i
        cnt += 1
        i += c
    i += 1
i = n-1
cnt = k-1
while i >= 0:
    if s[i] == 'o':
        if cnt < 0:
            quit()
        r[cnt] = i
        cnt -= 1
        i -= c
    i -= 1
for i in range(k):
    if l[i] == r[i]:
        print(l[i]+1)

Solution (Python):

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

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

left = []
i = 0
while i < n:
    if s[i] == "o":
        left.append(i)
        i += c
    i += 1

right = []
i = n - 1
while i >= 0:
    if s[i] == "o":
        right.append(i)
        i -= c
    i -= 1
right.reverse()
for i in range(len(left)):
    if left[i] == right[i]:
        print(left[i] + 1)

Solution (Python):
import sys,math,copy,queue,itertools,bisect
from fractions import gcd
sys.setrecursionlimit(10**7)
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
INF = 10**18
MOD = 10**9 + 7
DD = ((1,0),(0,1),(-1,0),(0,-1))
N,K,C = LI()
S = input()
dp = [0 for _ in range(N)]
j = 0
last = -INF
for i in range(N):
    if S[i] == 'o':
        if i - last > C:
            j += 1
            last = i
        dp[i] = j

if j != K:
    exit(0)

last = INF

j = K+1
for i in range(N-1,-1,-1):
    if 0 < dp[i] < j :
        if last - i <= C:
            dp[i] = 0
        else:
            j = dp[i]
            last = i

last = -1
cnt = 0
for i in range(N):
    if dp[i] > 0:
        if dp[i] != last:
            if cnt == 1:
                print (last_i + 1)
            cnt = 0
            last = dp[i]
            last_i = i
        cnt += 1
if cnt == 1: print (last_i + 1)

Solution (Python):
import bisect,sys
import math
from collections import deque

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac =fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % mod) % mod
        
    return CONV()



sys.setrecursionlimit(200005)


def main():
    N,K,C = isRaw()
    S = sRaw()
    ans = []
    lefts = []
    ava = 0
    idx = 0
    while idx < N:
        if S[idx]=="x":
            idx+=1
            continue
        ava+=1
        lefts.append(idx)
        if ava==K:
            break
        idx+=C+1
    rights = []
    ava = 0
    idx = N-1
    while idx >= 0:
        if S[idx]=="x":
            idx-=1
            continue
        ava +=1
        rights.append(idx)
        if ava == K:
            break
        idx-=C+1
    ans = [str(lefts[idx]+1) for idx in range(ava) if lefts[idx] == rights[ava-1-idx]]
    return "\n".join(ans)

if __name__ == "__main__":
    print(main())

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K, C = MAP()

S = input()

L = [0]*K

cnt = 0
idx = 0
while idx <= N-1 and cnt <= K-1:
	if S[idx] != "x":
		L[cnt] = idx+1
		idx += C+1
		cnt += 1
	else:
		idx += 1

R = [0]*K
S = S[::-1]

cnt = 0
idx = 0
while idx <= N-1 and cnt <= K-1:
	if S[idx] != "x":
		R[cnt] = N-idx
		idx += C+1
		cnt += 1
	else:
		idx += 1
R = R[::-1]
for x, y in zip(L, R):
	if x == y:
		print(x)

Solution (Python):
N, K, C = map(int, input().split())
S = input()
dl, pl, dr, pr = [], -(C + 1), [], -(C + 1)

for i in range(N):
    if S[i] == 'o' and i - pl > C and len(dl) < K:
        dl.append(i + 1)
        pl = i
    if S[N - i - 1] == 'o' and i - pr > C and len(dr) < K:
        dr.append(N - i)
        pr = i
for i in range(K):
    if dl[i] == dr[K - i - 1]:
        print(dl[i])

Solution (Python):
import sys


def main():
    N,K,C = map(int,input().split())
    s = input()
    wf,wb = [],[]
    
    now = -10**10
    for i,st in enumerate(s):
        if st == "o" and i+1 > now+C:
            wf.append(i+1)
            now = i+1
            
    now = 10**10
    s = s[::-1]
    for i,st in enumerate(s):
        if st == "o" and N-i < now-C:
            wb.append(N-i)
            now = N-i
            
    wf = wf[:K]
    wb = wb[:K]
    for f,b in zip(wf,wb[::-1]):
        if f == b:
            print(f)

if __name__ == "__main__":
    main()

Solution (Python):
N, K, C = map(int, input().split())
S = input()
L = [0] *K
R = [0] *K
i = 0
cnt = 0
while K > cnt:
    if S[i] == 'o':
        L[cnt] = i
        cnt += 1
        i += C
    i += 1
i = N-1
cnt = K-1
while cnt >= 0:
    if S[i] == 'o':
        R[cnt] = i
        cnt -= 1
        i -= C
    i -= 1
ans = []
for i in range(K):
    if L[i] == R[i]:
        ans.append(L[i]+1)
for x in ans:
    print(x)

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

r = []
l = []
i = 0
while 1:
    if S[i] == "x":
        i += 1
        continue
    r.append(i)
    if len(r) >= K:
        break
    i += C + 1

i = N - 1
while 1:
    if S[i] == "x":
        i -= 1
        continue
    l.append(i)
    if len(l) >= K:
        break
    i -= (C + 1)
for a, b in zip(r, reversed(l)):
    if a == b:
        print(a + 1)

Solution (Python):
def ris():
    return map(int, input().split())

def rs():
    return input()

n, k, c = ris()
s = rs()

i=0
rk = k
l1=[]
while(rk):
    if s[i]=='o':
        l1.append(i)
        rk-=1
        i+=c
    i+=1

i=n-1
rk=k
l2=[]
while(rk):
    if s[i]=='o':
        l2.append(i)
        rk-=1
        i-=c
    i-=1

for i1,i2 in zip(l1,reversed(l2)):
    if i1==i2:
        print(i1+1)

Solution (Python):
n, k, c = map(int, input().split())
s = input()
idx = 0
forward = []
while idx < len(s) and len(forward) < k:
    if s[idx] == 'o':
        forward.append(idx)
        idx += c + 1
    else:
        idx += 1

idx = len(s) - 1
backward = []
while idx >= 0 and len(backward) < k:
    if s[idx] == 'o':
        backward.append(idx)
        idx -= c + 1
    else:
        idx -= 1

for f, b in zip(forward, backward[::-1]):
    if f == b:
        print(f + 1)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



N,K,C = LI()
S = str(input())

L = []
R = []

for i in range(N):
    if S[i] == 'o':
        if len(L) == 0:
            L.append(i)
        else:
            if L[-1]+C+1 <= i:
                L.append(i)
    if len(L) == K:
        break

for i in range(N)[::-1]:
    if S[i] == 'o':
        if len(R) == 0:
            R.append(i)
        else:
            if R[-1]-C-1 >= i:
                R.append(i)
    if len(R) == K:
        break

R = list(reversed(R))

for i in range(len(L)):
    if L[i] == R[i]:
        print(L[i]+1)

Solution (Python):
N,K,C=map(int,input().split())
S=input()
X=[0]*N
Y=[0]*N
i=0
c=0
while(i<N):
    if S[i]=="o":
        c+=1
        X[i]=1
        i += (C+1)
    else:
        i+=1
if c>K:
    exit()
i = N - 1
while(i>=0):
    if S[i]=="o":
        Y[i]=1
        i -= (C+1)
    else:
        i -= 1
for i in range(N):
    if X[i] and Y[i]:
        print(i+1)

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

L, R = [], []

i, yasumi = 0, 0
while len(L) < K:
    if S[i] == 'o' and yasumi <= 0:
        L.append(i)
        yasumi = C + 1
    i += 1
    yasumi -= 1

i, yasumi = -1, 0
while len(R) < K:
    if S[i] == 'o' and yasumi <= 0:
        R.append(N+i)
        yasumi = C + 1
    i -= 1
    yasumi -= 1

R = R[::-1]
for i in range(K):
    if L[i] == R[i]:
        print(L[i] + 1)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n,k,c=MI()
    s=SI()
    ll=[0]*n
    rr=[0]*n
    for i,m in enumerate(s):
        if m == "o":
            if i-c-1>=0:ll[i] = ll[i - c - 1] + 1
            else:ll[i]=1
        else:ll[i]=ll[i-1]
    
    for i in range(n-1,-1,-1):
        m=s[i]
        if m == "o":
            if i + c + 1 < n:rr[i]=rr[i+c+1]+1
            else:rr[i]=1
        else:rr[i]=rr[(i+1)%n]
    
    ans=[]
    if n==1:ans.append(1)
    if n>1 and rr[1]<k:ans.append(1)
    for i in range(1,n-1):
        if ll[i-1]+rr[i+1]<k:ans.append(i+1)
    if n>1 and ll[n-2]<k:ans.append(n)
    print(*ans,sep="\n")

main()

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

L = list()
R = list()


i = 0
work_i = 0
while i < N and work_i < K:
    if S[i] == "o":
        L.append(i)
        work_i += 1
        i += C
    i += 1

j = N-1
work_j = 0
while j >= 0 and work_j < K:
    if S[j] == "o":
        R.append(j)
        work_j += 1
        j -= C
    j -= 1

R.reverse()



length = min(len(L), len(R))
for i in range(length):
    if L[i] == R[i]:
        print(L[i] + 1)

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

A = list()
B = list()

i = 0
num = 0
while num < K:
  if S[i] == "o":
    A.append(i)
    num += 1
    i += C
  i += 1
i = len(S)-1
num = 0
while num < K:
  if S[i] == "o":
    B.append(i)
    num+=1
    i -= C
  i -= 1
B.sort()

for i,j in zip(A,B):
  if i == j:
    print(i+1)

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

    L = []
    i = 0
    while len(L) < K:
        if S[i] == 'o':
            L.append(i)
            i += C
        i += 1

    R = []
    i = N-1
    while len(R) < K:
        if S[i] == 'o':
            R.append(i)
            i -= C
        i -= 1
    R = R[::-1]

    
    

    for i in range(K):
        if L[i] == R[i]:
            print(L[i] + 1)

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

DP1 = []
DP2 = []

day = 0
work = 0
while day < n and work < k:
    if S[day] == 'o':
        DP1.append(day)
        day += c + 1
        work += 1

    else:
        day += 1

day = n-1
work = 0
while day >= 0 and work < k:
    if S[day] == 'o':
        DP2.append(day)
        day -= c + 1
        work += 1
    else:
        day -= 1

for day1, day2 in zip(DP1, DP2[::-1]):
    if day1 == day2:
        print(day1+1)

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

DP1 = []
DP2 = []

day = 0
work = 0
while day < n and work < k:
    if S[day] == 'o':
        DP1.append(day)
        day += c + 1
        work += 1

    else:
        day += 1

day = n-1
work = 0
while day >= 0 and work < k:
    if S[day] == 'o':
        DP2.append(day)
        day -= c + 1
        work += 1
    else:
        day -= 1

for day1, day2 in zip(DP1, DP2[::-1]):
    if day1 == day2:
        print(day1+1)

Solution (Python):
from collections import deque
n, k, c = map(int, input().split())
s = str(input())


i = 0
l1 = []
while i <= n-1:
    if s[i] == 'o':
        l1.append(i+1)
        i += c + 1
    else:
        i += 1
    if len(l1) >= k:
        break
i = n-1
l2 = []
while i >= 0:
    if s[i] == 'o':
        l2.append(i+1)
        i -= (c + 1)
    else:
        i -= 1
    if len(l2) >= k:
        break
ans = []
for i, j in zip(l1, l2[::-1]):
    if i == j:
        ans.append(i)
print("\n".join(list(map(str, ans))))

Solution (Python):

import sys

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

assign_t = [False]*N
assign_b = [False]*N


i = 0
num = 0
while i<N:
    if S[i]=='o':
        assign_t[i]=True
        num += 1
        i += C+1
    else:
        i += 1

if num>K:
    print()
    sys.exit()

i = N-1
num = 0
while i>=0 and num<K:
    if S[i]=='o':
        assign_b[i]=True
        num += 1
        i -= C+1
    else:
        i -=1


for i in range(N):
    if assign_t[i] and assign_b[i]:
        print(i+1)

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

b = []

d = -1
for i in range(k):
    while s[d] == 'x':
        d -= 1
    b.append(n+d)
    d -= c+1

d = 0
for i in range(k):
    while s[d] == 'x':
        d += 1
    if d == b[-i-1]:
        print(d+1)
    d += c+1

Solution (Python):
N,K,C =map(int,input().rstrip().split(" "))
S = input()
kinmu = 0
niti = 0
f = []
b = []
kinmu = 0
niti = 0
while kinmu < K and niti < N:
  if S[niti] == "o":
    f.append(niti)
    kinmu += 1
    niti += C
  niti += 1
kinmu = 0
niti = N -1
while kinmu < K and niti >= 0:
  if S[niti] == "o":
    b.append(niti)
    kinmu += 1
    niti -= C
  niti -= 1
b.reverse()
for i in range(K):
  if f[i] == b[i]:
    print(f[i] + 1)

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


ansl = []
before = -float("inf")
for idx,s in enumerate(sl):
    if s == "o" and before + c < idx:
        before = idx
        ansl.append(idx)


ansl2 = []
before = -float("inf")
for idx,s in enumerate(sl[::-1]):
    if s == "o" and before + c < idx:
        before = idx
        ansl2.append(n-idx-1)


for a1,a2 in zip(ansl[:k], ansl2[:k][::-1]):
    if a1 == a2:
        print(a1+1)

Solution (Python):
import sys
input = sys.stdin.readline


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


def GetBase(t=0):
    ret = []
    last = -C * 2 - 1
    for i, s in enumerate(S[t:]):
        if s == 'x':
            continue
        elif last + C >= i + t:
            continue

        ret.append(i + t)
        last = i + t
    return ret


def GetReverse():
    ret = []
    last = -C * 2 - 1
    for i, s in enumerate(S[::-1]):
        if s == 'x':
            continue
        elif last + C >= i:
            continue

        ret.append(len(S) - 1 - i)
        last = i
    return reversed(ret)


def GetDepend(base_ans):
    ruiseki = []
    a = 0
    for s in S:
        if s == 'o':
            a += 1
            ruiseki.append(a)
        else:
            ruiseki.append(a)

    ret = {a: False for a in base_ans}
    for a in ret:
        if ruiseki[a] == ruiseki[min(N - 1, a + C)]:
            ret[a] = True
    return ret


def solve():
    base_ans = GetBase()
    if len(base_ans) > K:
        return []

    reverse_ans = GetReverse()

    return sorted(list(set(base_ans) & set(reverse_ans)))


N, K, C = inpl()
S = list(input().strip())

ans = solve()

for a in ans:
    print(a + 1)

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

wc = 0
arr = ["x"] * N
arr2 = ["x"] * N
cur = 0

while cur < N:
    if S[cur] == "x":
        cur += 1
        continue
    wc += 1
    arr[cur] = wc
    cur += C + 1

cur = N - 1
wc = K + 1
while cur >= 0:
    if S[cur] == "x":
        cur -= 1
        continue
    wc -= 1
    arr2[cur] = wc
    cur -= C + 1

for i, (a, b) in enumerate(zip(arr, arr2)):
    if a == b and a != "x":
        print(i + 1)

Solution (Python):
from collections import deque

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

last = deque()
pre = -C - 1
for i, s in enumerate(reversed(S)):
  if i > pre + C and s == 'o':
    last.appendleft(N - 1 - i)
    pre = i
    if len(last) == K:
      break

count = 0
pre = -C - 1
x = last.popleft()
for i, s in enumerate(S):
  if i > pre + C and s == 'o':
    count += 1
    while x < i:
      x = last.popleft()
    if x == i and count + len(last) == K:
      print(i + 1)
    pre = i
    if count == K:
      break

Solution (Python):
def main():
    n,k,c=map(int,input().split())
    S=input()
    l1=[[0,0] for _ in range(n)]
    l2=[0]*n
    memo=[0]*n
    x=0
    for i in range(n):
        if S[i]=="o" and memo[i]==0:
            x+=1
            l1[i][0]=x
            l1[i][1]=i+c+1
            for j in range(i,i+c+1):
                if j<n:
                    memo[j]=1
        elif S[i]=="o" and memo[i]==1:
            l1[i][0]=x
            l1[i][1]=l1[i-1][1]
        elif S[i]=="x" and memo[i]==0:
            l1[i][0]=x
            l1[i][1]=i+1
        else:
            l1[i][0]=x
            l1[i][1]=l1[i-1][1]
    S_=S[::-1]
    memo=[0]*n
    x=0
    for i in range(n):
        if S_[i]=="o" and memo[i]==0:
            x+=1
            l2[i]=x
            for j in range(i,i+c+1):
                if j<n:
                    memo[j]=1
        else:
            l2[i]=x
    l2=l2[::-1]
    ans=0
    for i in range(n):
        if S[i]=="o":
            x=0
            if i!=0:
                x+=l1[i-1][0]
            if i==0 and n!=1:
                x+=l2[1]
            else:
                if l1[i-1][1]<n and i<n-1:
                    x+=l2[max(l1[i-1][1],i+1)]
            if x<k:
                print(i+1)
if __name__ == '__main__':
    main()

Solution (Python):
n,k,c=map(int,input().split())
s=input()
l=len(s)
cand=[]
for i in range(l):
  if s[i]=='o':
    cand.append(i)
if len(cand)==k:
  for val in cand:
    print(val+1)
else:
  cnt1=[0]*n
  cnt2=[0]*n
  prev=0
  cnt=0
  for i in range(l):
    if s[i]=='o' and i>=prev:
      cnt+=1
      cnt1[i]=cnt
      prev=i+(c+1)
    else:
      cnt1[i]=cnt
  prev=l-1
  cnt=0
  for i in range(l-1,-1,-1):
    if s[i]=='o' and i<=prev:
      cnt+=1
      cnt2[i]=cnt
      prev=i-(c+1)
    else:
      cnt2[i]=cnt
  ans=[]
  for i in range(len(cand)):
    if i==0:
      if cnt2[cand[i]+1]<k:
        ans.append(cand[i]+1)
    elif i==len(cand)-1:
      if cnt1[cand[i]-1]<k:
        ans.append(cand[i]+1)
    else:
      if cnt1[cand[i]-1]+cnt2[cand[i]+1]<k:
        ans.append(cand[i]+1)
  for val in ans:
    print(val)

Solution (Python):
import sys
n, k, c = [int(x) for x in input().split()]
s = input()
counts = [[0] * 2 for i in range(n)]
for i in range(n):
    if s[i] == 'x':
        if i > 0:
            counts[i] = [max(counts[i - 1]), 0]
        else:
            counts[0]= [0, 0]
        continue
    if i == 0:
        counts[0]= [0, 1]
    elif i <= c:
        counts[i] = [max(counts[i - 1]), 1]
    else:
        counts[i] = [max(counts[i - 1]), max(counts[i - c - 1]) + 1]
r = []
checkk = k
nextgap = n
for i in range(n - 1, -1, -1):
    if i < nextgap and counts[i][1] >= checkk:
        if counts[i][0] < checkk:
            r.append(i + 1)
        checkk -= 1
        if checkk == 0:
            break
        nextgap = i - c
for i in range(len(r) - 1, -1, -1):
    print(r[i])

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)
    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]:
            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 = list(input())
os = 0
for ss in s:
    if ss == 'o':
        os += 1
s2 = list(reversed(s))

if c == 0 and os > k:
    exit(0)

def calc(s):
    global n, k, c
    answer = set()
    pre = None
    for idx, i in enumerate(s):
        if i == 'o' and (pre is None or idx > pre + c):
            answer.add(idx + 1)
            
            pre = idx
        if len(answer) >= k:
            return answer

answer1 = calc(s)
answer2 = calc(s2)
answer2 = set(map(lambda x: len(s2) - x + 1, answer2))

for i in sorted(list(answer1 & answer2)):
    print(i)

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

ANS = [0] * n
A = [0] * n
B = []
NX = [10**8] * n
kk = k
for i in range(n):
    if kk == 0:
        break
    if s[i] == "o" and (len(B) == 0 or i > B[-1]+c):
        A[i] = 1
        ANS[i] = 1
        B.append(i)
        kk -= 1

nx = 10**8
for i in range(n-1,-1,-1):
    if A[i] == 1:
        nx = i
    NX[i] = nx




bf = 10**8
nx = 10**8
for i in range(n-1,-1,-1):
    
    if A[i] == 1:
        nx = i
    if s[i] == "o" and A[i] == 0 and nx-i > c:
        
        nx = i
        bf = min(bf, i) - 1
        
        while bf >= 0 and A[bf] == 0:
            bf -= 1
        
        if bf >= 0:
            A[bf] = 0
            ANS[bf] = 0
            A[i] = 1
        


for i in range(len(ANS)):
    if ANS[i] == 1:
        print(i+1)

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):
N, K, C = map(int, input().split())
S = [c == "o" for c in input().strip()]

prev = -C - 1
count = 0
work_l = []
for i, c in enumerate(S):
	if c:
		if i > prev + C:
			count += 1
			prev = i
			work_l.append(i)

prev = -C - 1
count = 0
work_r = []
for i, c in enumerate(reversed(S)):
	if c:
		if i > prev + C:
			count += 1
			prev = i
			work_r.append(N - 1 - i)

work_r.reverse()

if len(work_l) == K and len(work_l) == len(work_r):
	for l, r in zip(work_l, work_r):
		if l == r:
			print(l + 1)

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

l = [0 for _ in range(n + 1)]
prev = -c
for i in range(1, n + 1):
    l[i] = l[i - 1]
    if prev + c < i and s[i - 1] == 'o':
        l[i] += 1
        prev = i
r = [0 for _ in range(n + 1)]
prev = n + c
for i in range(n - 1, -1, -1):
    r[i] = r[i + 1]
    if i < prev - c and s[i] == 'o':
        r[i] += 1
        prev = i
cnt = [1 if c == 'o' else 0 for c in s]
for i in range(n):
    if 0 < i - c:
        cnt[i] += l[i - c]
    if i + c + 1 < n + 1:
        cnt[i] += r[i + c + 1]
ans = [s[i] == 'o' and cnt[i] == k for i in range(n)]
prev = -c - 1
for i in range(n):
    if s[i] == 'o' and cnt[i] == k:
        if i <= prev + c:
            ans[i] = False
        prev = i
prev = n + c + 1
for i in range(n - 1, -1, -1):
    if s[i] == 'o' and cnt[i] == k:
        if prev - c <= i:
            ans[i] = False
        prev = i
for i in range(n):
    if ans[i]:
        print(i + 1)

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

HAYAI = []
OSOI = []

now = 0
c = 0
while now < N and c<K:
    if S[now]=='o':
        HAYAI.append(now)
        now += C+1
        c += 1
    else:
        now += 1
        
SS = S[::-1]
now = 0
c = 0
while now < N and c<K:
    if SS[now]=='o':
        OSOI.append(N-now-1)
        now += C+1
        c += 1
    else:
        now += 1

OSOI = OSOI[::-1]

for i in range(K):
  if HAYAI[i]==OSOI[i]:
    print(HAYAI[i]+1)

Solution (Python):
def get_max(ar, c):
    cnt = 0
    rtn = []
    rest = 0
    for a in ar:
        if a == "o" and rest <= 0:
            cnt += 1
            rest = c
        else:
            rest -= 1
        rtn.append(cnt)
    return rtn


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

from_start = get_max(s, c)
from_last = get_max(s[::-1], c)[::-1]
for i in range(n):
    aa = 0 if i == 0 else from_start[i - 1]
    aaa = from_start[i]
    bb = 0 if i == n - 1 else from_last[i + 1]
    bbb = from_last[i]
    if aaa == aa + 1 and bbb == bb + 1 and aaa + bb == k:
        print(i + 1)

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

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

c = 0
p = -1
for i in range(N):
  if S[i]=="o":
    if c+(T1[i+1] if i+1<N else 0)<K:
      print i+1
    if p==-1 or p+C<i:
      c += 1
      p = i

Solution (Python):
import sys
input=sys.stdin.readline
n,k,c=map(int,input().split())
s=input().rstrip()
nc=[0]*n
co=0
d=c+1
for i in range(n):
    if s[i]=='x':
        d+=1
    else:
        if d>=c:
            d=0
            co+=1
            nc[i]+=1
        else:
            d+=1
    if co==k:
        break
sn=list(s)
sn.reverse()
co=0
d=c+1
for i in range(n):
    if sn[i]=='x':
        d+=1
    else:
        if d>=c:
            d=0
            co+=1
            nc[n-1-i]+=1
        else:
            d+=1
    if co==k:
        break
co=0
da=c+1
db=c+1
for i in range(n):
    if s[i]=='x':
        da+=1
    else:
        if da>=c:
            da=0
            co+=1
            nc[i]+=1
        else:
            da+=1
    if co==k:
        break
    if sn[i]=='x':
        db+=1
    else:
        if db>=c:
            db=0
            co+=1
            nc[n-1-i]+=1
        else:
            db+=1
    if co==k:
        break
for i in range(n):
    if nc[i]==3:
        print(i+1)