Spies

Luka wants to overhear the problem setters so he can learn hints about the contest tasks. The setters walk through the town of Cres every day while quietly discussing the tasks. Luka has placed a spy network of relatives and friends throughout the town.

The town of Cres can be represented as a coordinate grid. The setters start walking at coordinate (0, 0). On each move, they go one unit in one of four directions.

• I: east, increasing the x-coordinate by 1.
• S: north, increasing the y-coordinate by 1.
• Z: west, decreasing the x-coordinate by 1.
• J: south, decreasing the y-coordinate by 1.

Each spy stands at a fixed coordinate. At any moment, a spy can hear the conversation if the spy is at the setters' current coordinate or at one of the eight adjacent coordinates, meaning both the horizontal and vertical differences are at most 1. The starting coordinate (0, 0) is also included as a position occupied by the setters.

Spies are numbered 1, 2, ..., N in input order. Determine which spies heard the conversation.

The first line contains the number of spies N. 1 <= N <= 1000.

Each of the next N lines contains two integers X and Y, separated by one space, giving a spy's coordinate. -10000 <= X, Y <= 10000.

The next line contains the number of moves K. 1 <= K <= 100000.

The last line contains a string of length K. Each character is one of I, S, Z, and J, describing the route taken that day.

Print the numbers of all spies who heard the conversation, in increasing order, one per line.

If no spy heard the conversation, print only -1.