Heart

Problem Description

Notice：Don't output extra spaces at the end of one line. Koishi loves her heart. Koishi's heart are divided into 21 pieces, indexed from $0$ to $20$. She has $n$ kinds of danmaku, using the $i$-th danmaku needs the help of a subset $b_i$ of her heart pieces and has aggressivity $p_i$. Suppose $A$ is a subset of her $n$ danmakus. If for any two different kinds of danmaku $u,v\in A,u\neq v$, it guarantees $b_u\cap b_v=\emptyset$, then we call $A$ a spellcard(because danmaku in the same spellcard must be released simultaneously, and one piece of heart can only supply one kind of damaku at the same time). The aggressivity of the spellcard $A$ is product of aggressivities of all danmakus belongs to $A$. Obviously, using spellcard $A$ needs the help of heart pieces. The related pieces subset is $S(A)=\cup_{u\in A}b_u$. Koishi wants to know some details about her spellcards. She will ask $m$ questions, in the $i$-th question, she wants to know the sum of aggressivities of all her spellcard $A$ whose $S(A)=x_i$, $x_i$ is a subset of heart pieces. You must answer all the questions correctly. modulo 998244353

Input

There are only one test case. First line contains a positive integer $n(1\leq n\leq 10^6)$, the number of danmakus. The $i$-th line of the following $n$ lines contains two non-negative integers $p_i,b_i(0\leq p_i<998244353,0\leq b_i<2^{21})$, describing the $i$-th danmaku, writing integer $b_i$ as binary string will get the subset $b_i$ The following integer contains a positive $m(1\leq m\leq 10^6)$, the number of questions. The $i$-th line of the following $m$ lines contains a non-negative integer $x_i(0\leq x_i<2^{21})$, describing the $i$-th question.

Output

Output $m$ lines, and the $i$-th line should contain a non-negative integer as the answer of the $i$-th question

Sample Input

3
1 1
1 2
1 3
3
1
2
3

Sample Output

1
1
2

Source

2020 Multi-University Training Contest 7