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



Sample input:
11 3 2
ooxxxoxxxoo


Sample output:
6

Submission status: Runtime Error

Solution code:
#pragma GCC optimize("O3", "unroll-loops")
//#pragma GCC target("avx2")
#pragma optimize("fast-math")

#include <bits/stdc++.h>
#include <stdio.h>

using namespace std;
#define endl '\n'
#define ull unsigned long long
#define si short int
#define ll long long
#define ld long double
#define pb push_back
#define pii pair<int, int>
#define pdd pair<double, double>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define piii pair<pair<int, int>, int>
#define all(vec) (vec).begin(), (vec).end()
#define piiii pair<pair<int, int>, pair<int, int>>
#define fr(a, from, c) for(int a=(from); (a)<(c); (a)++)

/*-----------------------------------------------------SegTree---------------------------------------------*/
int mux(int a, int b) {
    if (a > b) return a;
    return b;
}

int mun(int a, int b) {
    if (a < b) return a;
    return b;
}

int mxn11 = (int) (6e5 + 2);
vector<int> t(4 * mxn11 + 1, 0);
vector<int> tAdd(4 * mxn11 + 1, 0);

void build(int v, int vl, int vr) {
    if (vl == vr) {
        t[v] = vl;
    } else {
        int tmp = (vl + vr) >> 1;
        build((v << 1), vl, tmp);
        build((v << 1) + 1, tmp + 1, vr);
        t[v] = 0;
    }
}

void push(int v){
    tAdd[2*v]+=tAdd[v];
    tAdd[2*v+1]+=tAdd[v];
    t[v]+=tAdd[v];
    tAdd[v]=0;
}
int get(int v, int vl, int vr, int l, int r) {
    if (l > r) return 0;
    if (vl == l && vr == r) {
        return t[v]+tAdd[v];
    }
    int tmp = (vl + vr) >> 1;
    push(v);
    int a = get(v << 1, vl, tmp, l, mun(tmp, r));
    int b = get((v << 1) + 1, tmp + 1, vr, mux(tmp + 1, l), r);
    return a+b;
}

void update(int v, int vl, int vr, int l, int r, int x){
    if(l>r) return;
    if(vl==l && vr==r){
        tAdd[v]+=x;
        return;
    }
    int tmp=(vl+vr)/2;
    push(v);
    update(2*v, vl, tmp, l, min(r, tmp), x);
    update(2*v+1, tmp+1, vr, max(l, tmp+1), r, x);
    t[v] = t[2 * v] + tAdd[2 * v] + t[2 * v + 1] + tAdd[2 * v + 1];
}


/*-----------------------------------------------------SegTree---------------------------------------------*/
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

/*-----------------------------------------------------OperatorsOverloaded---------------------------------*/
template<typename T, typename U>
ostream &operator<<(ostream &o, pair<T, U> p) {
    o << p.first << " " << p.second << endl;
    return o;
}

template<typename T>
istream &operator>>(istream &o, vector<T> &arr) {
    for (int i = 0; i < arr.size(); i++) o >> arr[i];
    return o;
}

template<typename T>
ostream &operator<<(ostream &o, vector<T> &arr) {
    for (int i = 0; i < arr.size(); i++) o << arr[i] << " ";
    o << endl;
    return o;
}
/*-----------------------------------------------------OperatorsOverloaded---------------------------------*/
/*#ifdef ALLOC_LOCAL
const int ML_ = 450;
char mem_[ML_ * 1024 * 1024];
size_t _ptr = 0, _magic = 21323400;
void * operator new(size_t cnt) { if (_ptr + cnt < sizeof mem_) { _ptr += cnt; return  mem_ + _ptr - cnt; } else { assert(false);  _ptr = cnt + _magic; return mem_ + _magic; } }
void operator delete(void *) {}
#endif //ALLOC_LOCAL*/

/*-----------------------------------------------------MATH------------------------------------------------*/
inline ll gcd(ll a, ll b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

inline ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }


