#P13905. [2021年省选前集训]智慧树

    ID: 13112 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2200数论筛法树状数组数据结构模运算并查集

[2021年省选前集训]智慧树

仙界有一个园子,园中 nn 棵智慧树排成一行,依次编号为 11 到 nn.

每棵智慧树都会周期性地结出智慧果。第 ii 棵树每 mim_i 年结一次果,且今年离下次结果还有 bib_i 年。

现在要求你回答 qq 个问题,均形如:

  • 对于第 ll 至 rr 棵智慧树构成的序列,有多少个连续子序列,使得子序列中的树在某一年能同时结出智慧果?

输入格式

第一行一个正整数 nn, 表示有 nn 棵智慧树。

接下来 nn 行,第 ii 行两个整数 mi,bim_i, b_i, 意义如题中所述。

接下来一行一个正整数 qq, 表示有 qq 个问题。

接下来 qq 行,每行两个整数 l,rl, r, 表示一个问题,具体意义如题中所述。

输出格式

输出 nn 行,每行一个整数,表示每个问题的答案。

样例一

input

4
4 1
3 2
2 0
6 0
4
1 1
2 3
2 4
1 4



output

1
3
5
7



限制与约定

设 max⁡i=1n{mi}=M\max_{i=1}^n\{m_i\}=M.

对于全部数据,1≤n,q,M≤1061\le n, q, M\le10^6, ∀1≤i≤n\forall 1\le i\le n, 0≤bi<mi0\le b_i < m_i, 1≤mi≤M1\le m_i\le M.

子任务一(1010 分):n,q≤100n, q\le100, M≤20M\le20;

子任务二(1010 分):n,q≤1000n, q\le1000, M≤20M\le20;

子任务三(2020 分):n,q≤105n, q\le10^5, M≤20M\le20;

子任务四(3030 分):n,q,M≤105n, q, M\le10^5, ∀1≤i≤n\forall1\le i\le n, mim_i 均为素数;

子任务五(3030 分):无特殊限制。