小美有一个2×2的矩阵，矩阵左上角、右上角、左下角、右下角的数字分别为0、A、B、C。 小美觉得该矩阵不够大，她按如下方法扩展该矩阵： 将2×2的矩阵扩展为4×4的矩阵，4×4的矩阵被分为左上角、右上角、左下角、右下角这4个2×2的矩阵，其中左上角为原2×2的矩阵，右上角为原2×2的矩阵每个位置上的数加上A，左下角为原2×2的矩阵每个位置上的数加上B，右下角为原2×2的矩阵每个位置上的数加上C； 将4×4的矩阵扩展为8×8的矩阵，8×8的矩阵被分为左上角、右上角、左下角、右下角这4个4×4的矩阵，其中左上角为原4×4的矩阵，右上角为原4×4的矩阵每个位置上的数加上A，左下角为原4×4的矩阵每个位置上的数加上B，右下角为原4×4的矩阵每个位置上的数加上C； …… 经过不断扩展，小美可以得到一个无穷大的矩阵。小美打算用该矩阵和小团玩游戏，即对小团进行N次提问，每次给出正整数X、Y，并问小团矩阵上第X行第Y列上的数是多少，由于该数可能很大，只要求小团回答该数除以10^9后的余数。
第一行输入四个由空格隔开的整数A、B、C和N（0<=A,B,C<10^9、1<=N<=10^5）。 接下来N行，每行输入两个由空格隔开的整数X和Y（1<=X,Y<=10^9）。
输出N行，每行输出一个整数，第i行输出第i次提问的答案，即矩阵对应位置上的数除以10^9后的余数。
1 2 3 5 3 3 5 6 6 1 8 3 8 8
3 4 4 7 9
考点：分治
数据规模 N ≤ 1e5 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出
推荐方向：分治
本题切入点
矩阵按 2×2 递归扩展，属于分形结构：递归地把坐标缩小一半，累加所在象限的偏移量 A/B/C 即可。
把问题二分拆成规模更小的同类子问题，合并结果得到答案。
思路框架（分治 通法 · 非本题专属）
实现要点：分治常与递归结合，注意递归深度 O(log n) 一般安全。
复杂度：时间 O(n log n) ｜ 空间 O(n)
该范式的通法易错点
对照本题
样例 1：输入 1 2 3 5 / 3 3 / 5 6 / 6 1 / 8 3 / 8 8 → 输出 3 / 4 / 4 / 7 / 9
扩展后的矩阵前8行和前8列如下：
0 1 1 2 1 2 2 3
2 3 3 4 3 4 4 5
2 3 3 4 3 4 4 5
4 5 5 6 5 6 6 7
2 3 3 4 3 4 4 5
4 5 5 6 5 6 6 7
4 5 5 6 5 6 6 7
6 7 7 8 7 8 8 9
解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
本题来源：美团2023校招笔试-编程题（算法编程题）。