题面题面语言简体中文expand_more한국어English日本語简体中文有一个 N×MN \times MN×M 的网格。每个格子要么是空格，要么是障碍格。 令网格左下角的顶点为 (0,0)(0,0)(0,0)，右上角的顶点为 (M,N)(M,N)(M,N)。所有网格点的坐标均为整数。 给出 QQQ 个查询。每个查询给出两个不同的网格点 (x1,y1)(x_1,y_1)(x1,y1) 和 (x2,y2)(x_2,y_2)。 求连接这两个点的线段穿过内部的障碍格数量。如果线段只接触某个障碍格的边或顶点，而没有穿过该格子的内部，则不计入该格子。输入输入格式如下。N M QN\ M\ QN M Q S1S_1S1 S2S_2S 输出对于每个查询，输出一行线段穿过内部的障碍格数量。限制 1≤NM≤200 0001 \le NM \le 200\,0001≤NM≤200000. 1≤Q≤200 0001 \le Q \le 200\,0001≤Q≤200000. 是一个长度为 、仅由 和 组成的字符串。() 样例样例输入复制2 2 4 ## ## 0 0 2 2 0 1 2 1 0 0 2 1 0 2 2 0样例输出复制2 0 2 2
