U192230 Photo

YAOI Round #17 (Div.2) B. Photo

 这是一个发生在初二某班的真实事件。 ~~岐王是一个人。~~ 岐王惹恼了某位德高望重之人，被要求拍若干张表情包，在圣诞节前上交。明天就是圣诞节了，岐王很是发愁该将哪些照片制成表情包，于是找到了你，希望你计算一些参数，方便筛选 _优质_ 照片。 ---------- 岐王有 $n$ 张照片。 对于每张照片，岐王会提供给你一个参数，形式为 $\dfrac{p}{q}$。 他希望知道，在一个区间内的照片的参数和为多少。 由于答案可能过大，~~岐王的数学又不好，~~ 你需要将答案分子和分母分别取模后输出（详见输出格式和样例解释 2）。 由于明天就是圣诞节了，而且岐王还要加工表情包，他只给你 $0.5s$ 的时间算出答案。

第一行输入一个整数 $n$，表示照片的组数。 接下来的 $n$ 行，第 $i$ 行的两个整数表示第 $i$ 张照片的参数 $p_i$ 和 $q_i$。 第 $n+2$ 行输入一个整数 $T$ ，表示查询组数。 接下来的 $T$ 行，每行两个整数 $l$ 和 $r$ ，代表要查询 $\dfrac{p_l}{q_l} + \dfrac{p_{l+1}}{q_{l+1}} + \dots + \dfrac{p_r}{q_r}$ 按要求取模后的值。

输出共 $T$ 行。 输出的第 $i$ 行表示第 $i$ 个询问的答案，每行两个整数分别代表答案的分子和分母，**要求化作最简分数后将分子分母分别对 $998442553$ 取模**。

### 样例 1 解释 以第一次询问为例， $\dfrac{p_1}{q_1} + \dfrac{p_2}{q_2} + \dfrac{p_3}{q_3} = \dfrac{1}{2} + \dfrac{2}{3} + \dfrac{3}{4} = \dfrac{23}{12}$。 ### 样例 2 解释 第一次询问得到的和是 $\dfrac{47826941653}{16241372}$，$47826941653$ 对 $998442553$ 取模得到 $900141662$ ，${16241372}$ 对 $998442553$ 取模得到 $16241372$，因此输出 `900141662 16241372`。因此，取模时分子分母是分开模的，取模后直接输出，无需更多操作。 ### 数据范围 | 测试点编号 | $n$ | $T$ | 特殊性质 | | :-----------: | :-----------: | :-----------: | :-----------: | | $1,2$ | $\le 10$ | $\le 100$ | 无 | | $3,4$ | $\le 10^3$ | $\le 10^5$ | 无 | | $5$ | $\le 10^3$ | $\le 10^5$ | $q_i = 1$ | | $6$ | $\le 10^3$ | $\le 10^5$ | $q_i$ 相等 | | $7,8,9,10$ | $\le 10^4$ | $\le 10^5$ | 无 | 对于 $100\%$ 的数据，$1 \le n \le 10^4$，$1 \le T \le 10^5$，保证 $p_i$ 和 $q_i$ 在 `long long` 范围内，**化为最简分数的情况下** $\sum_{i=1}^n p_i$ 和 $\sum_{i=1}^n q_i$ 在 `long long` 范围内。 此外，对于任意 $i , j (i,j \le n)$，$p_i \times q_i \times p_j \times q_j$ 在 `long long` 范围内（注意此处的 $p$ 和 $q$ 均为化至最简的）。这意味着，将任意两个化简后的分数通分后相加所得的答案在化简之前的分子分母不会超出 `long long` 范围。 ---------- **一些提示：** 1. `__gcd(a,b)` 函数会返回 `a` 和 `b` 的最小公因数。 2. 读入的分数 **不保证** 最简。 ---------- 验题人：[blue_space](http://47.110.12.131:9016/user/99905)，[lzexmpoane](http://47.110.12.131:9016/user/99911)。 ~~记得看题目背景！~~