# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Identifying Map Tiles

Map websites such as Bing Maps and Google Maps often store their maps as many different image files, called tiles. The lowest zoom level (level 0) consists of a single tile with a low-detail image of the whole map, zoom level1consists of four tiles each containing a slightly more detailed version of a quarter of the map, and in general zoom levelncontains4ndifferent tiles that each contain a part of the map.

One way of identifying a tile is by means of a quadkey. A quadkey is a string of digits uniquely identifying a tile at a certain zoom level. The first digit specifies in which of the four quadrants of the whole map the tile lies: 0 for the top-left quadrant, 1 for the top-right quadrant, 2 for the bottom-left quadrant and 3 for the bottom-right quadrant. The subsequent digits specify in which sub quadrant of the current quadrant the tile is. The quad keys for zoom levels 1 to 3 are shown in Figure I.1(a).

Another way of identifying a tile is to give the zoom level and x and y coordinates, where (0, 0) is the left-top corner. The coordinates for the tiles of zoom level 3 are shown in Figure I.1(b). Given the quadkey of a tile, output the zoom level and x and y coordinates of that tile.

## Input

The input consists of:

- one line with a strings (1 ≤ length(s) ≤ 30), the quadkey of the map tile. The strings consists of only the digits ‘0’, ‘1’, ‘2’ and ‘3’.

## Output

Output three integers, the zoom level and the x and y coordinates of the tile.

## Samples

Input | Output |
---|---|

3 | 1 1 1 |

Input | Output |
---|---|

130 | 3 6 2 |

This NWERC 2015 problem is licensed under the CC BY-SA 3.0 license.

You can find the original problem on the NWERC website.