Yutori

AtCoder

IDabc161_e

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

11 3 2
ooxxxoxxxoo

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$.

Input #2

5 2 3
ooxoo

Output #2

1
5

There is only one possible choice for his workdays: Day $1,5$.

Input #3

5 1 0
ooooo

Output #3

There may be no days on which he is bound to work.

Input #4

16 4 3
ooxxoxoxxxoxoxxo

Output #4

11
16

API Response (JSON)

{
  "problem": {
    "name": "Yutori",
    "description": {
      "content": "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: *   Aft",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc161_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Takahashi has decided to work on $K$ days of his choice from the $N$ days starting with tomorrow.\nYou are given an integer $C$ and a string $S$. Takahashi will choose his workdays as follows:\n\n*   Aft...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments