You are required to type using a joystick instead of a keyboard. To type using a joystick at the first, you need a keymap. A keymap maps every lowercase English character to a point in 2D dimension space in which $$x, y$$ are integers. You must never map two distinct characters to the same point. Also, you require a pointer that is a point in 2D dimension space.

Now, you can start typing. At first, you can position the pointer freely where you want. Then, you start typing string $$s$$ character by character. Everything is normal, you can move the pointer down $$(x, y - 1)$$, up $$(x, y + 1)$$, left $$(x - 1, y)$$, and, right $$(x + 1, y)$$.

If you position the pointer on a point where a character is mapped to it, you can insert the character using the red button on the joystick.

Your task is to minimize the total number of moves (inserting character does not count as a move). It's easy to inform that the moves are obviously determined if the keymap is given. print a keymap that minimizes the cost if you are given $$s$$.

Input format

The first line contains $$s$$.

Output format

Print 26 lines. In the $$i^{th}$$ line, print $$x, y$$ denoting the coordinates of the mapped point to the $$i^{th}$$ English lowercase character.

Constraints

$$|S| = 10^6$$

$$S$$ consists of lowercase English characters.