The Great Lever Challenge

Time limit20sMemory limit2048 MB

Summary

Given a maze and levers that move the robot along the x or y axis with a flipping direction, print the lever indices that take the robot from @ to $.

Level: Medium5 of 10
Topics: Simulation, BFS, Graph
Solved: No attempts yet

Problem

This is a problem with public tests.

Do you like puzzle games? You probably do! This problem is a special challenge.

A robot is stuck in a labyrinthine maze. Your job is to guide it from its starting position to the destination. The robot is controlled by levers, and each lever has properties that define how the robot moves through the maze.

Each lever has three attributes:

Length: the distance the robot travels when the lever is activated.
Dimension: the axis of movement, either the $x$ axis (horizontal) or the $y$ axis (vertical).
State: the direction of movement, either positive (+) or negative (-).

When you pull a lever, its state changes to the opposite state. Then the robot moves in the direction given by the new state. If the new state is positive, the robot moves the lever's length toward the positive end of its axis. If the new state is negative, the robot moves toward the negative end. Be careful: if the robot runs into a wall or the border of the maze, it stops, and it moves again only after the next lever activation.

Your task is to move the robot from the starting point to the finish.

There are only 10 levels. Complete all of them!

Input

The first line contains a single integer, the number of the current test. The next line contains two integers $n$ and $m$ ( $1 \leq n, m \leq 1000$ ), the number of rows and columns in the maze. The next line contains an integer $k$ ( $1 \leq k \leq 100$ ), the number of available levers.

Each lever is described on its own line in the format <len><dim><state>. Here <len> is an integer from 1 to 1000, <dim> is x or y, and <state> is - or +.

The next $n$ lines describe the maze with strings of $m$ characters:

# is a wall.
. is an empty cell.
@ is the starting position.
$ is the finishing position.

There is exactly one start and exactly one finish in each maze. Every test is guaranteed to be solvable.

The $Ox$ axis points from left to right, and the $Oy$ axis points from top to bottom.

Output

Print the lever indices in the order you pull them to move the robot from the starting position to the finish. Levers are numbered from 1 in the same order as the input.

The number of printed indices must not exceed $10^5$ . Every test is guaranteed to be solvable within this limit.

Examples1

Example 1

Input

1
10 10
2
2x-
2y-
@..#######
##..######
$.#..#####
#..#..####
##..#..###
###..#..##
####..#..#
#####..#.#
######...#
##########

Expected output

1 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1
2 2 1 1 2 2 1 2 1 1 2 2 1 1 2 2 1 1 2 2
1 1 2 2 1 1 2 2 1 1