 Programming Contest PUC Chile - Div 1

#### Start

2018-06-20 21:40 UTC

## Programming Contest PUC Chile - Div 1

#### End

2018-06-21 00:20 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -459 days 15:31:45

2:40:00

0:00:00

# Problem BIdentifying 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 level $1$ consists of four tiles each containing a slightly more detailed version of a quarter of the map, and in general zoom level $n$ contains $4^ n$ different 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 quadkeys for zoom levels $1$ to $3$ are shown in Figure 1(a). (a) Quadkeys for zoom levels $1$ to $3$ (b) Coordinates for zoom level 3
Figure 1: Visualisation of the two representations. The images are taken from the MSDN.

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 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 string $s$ ($1\leq \text {length}(s) \leq 30$), the quadkey of the map tile.

The string $s$ 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.

Sample Input 1 Sample Output 1
3

1 1 1

Sample Input 2 Sample Output 2
130

3 6 2