Identifying Map Tiles

Map sites such as Bing Maps and Google Maps store a map as many small image files called tiles. The lowest zoom level, level 0, is a single tile holding a low detail image of the whole map. Level 1 has four tiles, and each one holds a slightly more detailed image of a quarter of the map. In general, level $n$ has $4^n$ tiles that each cover a part of the map.

One way to identify a tile is a quadkey. A quadkey is a string of digits that uniquely names one tile at a given zoom level. The first digit says which of the four quadrants of the whole map the tile lies in: 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. Every later digit uses the same numbering to say which sub quadrant of the current quadrant the tile lies in. The length of the quadkey is the zoom level of the tile.

(a) Quadkeys for zoom levels 1 to 3	(b) Coordinates for zoom level 3
Figure 1: the two representations. The images come from the MSDN.

Another way to identify a tile is to give its zoom level together with $x$ and $y$ coordinates. At level $n$ the map is a grid of $2^n$ by $2^n$ tiles, $x$ numbers the columns from 0 at the left edge, and $y$ numbers the rows from 0 at the top edge, so $(0, 0)$ is the top-left tile. Given the quadkey of a tile, print the zoom level and the $x$ and $y$ coordinates of that tile.

The input is one line with a string $s$ ($1 \le |s| \le 30$), the quadkey of the map tile.

The string $s$ contains only the digits 0, 1, 2, and 3.

Print three integers on one line, separated by single spaces: the zoom level, the $x$ coordinate, and the $y$ coordinate of the tile.