Luka

Interview

Time limit1sMemory limit128 MB

Summary

Simulate a walker's path on a grid and output every time step when the walker is within Chebyshev distance 1 of a fixed point.

Level: Easy3 of 10
Topics: Simulation, Array
Solved: No attempts yet

Problem

Luka arrived ten days before the national competition to gather hints about the problems. He knows that the problem setters take a daily walk through the town of Cres, quietly discussing the problems as they go.

Cres can be represented as a plane coordinate grid. The problem setters start their walk at (0, 0), and on each turn they move one unit in one of four directions. Moving right increases the x-coordinate by 1, moving up increases the y-coordinate by 1, and they may also move left or down.

Luka stands at point (X, Y) on the grid. He can hear part of the conversation only when the problem setters are at Luka's position or at one of the eight grid positions adjacent to Luka.

Write a program that finds every time when Luka could hear the conversation. The starting position before any move is time 0, and the moment immediately after the i-th move is time i.

Input

The first line contains two integers X and Y, Luka's position. -10000 ≤ X, Y ≤ 10000.

The second line contains an integer K. 1 ≤ K ≤ 100000.

The third line contains a string of length K describing the route taken that day. Each character is one of the following:

I: move east, or one unit to the right
S: move north, or one unit up
Z: move west, or one unit to the left
J: move south, or one unit down

Output

Print every time when Luka could hear the conversation, in strictly increasing order. Print one time per line.

If Luka could not hear the conversation at any time, print -1 on the first and only line.

Examples3

Example 1
Input
```
2 2
3
III
```
Expected output
```
-1
```
Example 2
Input
```
0 1
3
IJI
```
Expected output
```
0
1
```
Example 3
Input
```
-1 0
8
JJZZSSIS
```
Expected output
```
0
1
5
6
7
8
```