inline ll gcdex(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll xx, yy;
    ll gc = gcdex(b, a % b, yy, xx);
    x = xx;
    y = yy - (a / b) * xx;
    return gc;
}

inline ll pwm(ll xx, ll pow, ll MD) {
    if (pow < 0) { pow = pow % (MD - 1) + MD - 1; }
    ll mlt = 1;
    while (pow) {
        if (pow & 1) {
            mlt *= xx;
            mlt %= MD;
        }
        xx *= xx;
        pow >>= 1;
        xx %= MD;
    }
    return mlt;
}

inline int inv(ll r, int _mod) { return pwm(r % _mod, _mod - 2, _mod); }

inline int64_t hilbertOrder(int x, int y, int pow, int rotate) {
    if (pow == 0) {
        return 0;
    }
    int hpow = 1 << (pow - 1);
    int seg = (x < hpow) ? (
            (y < hpow) ? 0 : 3
    ) : (
                      (y < hpow) ? 1 : 2
              );
    seg = (seg + rotate) & 3;
    const int rotateDelta[4] = {3, 0, 0, 1};
    int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
    int nrot = (rotate + rotateDelta[seg]) & 3;
    int64_t subSquareSize = int64_t(1) << (2 * pow - 2);
    int64_t ans = seg * subSquareSize;
    int64_t add = hilbertOrder(nx, ny, pow - 1, nrot);
    ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
    return ans;
}

/*-----------------------------------------------------MATH------------------------------------------------*/
const int mxn=6e5+10;
int dpleft[mxn];
int dpright[mxn];
void solve(){
    int n,k,c;
    cin>>n>>k>>c;
    string t;
    cin>>t;
    string s=string(c+10, 'x')+t+string(c+10,'x');
    //cout<<s<<endl;
    n=s.size();
    if(c==0){
        int ind=-1;
        int hto=0;
        for(int i=0;i<s.size();i++){
            hto+=(s[i]=='o');
        }
        if(hto==k){
            for(int i=0;i<s.size();i++){
                if(s[i]=='o') {
                    cout<<i-(c+10)+1<<endl;
                    //cout<<i<<endl;
                }
            }
            return;
        }
        else {
            cout<<endl;
            return;
        }
    }
    for(int i=c+10;i<n;i++){
        dpleft[i]=max(dpleft[i-1], ((i-c-1>=0)?dpleft[i-c-1]:0) +(s[i]=='o'));
    }
    for(int i=n-(c+10)-1;i>=0;i--){
        dpright[i]=max(dpright[i+1], ((i+c+1<n)?dpright[i+c+1]:0) +(s[i]=='o'));
    }
   /* for(int i=c+10;i<n-(c+10);i++) cout<<dpright[i]<<" ";
    cout<<endl;
    for(int i=c+10;i<n-(c+10);i++) cout<<dpleft[i]<<" ";
    cout<<endl;*/
    for(int i=1, j=i+c;j<n;j++, i++){
        if(dpleft[i-1]+dpright[j]>=k){
            update(1,0,n-1, i,j-1, 1);
        }
    }
    for(int i=c+10;i<n;i++){
        int a=get(1,0,n-1,i, i);
        if(a==0 && s[i]!='x'){
            cout<<i-(c+10)+1<<endl;
        }
    }
}



void testcases(int n) {
    n = 1 - n;
    if (!n) cin >> n;
    for (int i = 0; i < n; i++) {
        solve();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    //freopen("C:\\Users\\Maximus\\CLionProjects\\Codeforces\\BestTeam\\output.txt", "r", stdin);
    //f=fopen("C:\\Users\\Maximus\\CLionProjects\\Codeforces\\BestTeam\\output.txt", "w");
    //freopen("C:\\Users\\Maximus\\CLionProjects\\Codeforces\\BestTeam\\output.txt", "w", stdout);

    unsigned int beg_time = clock();
    testcases(0);
    // 0 - no t, 1 - with t

    unsigned int end_time = clock();
    //cout << endl << endl << end_time - beg_time;
    return 0;
}

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
n, k, c = map(int, input().split())
s = input()

if c == 0:
    if s.cnt("o") == k:
        print(*range(1, n + 1), sep="\n")
    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)

