화성에서 작물 키우기

화성 임무 APOLLO가 강한 폭풍을 맞았다. 우주비행사 Mark Watney는 부상을 입은 뒤 길을 잃었다. 사령관 Melissa는 나머지 대원을 구하려고 Mark를 남겨 두고 떠났다. 부상으로 살아남기 어렵다고 판단했기 때문이다. 그러나 Mark는 살아남았고, 지금은 화성에 홀로 있다.

Mark의 식량은 5개월분뿐이지만, 구조는 4년 뒤에 이루어진다. 그는 밭에서 작물을 길러 생존하려 한다. NASA의 도움으로 재배 방법은 알아냈지만, 어느 칸에 심을지는 아직 정해야 한다.

밭은 2차원 좌표 평면에 놓인 볼록 다각형이다. 칸은 다각형의 내부와 경계(꼭짓점 포함)에 있는 모든 정수 좌표 점이다. 모든 꼭짓점의 좌표는 정수이다.

성장 요인 $f = (a, b)$가 주어지면, 칸 $(x, y)$의 성장 능력은 $g = a \times x + b \times y$이다. Mark는 성장 능력이 가장 큰 칸을 고르려 한다. 성장 요인마다 밭의 모든 칸 중 최대 성장 능력을 구하라.

첫 줄에 테스트 케이스의 수 T(1 ≤ T ≤ 100)가 주어진다.

각 테스트 케이스의 첫 줄에는 공백으로 구분된 두 정수 N과 Q가 주어진다. N은 꼭짓점의 개수(3 ≤ N ≤ 10,000), Q는 성장 요인의 개수(1 ≤ Q ≤ 100,000)이다.

이어서 N줄에 꼭짓점의 좌표 x, y가 주어진다. $-10^9 \le x, y \le 10^9$이다. 꼭짓점은 반시계 방향으로 주어지며, 同一 직선 위에 있는 세 꼭짓점은 없다.

이어서 Q줄에 a, b가 주어진다. $-10^9 \le a, b \le 10^9$이다.

성장 요인마다 밭의 칸들 중 최대 성장 능력을 한 줄에 출력한다.