스네이크 게임

알고리즘 원툴 상원이는 첫 프로젝트를 시작했다. 바로 스네이크 게임을 만드는 것이다.

게임에 자신만의 시그니처를 넣고 싶었던 상원이는 특별한 기능을 추가하기로 했다. 원래 뱀은 초록색이지만, 게임을 진행하다가 뱀 모양 안에 숨겨진 특정 모양인 트리거 패턴이 있으면 뱀의 색을 바꾸는 기능이다. 하지만 프로젝트에 며칠 밤을 새운 상원이는 이 기능을 만들 체력이 없다. 여러분이 힘들어하는 상원이를 위해 기능 구현을 도와주자. 구현해야 할 기능은 뱀 모양에 트리거 패턴이 몇 개나 있는지 찾는 것이다.

회전된 트리거 패턴도 개수에 포함해야 한다. 위 뱀 모양의 경우, 보라색으로 표시된 트리거 패턴이 두 번 나타난다. 단, 회전으로는 만들 수 없는 뒤집힌 모양은 포함하지 않는다.

뱀 모양과 트리거 패턴이 주어졌을 때, 뱀 모양에 있는 트리거 패턴의 개수를 구하라.

첫 번째 줄에 뱀 모양을 나타내는 점의 개수 $N$과 숨겨진 모양을 나타내는 점의 개수 $M$이 주어진다. $(3 \le N, M \le 500\,000)$

이어지는 $N$개의 줄에 정수 좌표 $x\_i, y\_i$가 주어진다. 뱀 모양은 $(x\_i, y\_i)$와 $(x\_{i+1}, y\_{i+1})$을 선분으로 이은 모양이다. $(-10^9 \le x\_i, y\_i \le 10^9)$

이어지는 $M$개의 줄에 정수 좌표 $x\_i, y\_i$가 주어진다. 트리거 패턴은 $(x\_i, y\_i)$와 $(x\_{i+1}, y\_{i+1})$을 선분으로 이은 모양이다. $(-10^9 \le x\_i, y\_i \le 10^9)$

각 모양의 선분은 축에 평행하며, 연속한 두 선분을 제외하면 서로 겹치지 않는다. 연속한 두 선분은 수직이고 끝 점에서만 만난다.

뱀 모양에 있는 트리거 패턴의 개수를 출력한다.