Submission status: Runtime Error

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

res = []

def DFS(res, cur, i, rest):
  #print(res, cur, i, rest)
  if len(cur) == K:
    res.append(cur)
    return
  if i >= N:
    return
  if S[i] == 'o' and rest <= 0:
    DFS(res, cur + [i], i + 1, C)
  DFS(res, cur, i + 1, rest - 1)

DFS(res, [], 0, 0)

if not res:
  exit()

for e in res[0]:
  if all([e in l for l in res]):
    print(e + 1)

Submission status: Runtime Error

Solution code:
for i in range(N):
    if s[i]=='o':
        si=copy.copy(s)
        si[i]='x'
        day=N
        count=0
        flag=False
        while day>K-1 and count<K:
            if si[day-1]=='x':
                day-=1
            else:
                count+=1
                day-=C+1
                if count==K:
                    flag=True
        if flag==False:
            print(i+1)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
N,K,C = list(map(int,input().split()))
S = input()
work = []

def judge(k,SS):
    for id,i in enumerate(SS):
        if i == "o":
            if id+C<len(SS):
                print(k)
                if judge(k-1,SS[id+C:]): break
    if k==0: return True


for a in range(N):
    SS = S[:a]+"x"+S[a+1:]
    if a >= C: 
        SS = SS[:a-C] + "xx" +SS[a:]
    if a <= N-C: 
        SS = SS[:a] + "xx" +SS[a+C:] 
    if a == 1: SS = "x" +  SS[1:] 
    if a == N-2: SS = SS[:N-1] + "x" 
    #もしダメならば
    print(SS)
    if judge(K-1,SS):
        work.append(a)
for a in work:
    print(a+1)

Submission status: Runtime Error

Solution code:
n, k, c = map(int, input().split())
S = input()
pre = [0]*n
pre[0] = 1 if S[0] == "o" else 0
for i in range(1, n):
    if S[i] == "o" and i-c-1 >= 0:
        pre[i] = max(pre[i-1], pre[i-c-1]+1)
    else:
        pre[i] = pre[i-1]

suf = [0]*n
suf[-1] = 1 if S[-1] == "o" else 0
for i in range(n-2, -1, -1):
    if S[i] == "o" and i+c+1 < n:
        suf[i] = max(suf[i+1], suf[i+c+1]+1)
    else:
        suf[i] = suf[i+1]

# print(pre)
# print(suf)

if S[0] == "o" and suf[1] < k:
    print(1)

for i in range(1, n-1):
    if S[i] == "o" and pre[i-1]+suf[i+1] < k:
        print(i+1)

if S[-1] == "o" and pre[-2] < k:
    print(n)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

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()
t = []
for i in range(n):
    if s[i] == 'o':
        t.append(1)
    else:
        t.append(0)

r = [False]*n
l = [False]*n
flag = True
for i in range(n):
    if flag and t[i] == 1:
        flag = False
        l[i] = True
        cnt = 0
        continue
    elif not flag and cnt == c-1:
        flag = True
    cnt += 1

flag = True
for i in range(n)[::-1]:
    if flag and t[i] == 1:
        flag = False
        r[i] = True
        cnt = 0
        continue
    elif not flag and cnt == c-1:
        flag = True
    cnt += 1

for i in range(n):
    if r[i] and l[i]:
        print(i+1)

Submission status: Runtime Error

Solution code:
from itertools import combinations

n, k, c = list(map(int, input().split()))
inp = input()
if c <= 0 or k <= 0:
    print()
