Hidden Art

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

요약

작은 패턴이 무한히 반복된 평면에서, 픽셀 경계에 맞춰 자른 정사각형의 네 꼭짓점 색이 모두 다르게 되는 경우가 있는지 판정한다.

난이도: 보통10점 중 7점
유형: 정수론, 해시맵, 수학, 완전 탐색
정답자: 아직 제출이 없습니다

문제

You have recently moved to a new home, and you are almost done decorating it. However, you still feel like something is missing: you need some art on the wall! Since you have already spent most of your budget on the furniture, you decide to go to the cheapest art shop there is: the Budget Art Printing Company (BAPC).

At the BAPC, you can buy infinitely large sheets of paper on which a decoration is printed. Such a decoration consists of a rectangular pattern which is repeated in all directions. This pattern in turn consists of square pixels that are colored white, red, green or blue. After buying a sheet of paper, customers may then cut out a part of the sheet to create their very own artwork.

You have just found a pattern of pixels you like, but before you have it printed you decide to check whether it is possible to cut a beautiful artwork from it. You consider an artwork beautiful if it satisfies the following properties:

It is cut out along pixel boundaries.
It is a square.
The pixels in the four corners of the square have four different colors.

Is there a beautiful artwork hidden in this infinite sheet printed with the selected pattern?

As an example, consider the first sample input, visualized in Figure H.1. In the infinitely repeated pattern, it is possible to find several beautiful artworks.

Figure H.1: Visualization of the first sample input. The pattern is shown repeated five times in the horizontal direction and two times in the vertical direction, but remember that it repeats indefinitely in all directions. The three bold outlined squares indicate some possible beautiful artworks.

입력

The input consists of:

One line with two integers $h$ and $w$ ( $1 \leq h \leq 4000$ , $1 \leq w \leq 50$ ), the height and width of the chosen pattern.
$h$ lines, each with a string of $w$ characters $c$ ( $c \in \\{`w`, `r`, `g`, `b`\\}$ ), describing the pattern.

출력

If it is possible to cut out a beautiful artwork from the sheet with the selected pattern, output "possible", otherwise output "impossible".

예제3

예제 1
입력
```
3 2
wr
wg
bg
```
예상 출력
```
possible
```
예제 2
입력
```
2 4
gbrw
wbgr
```
예상 출력
```
impossible
```

예제 3

입력

6 6
bwwrrr
bbbrrr
bbbrwr
rrrggg
rrrgww
rwwggg

예상 출력

possible