题目描述

给定 $n$ 个两两不交的区间 $[l_i,r_i]$，$q$ 次询问，每次给定一个数 $x$，设其二进制最高位为 $d$（即 $d$ 为最大的满足 $2^d\le x$ 的整数），枚举 $i=(d+1),\dots, 60$，依次执行以下操作：

• 如果 $n$ 个区间中存在一个区间包含 $y$，满足 $y$ 的二进制后 $i+1$ 位为 $2^i+x$，则令 $x\leftarrow 2^i+x$；
• 如果 $n$ 个区间中存在一个区间包含 $y$，满足 $y$ 的二进制后 $i+1$ 位为 $x$，则令 $x\leftarrow x$；
• 特别地，如果二者同时满足，则等概率选择一个操作执行。

保证每个时刻都至少有一个操作可被执行。

求最终 $x$ 的期望对 $998244353$ 取模的结果。

输入格式

第一行，一个整数 $n$（$1 \le n \le 10^4$）。

接下来 $n$ 行，第 $i$ 行两个整数 $l_i,r_i$（$1 \le l_i\le r_i \le 2^{61}-1$，保证 $[l_i,r_i]$ 两两不交）。

接下来一行，一个整数 $q$（$1 \le q \le 2\times10^5$）。

接下来 $q$ 行，每行一个整数 $x$（$1 \le x \le 2^{60}-1$），表示一次询问。

输出格式

对于每个询问，输出一行一个整数表示答案。

样例

样例输入 1

2
11 11
15 15
1
3

样例输出 1

13

样例解释

$11=(1011)_2$，$15=(1111)_2$，$3=(11)_2$。

对 $3$ 进行操作时：

• 第一次（$i=2$）：可以选择任意一种操作。操作后 $x$ 变为 $3=(011)_2$ 或 $7=(111)_2$。
• 第二次（$i=3$）：只能选择第一种操作。操作后 $x$ 变为 $11=(1011)_2$ 或 $15=(1111)_2$。
• 之后所有操作都只能选择第二种。

最终得到的数为 $11$ 或 $15$，二者概率均为 $1\over 2$，则期望值为 $11\times {1\over 2}+15\times {1\over 2}=13$。