else:
    # cond
    s = [i+1 for i, x in enumerate(inp) if x == 'o']
    # print(s)
    allset = set(s)
    # print(allset)
    if len(s) <= 0:
        print()
    else:
        # cond
        
        for l in combinations(s, k): 
            for i, j in zip(l[:-1], l[1:]):
                # print(j - i)
                isOk = True
                if j - i <= c:
                    isOk = False
                    # print("break")
                    break
            if isOk:    
                allset.intersection_update(set(l))
                # print(allset)
            if len(allset) <= 0:
                break
        if len(allset) > 0:
            for x in sorted(allset):
                print(x)
        else:
            print()

Submission status: Runtime Error

Solution code:
N, K, C = map(int, raw_input().split())
S = raw_input()
#N, K, C = 16, 16, 1
#S = "ooxxoxoxxxoxoxxo"

workCnt = [0]*(N+1)
res = []
def work(KK, CC, SS, pos, NN):
    if KK <= 0:
        for p in res:
            workCnt[p] = workCnt[p] + 1
        return 1

    if pos >= NN:
        return 0

    #work ok
    cnt = 0
    if SS[pos] == 'o':
        res.append(pos)
        cnt = cnt + work(KK-1, CC, SS, pos+CC, NN)
        res.pop()

    #for ii in range(pos + 1, NN):
    cnt = cnt + work(KK, CC, SS, pos+1, NN)

    return cnt


total = work(K, C+1, S, 0, N)
if total > 0:
    for i in range(N):
        if workCnt[i] >= total:
            print(i+1)

Submission status: Runtime Error

Solution code:
def getlist_pattern( offset, rstr, N, step ):
  aap = []
  if(N<=0):
    return aap
  
  for i,ch in enumerate(rstr):
    if( ch == "o" ):
      ap = getlist_pattern( offset+i+step, rstr[i+step:], N-1,step )
      
      if( ap==[] ):
        ap = [[offset+i]]
      else:
      	for j in range(len(ap)):
          ap[j].append(offset+i)
      aap.extend(ap)
  return aap    

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

vstr = input()

pp = getlist_pattern( 0, vstr, k, 2 )


for p in pp:
  if(len(p) == k):
    base = p
    break

base.sort()

for ind in base:
  err_flag = 0
  for p in pp:
    if(len(p) == k):
      if( not( ind in p )):
        err_flag = 1
        break
  if( err_flag==0):
  	print( ind+1 )

Submission status: Runtime Error

Solution code:
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 += 3
  i += 1
i = len(S)-1
num = 0
while num < K:
  if S[i] == "o":
    B.append(i)
    num+=1
    i -= 3
  i -= 1
B.sort()

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

Submission status: Runtime Error

Solution code:
from itertools import combinations

n, k, c = list(map(int, input().split()))
inp = input()
if c <= 0 or k <= 0:
    print()
else:
    # cond
    s = [i+1 for i, x in enumerate(inp) if x == 'o']
    # print(s)
    allset = set(s)
    # print(allset)
    if len(s) <= 0:
        print()
    else:
        # cond
        
        for l in combinations(s, k): 
            for i, j in zip(l[:-1], l[1:]):
                # print(j - i)
                isOk = True
                if j - i <= c:
                    isOk = False
                    # print("break")
                    break
            if isOk:    
                allset.intersection_update(set(l))
                # print(allset)
            if len(allSet) <= 0:
                break
        if len(allset) > 0:
            for x in sorted(allset):
                print(x)
        else:
            print()

Submission status: Runtime Error

Solution code:
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]
    #print(ll)
    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]
    #print(rr)
    ans=[]
    if 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-2>=0 and ll[n-2]<k:ans.append(n)
    print(*ans,sep="\n")

main()

Submission status: Runtime Error

Solution code:
from itertools import combinations

n, k, c = list(map(int, input().split()))
inp = input()
if c <= 0 or k <= 0:
    print()
