Battle of Nieuwpoort

시간 제한1초메모리 제한1024 MB

요약

주어진 연도를 2에서 16 사이의 진법으로 나타냈을 때 끝이 정확히 00이 되고 첫 자리가 0이 아닌 진법을 찾는다.

난이도: 쉬움10점 중 3점
유형: 수학, 정수론, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

The battle of Nieuwpoort occurred in the year $1600$ . This is famously easy to remember, because it ends in two zeros. Alas, not all historical events have been so obliging!

You suspect that the problem is with the fixation of historians on the decimal system. Maybe, given the year of another battle, there exists a small base (at most $16$ ) in which this year would also be easy to remember?

입력

The input consists of:

One line with $4$ tokens:
- One integer $y$ ( $1\leq y\leq 2024$ , in base- $10$ ), the year of the battle.
- Three words $w$ ( $2\leq |w|\leq 20$ ), naming the battle. The words only consist of English letters (A-Z and a-z).

출력

If it is possible to rewrite the year to make it easier to remember, output this base $b$ ( $2\leq b\leq 16$ , in base- $10$ ) and the year written in base- $b$ . Otherwise, output "impossible".

The year in base- $b$ must end with "00" and must not start with '0'.

Use letters 'a', 'b', 'c', etc. for the digits following '9' in bases higher than $10$ .

If there are multiple valid solutions, you may output any one of them.

예제7

예제 1
입력
```
1600 Battle of Nieuwpoort
```
예상 출력
```
10 1600
```
예제 2
입력
```
625 Battle of Sarus
```
예상 출력
```
5 10000
```
예제 3
입력
```
1600 Battle of Sekigahara
```
예상 출력
```
8 3100
```
예제 4
입력
```
1815 Battle of Waterloo
```
예상 출력
```
11 1400
```
예제 5
입력
```
1859 Battle of Solferino
```
예상 출력
```
13 b00
```
예제 6
입력
```
1848 Battle of Bov
```
예상 출력
```
2 11100111000
```
예제 7
입력
```
1453 Fall of Constantinople
```
예상 출력
```
impossible
```