L. Tea Pouring
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

At the TEA Manufacturing Sector Composed Of Developers & Engineers, we specialize in brewing high-quality tea. Today, famous tea critic John Tea has come to try our tea. However, from past experience, we know our tea is far too strong for most customers, including John Tea.

Thus, we must dilute the tea with water. For a regular customer, we could give them some water and have them pour the water into the tea until they like it, but John Tea has a very fine tea palate, and such inaccurate methods will not work.

The concentration of a tea + water solution is the ratio of the volume of tea to the total volume of the solution. We have measured John Tea's desired concentration to be $$$C \cdot 10^{-9}$$$, and he will only accept the tea if the concentration is within $$$10^{-9}$$$ of the desired concentration.

Unfortunately, our patent-pending state-of-the-art tea dilution machine has not been invented yet, so we'll have to dilute the tea the old-fashioned way. We have a small $$$A$$$-liter jug (Jug A), a large $$$B$$$-liter jug (Jug B), faucets dispensing water and tea, a drain, and a robot which can pour liquids and follow simple commands.

The following is a list of commands which we can give to the robot, and what they will do.

  • FILL A W: Fill Jug A to the brim with water.
  • FILL A T: Fill Jug A to the brim with tea.
  • FILL B W: Fill Jug B to the brim with water.
  • FILL B T: Fill Jug B to the brim with tea.
  • POUR A B: Pour liquid from Jug A to Jug B until Jug A empties or Jug B becomes full.
  • POUR B A: Pour liquid from Jug B to Jug A until Jug B empties or Jug A becomes full.
  • DUMP A: Dump the contents of Jug A into the drain.
  • DUMP B: Dump the contents of Jug B into the drain.
  • SUBMIT A: Submit the contents of Jug A to John Tea. No more commands should follow.
  • SUBMIT B: Submit the contents of Jug B to John Tea. No more commands should follow.

After each command, the jugs are stirred to ensure uniform concentration. In degenerate cases (such as when a jug is already full when a POUR command is given), nothing happens. You will receive a Wrong Answer verdict if you perform any commands after a SUBMIT command, submit an empty jug, submit tea with an unacceptable concentration, or fail to submit a jug.

Currently both jugs are empty, and the robot is awaiting your commands.

Construct a sequence of up to $$$10^5$$$ commands for the robot to submit acceptable tea to John Tea.

Input

The input consists of $$$3$$$ space separated integers, $$$A$$$, $$$B$$$, $$$C$$$. $$$(1 \leq A \lt B \leq 1000)$$$, $$$(0 \leq C \leq 10^9)$$$. $$$A$$$ and $$$B$$$ are the capacities of the jugs in liters, and $$$C \cdot 10^{-9}$$$ is the desired concentration.

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Test $$$1$$$ satisfies $$$C = 0$$$.

Test $$$2$$$ satisfies $$$C = 10^9$$$.

Tests $$$3-4$$$ satisfy $$$A = 1$$$, $$$B = 1000$$$, and $$$C$$$ is a multiple of $$$10^6$$$.

Tests $$$5-6$$$ satisfy $$$A = 1$$$ and $$$B = 2$$$.

Tests $$$7-8$$$ satisfy $$$A = 1$$$ and $$$B = 3$$$.

Tests $$$9-10$$$ satisfy $$$A = 2$$$ and $$$B = 3$$$.

Tests $$$11-14$$$ satisfy $$$A, B \leq 10$$$

Tests $$$15-20$$$ satisfy no additional constraints.

Output

On the first line, output $$$K$$$, the number of commands. $$$(0 \leq K \leq 10^5)$$$

On the next $$$K$$$ lines, output a command.

Examples
Input
1 2 500000000
Output
5
FILL A T
POUR A B
FILL A W
POUR A B
SUBMIT B
Input
1 3 111111111
Output
9
FILL B W
POUR B A
FILL B T
DUMP A
POUR B A
DUMP B
POUR A B
FILL B W
SUBMIT B
Note

—

We have created a tea pouring simulator™ in C++ to simulate the robot executing a list of commands.

It is available here: https://ide.usaco.guide/P-L2eGkO-X6DZQX8KeV.

The simulator reads from standard input. The standard input should contain the test input ($$$A$$$, $$$B$$$, and $$$C$$$), followed by the test output (your construction; $$$K$$$ and your list of $$$K$$$ commands). The simulator will output "Accepted" if your sequence of commands satisfies the problem constraints and submits acceptable tea to John Tea, and "Wrong Answer" otherwise.