#10203. [百度之星 2025] Operation（暂无数据）

给定 个两两不交的区间 ， 次询问，每次给定一个数 ，设其二进制最高位为 （即 为最大的满足 的整数），枚举 ，依次执行以下操作：

• 如果 个区间中存在一个区间包含 ，满足 的二进制后 位为 ，则令 ；
• 如果 个区间中存在一个区间包含 ，满足 的二进制后 位为 ，则令 ；
• 特别地，如果二者同时满足，则等概率选择一个操作执行。

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

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

第一行一个整数 （）。

接下来 行，第 行两个整数 （，保证区间 两两不交）。

接下来一行一个整数 （）。

接下来 行，每行一个整数 （），表示一次询问。

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

样例 1

输入：

2
11 11
15 15
1
3

输出：

13

样例解释：

，，。

对 进行操作时：

• 第一次（）：可以选择任意一种操作。操作后 变为 或 。
• 第二次（）：只能选择第一种操作。操作后 变为 或 。
• 之后所有操作都只能选择第二种。

最终得到的数为 或 ，二者概率均为 ，则期望值为 。