Impressive Integers

Time limit1sMemory limit512 MB

Summary

Given n up to 1000, decide whether an equilateral triangle can be tiled by n equilateral triangles of only two side lengths, and print such a tiling if one exists.

Level: Medium7 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

Recently, Alice and her sister Clara learned about adorable numbers. A positive integer $n$ is called adorable if there exist integers $a$ , $b$ , and $c$ such that an equilateral triangle with side length $c$ can be tiled with $n$ smaller equilateral triangles, each having side length $a$ or $b$ . For instance, $6$ is adorable, as shown in Figure I.1a below.



(a) Visualization of the second sample output.	(b) Coordinate system used for the output.

They decided to see who could come up with more adorable numbers, but checking all numbers by hand is too cumbersome. Alice therefore asked you to check whether the numbers Clara listed are adorable. Because she wants to be sure that every number claimed to be adorable really is, she asked you to write a program that, given an integer $n$ , determines whether it is adorable. If it is, the program outputs a valid tiling as shown in Figure I.1a.

Input

The input consists of:

A single positive integer $n$ ( $1 \leq n \leq 1\,000$ ).

Output

If $n$ is adorable, output a valid tiling in the following format:

Three integers $a, b, c$ ( $1 \leq a, b \leq c \leq 10^9$ ) such that an equilateral triangle with side length $c$ can be tiled with $n$ equilateral triangles with side lengths $a$ and $b$ .
$n$ lines, each describing one triangle and consisting of:
- one of A and B, specifying whether the side length of the triangle is $a$ or $b$ ;
- two integers $x, y$ , giving the leftmost corner of the triangle;
- one of U and D, specifying whether the triangle points upward or downward.

These triangles must form a valid tiling of the equilateral triangle with corners at $(0, 0), (0, c),$ and $(c, 0)$ , where all coordinates use the coordinate system in Figure I.1b.

If $n$ is not adorable, output impossible.

If your tiling consists of triangles that all have the same size, you may use either A or B exclusively for all triangles, or set $a = b$ and label each triangle with A or B arbitrarily.

It can be shown that a tiling following these rules exists for every adorable number in the input range. You may output any valid tiling.

Examples2

Example 1
Input
```
2
```
Expected output
```
impossible
```

Example 2

Input

Expected output

1 2 3
B 0 1 U
A 0 0 U
A 0 1 D
A 1 0 U
A 1 1 D
A 2 0 U