생물학

안드로이드 바샤는 생물학 연구 과제를 준비하고 있다. 이 연구에서 그는 거미류를 다룬다. 바샤가 관심을 두는 대상은 거미 자체가 아니라 여러 종의 거미가 만드는 거미줄이다.

바샤는 거미줄이 어떻게 만들어지는지 이미 알아냈다. 거미줄은 거미줄 매듭이라고 부르는 점들의 집합이고, 이 매듭들은 이른바 가닥으로 서로 연결된다. 매듭은 한 평면 위의 점으로 볼 수 있다. 가닥은 두 매듭을 잇는 선분이다. 가닥들은 매듭에서만 서로 교차한다.

바샤는 어떤 거미가 품질이 가장 좋은 거미줄을 만드는지 알고 싶어 한다. 이를 위해 거미줄의 끈끈함을 그 안에 있는 서로 다른 함정의 개수로 정의한다. 함정은 꼭짓점이 거미줄 매듭이고 변이 가닥인 다각형이다. 이 다각형은 자기 자신과 교차하지 않으며 자기 자신과 접하지도 않는다.

바샤는 매듭이 16개인 거미줄 여러 개를 분석했다. 그 끈끈함은 $5\,000$에서 $300\,000$ 사이였다. 이제 그는 매듭이 16개이고 끈끈함이 $300\,000$보다 큰 거미줄이 어떤 모습일 수 있는지 알고 싶어 한다.

이 문제에는 입력 데이터가 없다.

처음 16줄에는 거미줄 매듭의 좌표를 정수 쌍 $x_i$, $y_i$로 출력한다 ($-1000 \leq x_i, y_i \leq 1000$). 다음 16줄에는 거미줄의 인접 행렬을 출력한다. 인접 행렬은 0과 1로만 이루어진 $16 \times 16$ 표이다. 행렬은 대칭이어야 하며, 주대각선의 값은 모두 0이어야 한다.

서로 다른 두 매듭은 서로 다른 점에 있어야 한다. 매듭은 가닥의 내부 점 위에 놓일 수 없다. 두 가닥이 교차할 수 있는 곳은 두 가닥의 공통 매듭뿐이다.

거미줄의 끈끈함은 $300\,000$보다 커야 한다. 그러한 거미줄이 존재한다는 것은 보장되어 있다.

예시 출력은 올바른 답이 아니며, 출력 형식만 보여 준다. 출력해야 할 거미줄은 6개가 아니라 16개의 매듭을 가져야 한다는 점에 유의하라. 위의 그림은 예시 출력에 해당한다. 예시 거미줄의 끈끈함은 21에 불과하다.