기하할당제

$N \times M$ 크기의 격자가 있다. 각 칸은 빈 칸이거나 장애물 칸이다.

격자의 왼쪽 아래 꼭짓점을 $(0,0)$, 오른쪽 위 꼭짓점을 $(M,N)$이라 하자. 모든 격자점의 좌표는 정수이다.

$Q$개의 쿼리가 주어진다. 각 쿼리에서는 서로 다른 두 격자점 $(x_1,y_1)$과 $(x_2,y_2)$가 주어진다.

두 점을 잇는 선분이 내부를 지나가는 장애물 칸의 개수를 구하여라. 선분이 장애물 칸의 변이나 꼭짓점에 닿기만 하고 그 칸의 내부를 지나가지 않는 경우에는 그 칸을 세지 않는다.

입력은 다음과 같은 형식으로 주어진다.

$N\ M\ Q$ $S_1$ $S_2$

각 쿼리마다 선분이 내부를 지나가는 장애물 칸의 개수를 한 줄에 하나씩 출력한다.

• $1 \le NM \le 200\,000$.
• $1 \le Q \le 200\,000$.
• $$는 , 로만 이루어진 길이 의 문자열이다. ()