#P17718. [2026年福建省队集训]于一

[2026年福建省队集训]于一

题目描述

有一条长度为 LL 的街。令一个点的坐标范围为 [1,L][1,L],且坐标一定是整数。

街上有 nn 个灯笼,第 ii 个灯笼在坐标 aia_i,可设定的亮度范围在 [0,di][0,d_i],任何一个灯笼的亮度一定为整数。

定义坐标在 xx,亮度为 dd 的灯笼能照亮坐标在 yy 的点当且仅当 ∣x−y∣≤d|x-y| \le d。

于一有 mm 个关键点需要被照亮,其中第 ii 个关键点的坐标为 pip_i。

因此于一可以给每个灯笼设定其亮度,并且他希望设定完亮度后每个关键点都能被至少一个灯笼照亮。

于一有若干个想法。对于第 ii 次询问,他想知道如果他在坐标 bib_i 新增了一个可设定的亮度范围在 [0,vi][0,v_i] 的灯笼,那么有多少种不同的给每个灯笼设定亮度的方案满足——任意一个关键点都能至少被一个灯笼照亮。询问之间是独立的。且不存在两个灯笼(包括新增的灯笼)坐标相同,不存在两个关键点坐标相同。

由于答案可能很大,你只需要告诉于一满足要求的方案数,对 998244653 取模后的值。

两种设定亮度的方案不同,当且仅当存在一个灯笼在两种方式下被设定的亮度不同。

输入格式

第一行包含三个整数 L,n,mL, n, m。

接下来 nn 行,每行包含两个整数 ai,dia_i, d_i,分别表示第 ii 个灯笼的坐标和可设定的亮度上限。

接下来一行包含 mm 个整数 p1,p2,…,pmp_1, p_2, \ldots, p_m,表示关键点的坐标。

接下来一行包含一个整数 qq,表示询问次数。

接下来 qq 行,每行包含两个整数 bi,vib_i, v_i,分别表示新增的灯笼的坐标和可设定的亮度上限。

输出格式

输出 qq 行,每行一个整数表示答案对 998244653 取模后的值。

样例输入

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

样例输出

8
24
8

样例解释

对于第一次询问,共有 8 种合法的方案。

新增的灯的亮度只能为 0,所有合法的方案如下:

  • 设定第一个灯笼亮度为 0,第二个灯笼亮度为 0,第三个灯笼亮度为 1。
  • 设定第一个灯笼亮度为 0,第二个灯笼亮度为 0,第三个灯笼亮度为 2。
  • (下略)

数据范围

对于 100%100\% 的数据满足,1≤L≤1081 \le L \le 10^8,1≤n,q≤5×1051 \le n, q \le 5 \times 10^5,1≤m≤min⁡(L,500)1 \le m \le \min(L, 500),1≤ai,di,pi≤L1 \le a_i, d_i, p_i \le L,0≤di,vi≤L−10 \le d_i, v_i \le L-1。

保证 ∀1≤i,j≤n (i≠j),ai≠aj\forall 1\le i,j\le n\ (i\neq j), a_i \neq a_j。

保证 ∀1≤i≤n,1≤j≤q,ai≠bj\forall 1\le i\le n, 1\le j\le q, a_i \neq b_j。

保证 ∀1≤i,j≤m (i≠j),pi≠pj\forall 1\le i,j\le m\ (i\neq j), p_i \neq p_j。

各测试点的具体限制见下表:

测试点 限制
1~2 L≤10,n≤5,m≤10,q=1L \le 10, n \le 5, m \le 10, q=1
3~4 L≤108,n≤2,m≤500,q=1L \le 10^8, n \le 2, m \le 500, q=1
5~6 L≤106,n≤1000,m≤6,q≤1000L \le 10^6, n \le 1000, m \le 6, q \le 1000
7~9 L≤108,n≤1000,m≤12,q≤1000L \le 10^8, n \le 1000, m \le 12, q \le 1000
10~11 L≤107,n≤2×105,m≤16,q=1L \le 10^7, n \le 2\times 10^5, m \le 16, q=1
12~13 $L \le 10^7, n \le 2\times 10^5, m \le 16, q \le 2\times 10^5$
14~16 $L \le 10^7, n \le 3\times 10^5, m \le 30, q \le 2\times 10^5$
17~18 $L \le 10^8, n \le 5\times 10^5, m \le 500, q \le 5\times 10^5$,满足特殊性质 A
19~22 $L \le 10^8, n \le 5\times 10^4, m \le 100, q \le 5\times 10^4$
23~25 $L \le 10^8, n \le 5\times 10^5, m \le 500, q \le 5\times 10^5$

特殊性质 A:所有询问中的新增灯笼的坐标 xix_i 都相同。