#2750 2 Times Bestseller

13  1 s   128 MB  

Description

형호는 2의 멱수로 예술을 하는 수의 장인이다. 문제의 제목은 배수(times)이지만 문제에 사용되는 수 들은 멱수(power)임에 유의하자.
 
형호의 주력 상품은 5x5판에 숫자가 배치된 멱수판이다. 형호가 25개의 2의 멱수를 입력하면,
 
아래의 규칙에 따라서 가공된 멱수판을 얻을 수 있다.
 
원래의 멱수판을 A, 가공된 멱수판을 B라 하자. 가공된 멱수판 B의 i행 j열의 값 bi,j의 값은 아
 
래의 수식처럼 결정된다. 물론 1~5행과 1~5열을 벗어난 값은 1로 가정한다.
 
bi,j = ai,j × ai−1,j × ai+1,j × ai,j−1 × ai,j+1 × ai,j
 
 

어느 날 특정 숫자가 배치된 멱수판이 인기가 많다는 것을 알아챈 형호는 똑같이 생긴 멱수판을
 
대량생산하려고 한다. 하지만 이미 가공된 후 해당 멱수판이 인기있다는 것을 알았기 때문에, 가
 
공하기 전의 멱수판이 어떤 모양이었는지 기억이 나지 않았다.
 
형호를 위해 가공된 멱수판이 주어지면, 가공되기 전의 멱수판을 계산하는 프로그램을 작성해보자.

Input

총 다섯 줄에 걸쳐서, 한 줄에 다섯개의 숫자가 주어진다. 입력된 숫자는 5x5 크기의 가공된 멱수판을 의미한다.
 
입력으로 주어지는 멱수판은 한 번 가공된 멱수판이므로, 해당 가공된 멱수판을 만들 수 있는 원본 멱수판은 항상 존재한다.

또한 가공된 멱수판의 모든 숫자는 10진수 3자리를 넘지 않는다.

Output

입력으로 주어진 멱수판을 만들 수 있는 원본 멱수판을 아래의 양식 처럼 5줄에 걸쳐서 출력한
 
다.
 
a1,1 ⋯ a1,5
 
⋮        ⋱       ⋮
 
a5,1 ⋯ a5,5
 
문제의 답이 여러 개가 존재할 수 있는 경우 아래와 같은 규칙을 따른다.
 
가능한 답이 여러 개 존재하는 경우 그 중 a1,1의 값이 가장 작은 것을 출력한다.
 
그러한 답이 여러 개 존재하는 경우 그 중 a1,2의 값이 가장 작은 것을 출력한다.
 
...
 
그러한 답이 여러 개 존재하는 경우 그 중 a1,5의 값이 가장 작은 것을 출력한다.
 
그러한 답이 여러 개 존재하는 경우 그 중 a2,1의 값이 가장 작은 것을 출력한다.
 
...
 
그러한 답이 여러 개 존재하는 경우 그 중 a5,5의 값이 가장 작은 것을 출력한다.
 
]

Sample Input

Sample Output

4 128 32 512 64
64 128 256 256 256
128 128 16 128 64
512 128 8 128 128
256 32 16 64 64
1 4 2 4 8
1 16 1 8 2
4 2 1 4 2
16 1 2 2 4
8 2 2 2 8

HINT

Source

shake! 2016 예선