Given $n$ pairwise disjoint intervals $[l_i, r_i]$, there are $q$ queries. For each query, you are given a number $x$. Let $d$ be the highest bit of $x$ (i.e., $d$ is the largest integer such that $2^d \le x$). Iterate $i = (d+1), \dots, 60$ and sequentially perform the following operations:

• If there exists an interval among the $n$ intervals that contains a value $y$ such that the last $i+1$ bits of $y$ are $2^i + x$, then set $x \leftarrow 2^i + x$.
• If there exists an interval among the $n$ intervals that contains a value $y$ such that the last $i+1$ bits of $y$ are $x$, then set $x \leftarrow x$.
• Specifically, if both conditions are satisfied, choose one operation to perform with equal probability.

It is guaranteed that at least one operation can be performed at any given time.

Calculate the expected value of the final $x$ modulo $998244353$.

Input

The first line contains an integer $n$ ($1 \le n \le 10^4$).

The next $n$ lines each contain two integers $l_i, r_i$ ($1 \le l_i \le r_i \le 2^{61}-1$, guaranteed that $[l_i, r_i]$ are pairwise disjoint).

The next line contains an integer $q$ ($1 \le q \le 2\times 10^5$).

The next $q$ lines each contain an integer $x$ ($1 \le x \le 2^{60}-1$), representing a query.

Output

For each query, output a single integer representing the answer.

Examples

Input 1

2
11 11
15 15
1
3

Output 1

13

Note

$11=(1011)_2$, $15=(1111)_2$, $3=(11)_2$.

When performing operations on $3$:

• First step ($i=2$): Either operation can be chosen. After the operation, $x$ becomes $3=(011)_2$ or $7=(111)_2$.
• Second step ($i=3$): Only the first operation can be chosen. After the operation, $x$ becomes $11=(1011)_2$ or $15=(1111)_2$.
• For all subsequent steps, only the second operation can be chosen.

The final values obtained are $11$ or $15$, each with probability $1\over 2$. The expected value is $11\times {1\over 2}+15\times {1\over 2}=13$.