## Girls Invitational '18 S2 - Amazing Maze

View as PDF

Points: 10
Time limit: 2.0s
Memory limit: 64M

Problem type

As a thank you gift for an amazing year of teaching, you bought your ICS teacher a coffee. But when they drank the coffee, they started to feel funny.
When your teacher got home, they turned on the TV, and started to watch the news. The news was running a story on a coffee recall! Due to horrible quality control, coffee from Celestial Dollars is turning people sick. But not just a normal kind of sick. It is turning them into mice! Suddenly, your teacher found themself being transformed into a mouse!
The news wrapped up the story by mentioning that the company Hip Hip Array is testing an antidote. As an apology for poisoning your teacher, you are going to help them break into the lab and steal the antidote. Unfortunately for you, the lab has a high-tech security system of Boolean algebra mazes, meaning that you have to avoid getting electrocuted while travelling through the lab.
You will be given a grid that is $$N$$ characters tall and $$M$$ characters long. This grid represents the maze. You will next be given the contents of the maze.
Various characters mark different objects in the maze:

• . Marks a blank space.
• B Marks a block, which neither your teacher nor electricity can pass.
• G Marks a wire that is on. This is guaranteed to be an input to a single gate.
• R Marks a wire that is off. This is guaranteed to be an input to a single gate.
• | Marks a wire with an unknown state, which you may need to figure out.
• A Marks an AND gate. Your teacher cannot pass through an AND gate.
• a Marks a NAND gate. Your teacher cannot pass through a NAND gate.
• O Marks an OR gate. Your teacher cannot pass through an OR gate.
• o Marks a NOR gate. Your teacher cannot pass through a NOR gate.
• X Marks an XOR gate. Your teacher cannot pass through an XOR gate.

The second rows from the top and bottom will always be entirely made of blocks (B) and unknown wires (|).
The maze is designed as a series of Boolean puzzles.
Each puzzle consists of two gates: one at the top row, and one at the bottom row. Each gate has two inputs, one from the left, and one from the right. The output of a gate points towards the other gate in the puzzle. The two gates of a single puzzle are always in the same column. The output of a gate will be a series of unknown wires (|) all in the same column as the gate. This will extend until it reaches a block (B).
There is up to one block per column. An entire puzzle is $$3$$ columns wide. There is at least $$1$$ column separating two puzzles. Neither the first nor last columns will be part of a puzzle.

#### Input Specification

The first line contains $$N\ (7 \le N \le 500)$$ and $$M\ (5 \le M \le 1000)$$, separated by a space. $$N$$ lines follow, each of which contain $$M$$ characters.

Each of the next $$N$$ lines contains the data for what is in each row. The rows are given in the order from top to bottom.

#### Output Specification

For each Boolean puzzle you encounter, output Up or Down, depending on which path is safe. The output for each puzzle should be on its own line. It is guaranteed that there is a unique solution.

#### Sample Input

7 10
.RAG..GAG.
BB|BBBB|BB
..|....|..
..B....B..
..|....|..
BB|BBBB|BB
.RoR..GXG.

#### Sample Output

Up
Down