小美有一个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接下来N行，每行输入两个由空格隔开的整数X和Y（1

输出描述:

输出N行，每行输出一个整数，第i行输出第i次提问的答案，即矩阵对应位置上的数除以10^9后的余数。