else:
    # cond
    s = [i+1 for i, x in enumerate(inp) if x == 'o']
    # print(s)
    allset = set(s)
    # print(allset)
    if len(s) <= 0:
        print()
    else:
        # cond
        
        for l in combinations(s, k): 
            for i, j in zip(l[:-1], l[1:]):
                # print(j - i)
                isOk = True
                if j - i <= c:
                    isOk = False
                    # print("break")
                    break
            if isOk:    
                allset.intersection_update(set(l))
                # print(allset)
        if len(allset) > 0:
            for x in sorted(allset):
                print(x)
        else:
            print()

Submission status: Runtime Error

Solution code:
N,K,C =map(int,input().rstrip().split(" "))
S = input()
kinmu = 0
niti = 0
f = []
b = []
for i in range(N):
  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)

Submission status: Runtime Error

Solution code:
N, K, C = map(int, raw_input().split())
S = raw_input()
#N, K, C = 16, 4, 3
#S = "ooxxoxoxxxoxoxxo"

workCnt = [0]*(N+1)
res = []
def work(KK, CC, SS, pos, NN):
    if KK <= 0:
        for p in res:
            workCnt[p] = workCnt[p] + 1
        return 1

    if pos >= NN:
        return 0

    #work ok
    cnt = 0
    if SS[pos] == 'o':
        res.append(pos)
        cnt = cnt + work(KK-1, CC, SS, pos+CC, NN)
        res.pop()

    #for ii in range(pos + 1, NN):
    cnt = cnt + work(KK, CC, SS, pos+1, NN)

    return cnt


total = work(K, C+1, S, 0, N)
for i in range(N):
    if workCnt[i] >= total:
        print(i+1)

Submission status: Runtime Error

Solution code:
N,K,C = map(int,(input().split()))
S = list(input())
ol = []
ans = []
for i in range(N):
    if S[i] == "o":
        ol.append(i)

for i in ol:
    if i != ol[0]:
        now = ol[0]
    else:
        if len(ol)>1:
            now = ol[1]
    c = 1
    for j in ol:
        if j > now+C:
            if j != i:
                now = j
                c += 1
        if c >= K:
            break
    if c < K:
        ans.append(i) 
for i in ans:
    print(i+1)

Submission status: Runtime Error

Solution code:
// #include "pch.h"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <limits.h>
#include <string>
#include <stack>
#include <deque>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <time.h>
#include <cassert>
#include <fstream>
#include <stdio.h>
#include<unordered_map>

typedef long long ll;
typedef std::pair<int, int> Pii;
typedef std::pair<long long, long long> Pll;
typedef std::pair<double, double> Pdd;

#define rip(i, n, s) for (int i = (s);i < (int)( n ); i++)
#define mapa make_pair
#define all(a) a.begin(), a.end()
#define MM << " " <<

