시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 69 58 54 87.097%

문제

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 I.1(a).

(a) Quadkeys for zoom levels 1 to 3 (b) Coordinates for zoom level 3
Figure I.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 I.1(b). Given the quadkey of a tile, output the zoom level and x and y coordinates of that tile.

입력

The input consists of:

  • one line with a string s (1 ≤ length(s) ≤ 30), the quadkey of the map tile.

The string s consists of only the digits ‘0’, ‘1’, ‘2’ and ‘3’.

출력

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

예제 입력

3

예제 출력

1 1 1

예제 입력 2

130

예제 출력 2

3 6 2

힌트