- 19

## Statement

## Goal

Rossi is a cute chibi devil who rolls giant dice, arranged on a grid, by walking across the top of them.Your goal is to help Rossi solve the puzzle with the minimum number of die rolls.

The puzzle is solved when the following two conditions hold true:

- The value of each die is 6, i.e. they all have 6 pips showing on the

- All dice form a single connected group.

==============================

Moving around

==============================

- Rossi's position is on top of the

**last die he moved**. If he hasn't moved yet, he's on top of the

**first die of the list**.

- Dice form a group when they are standing adjacent to one another. Diagonals do not count.

- Rossi can walk freely between dice in the same group. Walking is not counted against the solution's length.

- The map is always a

==============================

Rolling dice

==============================

- If there is a free grid space from Rossi's standing position on a die, he can roll the die there. Since he can walk freely among the group, he can thus roll any "free" die within the group boundary.

- When a die is rolled, one of its bottom edges (the one between the old and new position) stays still, causing it to

**tumble and 'roll' in the relevant direction**.

- Therefore rolling a die can

**change where the number 6 face is**.

For example, if the die is rolled to the

**RIGHT**and the 6 face was

- Rolling a die adds one to the solution's length.

- We're only interested in the 6 faces' ending position, so you only need to track that face on each die.

- Each time Rossi rolls a die, output the position of that die and the direction in which it was rolled to to STDOUT.

==============================

==============================

Some dice are made of

- Rossi cannot roll

- Their 6 face is always on

==============================

Output to STDOUT

==============================

You must find the shortest solution to the puzzle. The puzzles are designed so that there is always only one "shortest" solution.

- The shortest solution is based on the

**number of times a die was rolled**.

Try checking the test cases with real dice if you are confused! :)

Input

**Line 1:**An integer

`N`, the number of dice on the 4 x 4 board.

**Next**

`N`lines:`x`,

`y`and

`face`, separated with spaces.

`x`and

`y`are a die's position, with

`x`increasing

`y`

`face`is either the relative position of that die's 6 face

Output

The shortest possible solution to the puzzle - a list of the die rolls that were performed by Rossi,

LEFT , RIGHT , UP or DOWN

**one roll per line with the following format:**`id``direction`— separated with spaces.`id`is the identifier number of the die being rolled. The dice are 0-indexed by their ordering in the input, so`id`ranges from 0 to`N`- 1.`direction`is the direction in which it was rolled:Constraints

2 ≤

0 ≤

0 ≤

There is a single shortest possible solution to the puzzle.

`N`≤ 150 ≤

`x`≤ 30 ≤

`y`≤ 3There is a single shortest possible solution to the puzzle.

Example

Input

2 0 0 WEST 2 0 TOP

Output

0 RIGHT

A higher resolution is required to access the IDE

Online Participants

### Channels

### Direct Messages

No private conversations