template<typename T>
using MaxHeap = std::priority_queue<T>;
template<typename T>
using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template<typename T>
inline bool chmax(T &a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
template<typename T>
inline bool chmin(T &a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}

template<typename T>
std::vector<T> vec(int len, T elem) { return std::vector<T>(len, elem); }
template<typename T>
void vdeb(std::vector<T> &da) {
	for (int i = 0;i < da.size();i++) {
		if (i == da.size() - 1) std::cout << da[i];
		else std::cout << da[i] << ' ';
	}
	std::cout << std::endl;
}
template<typename T>
void vdeb(std::vector<std::vector<T>> &da) {
	for (int i = 0;i < da.size();i++) vdeb(da[i]);
	std::cout << std::endl;
}

using namespace std;

int main(){
	int n,k,c; cin >> n >> k>> c;
	string s; cin >> s;
	if(c == 0){
		rip(i,n,0) if(s[i]=='o') k--;
		if(k < 0) return 0;
		rip(i,n,0){
			if(s[i] == 'o') printf("%d\n", i+1);
		}
		return 0;
	}
	vector<int> dp(n),dpp(n);
	dp[0] = 1;
	dpp[n-1] = 1;
	if(s[0] == 'x') dp[0] = 0;
	if(s[n-1] == 'x') dp[n-1] = 0;
	rip(i,n,1){
		dp[i] = dp[i-1];
		if(c < i && s[i] == 'o') chmax(dp[i], dp[i-c-1]+1);
		else chmax(dp[i], 1);
	}
	for(int i = n-2;i>-1;i--){
		dpp[i] = dpp[i+1];
		if(i+c+1 < n && s[i] == 'o') chmax(dpp[i], dpp[i+c+1]+1);
		else chmax(dpp[i], 1);
	}
	vector<int> ans(0);
	vector<int> su(n+1);
	rip(i,c+1,0){
		if(dpp[i] >= k) su[0]++, su[i]--;
	}
	rip(i,n-c-1,0){
		if(dp[i] + dpp[i+c+1] >=k) su[i+1]++, su[i+c+1]--;
	}
	rip(i,n,n-c-1){
		if(dp[i] >= k) su[n]--, su[i+1]++;
	}
	int ok= 0;
	rip(i,n,0){
		ok += su[i];
		if(ok == 0) ans.push_back(i+1);
	}
	// vdeb(dp);vdeb(dpp);vdeb(su);
	rip(i,ans.size(),0) printf("%d\n", ans[i]);
}

Submission status: Runtime Error

Solution code:
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)
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)

Submission status: Runtime Error

Solution code:
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:
                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()

Submission status: Runtime Error

Solution code:
N,K,C = map(int,(input().split()))
S = list(input())
ol = []
ans = []
for i in range(N):
    if S[i] == "o":
        ol.append(i)

for i in ol:
    if i != ol[0]:
        now = ol[0]
    else:
        now = ol[1]
    c = 1
    for j in ol:
        if j > now+C:
            if j != i:
                now = j
                c += 1
        if c >= K:
            break
    if c < K:
        ans.append(i) 
for i in ans:
    print(i+1)

Submission status: Runtime Error

Solution code:
N, K, skip = map(int, input().split(" "))
lazy = list(input())
skip_to = [None]*N
for i in range(N)[::-1] : 
    if lazy[i] == "o" :
        skip_to[i] = i
    else :
        if i == N-1 :
            continue
        skip_to[i] = skip_to[i+1]

must_work = [True]*N

def check (work_day, i, N, K, skip) :
    if not any(must_work) :
        return True
    if len(work_day) == K :
        m = 0
        for j in range(N) : 
            if m < K and j ==  work_day[m] : 
                must_work[j] = must_work[j] and True
                m += 1
            else :
                must_work[j] = False
        return False

    if i >= N :
        return False

    if lazy[i] == "x" :
        check(work_day, skip_to[i], N, K, skip)
    else :
        work_day.append(i)
        if check(work_day, i+skip, N, K, skip) :
            return True
        work_day.pop()
        
    if check(work_day, i+1, N, K, skip) :
        return True
    return False

for i in range(N) : 
    if check([], i, N, K, skip) :
        break 

for i in range(N) :
    if must_work[i] :
        print(i+1)

Submission status: Runtime Error

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

i_maru = [i for i in range(n) if s[i]=="o"]
n_maru=len(i_maru)

dp_left=[0]*n
dp_left[i_maru[0]]=1

last = i_maru[0]
for i in i_maru[1:]:
    if i-last > c:
        dp_left[i]=dp_left[last]+1
        last=i
    else:
        dp_left[i]=dp_left[last]
        
dp_right=[0]*n
dp_right[i_maru[-1]]=1

last = i_maru[-1]
for i in i_maru[:-1][::-1]:
    if last-i > c:
        dp_right[i]=dp_right[last]+1
        last=i
    else:
        dp_right[i]=dp_right[last]

if dp_right[i_maru[1]]<=c:
    print(i_maru[0]+1)
    

