Problem E
Farmer's Field
Taeko Okajima is helping her relatives with their safflower field. She needs your help eliminating weeds from the safflower field. Her field is arranged in a $1$ dimensional line of units, where each unit is either a safflower crop, empty space, or weed, denoted by $C$, $S$ and $W$ respectively. The first and last units are crops.
Taeko has herbicides, which kills all crops and weeds within a radius $r$ of the location it is sprayed. Specifically if herbicide is sprayed at some location $i$, then all crops and weeds between $i+r$ and $i-r$ inclusive are killed. Taeko has an infinite amount of herbicide, so she can spray at as many locations as she wants.
Your task is to inform Taeko whether it is possible to kill all weeds without killing any of the safflower crops. Output a single string “POSSIBLE” or “IMPOSSIBLE”.
Input
The first line contains a single integer $n \: (1 \leq n \leq 10^5)$, the number of units in the field. The second line contains a single length $n$ string that represents Taeko’s safflower field. This field consists of $C$, $S$, and $W$, representing a crop $C$, empty space $S$, or weed $W$, respectively. The third line contains a single integer $r \: ( 1\leq r \leq \lfloor \frac{n - 1}{2} \rfloor )$, which represents the radius of the herbicide.
Output
Output a single string “POSSIBLE” or “IMPOSSIBLE”. Output “POSSIBLE” if it is possible to kill all weeds without killing any of the safflower crops. Output “IMPOSSIBLE” otherwise.
| Sample Input 1 | Sample Output 1 |
|---|---|
25 CCCCSWSSSCSSSWSSSCCSSSWSC 2 |
POSSIBLE |
| Sample Input 2 | Sample Output 2 |
|---|---|
24 CCCSSWSCCSSSWSSSWWSCSWCC 2 |
IMPOSSIBLE |
