1+1

题号：NC219486
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Bear_2 还在用 o(n*logn*logn) 的二维线段树，不知道世界上原来有四叉树可以 o(n*logn) 解决二维区间问题。

Bear_2 就想知道一颗 X 范围为 1~n，Y 范围为 1~m 的四叉树在访问叶子节点需要经过多少个节点，例如访问 $\{X_l=X_r=x\ ,\ Y_l=Y_r=y\}$ 的情况需要经过多少个节点？

那么问题肯定来了，是不是都不知道四叉树长什么样？

Bear_2 眼中的四叉树应该是这样的：

对于一个节点 $\{X_l=A\ ,\ X_r=B\ ,\ Y_l=C\ ,\ Y_r=D\}$ 至多存在 4 个子节点

1. $\{X_l=A\ ,\ X_r=\frac{A+B}2\ ,\ Y_l=C\ ,\ Y_r=\frac{C+D}2\}$

2. $\{X_l=A\ ,\ X_r=\frac{A+B}2\ ,\ Y_l=\frac{C+D}2+1\ ,\ Y_r=D \}$ 若C==D时不存在

3. $\{X_l=\frac{A+B}2+1\ ,\ X_r=B\ ,\ Y_l=C\ ,\ Y_r=\frac{C+D}2\}$ 若A==B时不存在

4. $\{X_l=\frac{A+B}2+1\ ,\ X_r=B\ ,\ Y_l=\frac{C+D}2+1\ ,\ Y_r=D\}$ 若A==B或C==D时不存在

详情见说明

第一行给出三个正整数 n,m,q {1<=n,m<=1000,1<=q<=10000} 分别代表X的范围，Y的范围和查询组数
之后的 q 行每行给出两个正整数 x,y {1<=x<=n,1<=m<=m} 表示查询从节点  查询到  需要经过多少个节点

对于每组查询，在一行内输出一个正整数表示从节点  查询到  需要经过多少个节点

示例1

复制

复制