for i in range(1,n_maru-1):
    if i_maru[i+1]-i_maru[i-1]>c:
        hitsuyou = dp_left[i_maru[i-1]]+dp_right[i_maru[i+1]]
        if hitsuyou<=c:
            print(i_maru[i]+1)

        
if dp_left[i_maru[-2]]<=c:
    print(i_maru[-1]+1)

Submission status: Runtime Error

Solution code:
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 i-c-1>=0:
            if m=="o":ll[i]=ll[i-c-1]+1
            else:ll[i]=ll[i-1]
        else:
            if m=="o":ll[i]=1
            else:ll[i]=ll[i-1]
    #print(ll)
    for i in range(n-1,-1,-1):
        m=s[i]
        if i+c+1<n:
            if m=="o":rr[i]=rr[i+c+1]+1
            else:rr[i]=rr[i+1]
        else:
            if m=="o":rr[i]=1
            else:rr[i]=rr[(i+1)%n]
    #print(rr)
    ans=[]
    if 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 ll[n-2]<k:ans.append(n)
    print(*ans,sep="\n")

main()

Submission status: Runtime Error

Solution code:
from itertools import combinations

n, k, c = list(map(int, input().split()))
inp = input()
if c <= 0 or k <= 0:
    print()
else:
    # cond
    s = [i+1 for i, x in enumerate(inp) if x == 'o']
    # print(s)
    allset = set(s)
    if len(s) <= 0:
        print()
    else:
        # cond
        
        for l in combinations(s, k): :
            for i, j in zip(t[:-1], t[1:]):
                if j - i > c:
                    break
                else:
                    allset.intersection_update(set(l))
        if len(allset) > 0:
            for x in allset:
                print(x)
        else:
            print()

Submission status: Runtime Error

Solution code:
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())

dp = [0]*N
for i in range(N)[::-1]:
    if S[i]=='o':
        if i+C+1 >= N:
            dp[i] = 1
        else:
            dp[i] = max(dp[i+C+1]+1,dp[i+1])
    else:
        dp[i] = dp[i+1]

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

ans = []
if dp[1] < K:
    ans.append(1)

for i in range(1,N-1):
    if dp[i]+dpz[i]-1 >= K and dp[i+1]+dpz[i+1]-1 < K and dp[i-1]+dpz[i-1]-1 < K:
        ans.append(i+1)
if N >= 2:
    if dpz[N-2] < K:
        ans.append(N)

for a in ans:
    print(a)

Submission status: Runtime Error

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

i_maru = [i for i in range(n) if s[i]=="o"]
n_maru=len(i_maru)

dp_left=[0]*n
dp_left[i_maru[0]]=1

last = i_maru[0]
for i in i_maru[1:]:
    if i-last > c:
        dp_left[i]=dp_left[last]+1
        last=i
    else:
        dp_left[i]=dp_left[last]
        
dp_right=[0]*n
dp_right[i_maru[-1]]=1

last = i_maru[-1]
for i in i_maru[:-1][::-1]:
    print(i,last)
    if last-i > c:
        dp_right[i]=dp_right[last]+1
        last=i
    else:
        dp_right[i]=dp_right[last]

if dp_right[i_maru[1]]<=c:
    print(i_maru[0]+1)
    

for i in range(1,n_maru-1):
    print(i,i_maru[i-1],i_maru[i],i_maru[i+1])
    if i_maru[i+1]-i_maru[i-1]>c:
        hitsuyou = dp_left[i_maru[i-1]]+dp_right[i_maru[i+1]]
        if hitsuyou<=c:
            print(i_maru[i]+1)

        
if dp_left[i_maru[-2]]<=c:
    print(i_maru[-1]+1)

Submission status: Runtime Error

Solution code:
n,k,c= map(int, input().split())
s=input()
l=[]

for c in s.split("x"*c):
    count=0
    while i<len()
    if i=="o":