The problem background is purely fictional.

Xiao L and Xiao J go to play claw machines. There are $n$ claw machine shops on the street, and the $i$-th shop has $a_i$ claw machines. Each machine contains only one type of doll, and all dolls in all machines are distinct. Before they start, Xiao L and Xiao J have estimated the difficulty of each machine. For the $j$-th machine in the $i$-th shop, it costs exactly $b_{ij}$ to catch one doll, and there are a total of $c_{ij}$ dolls available in that machine.

Xiao L and Xiao J go to the shops $q$ times in total. For the $i$-th visit, they bring a total of $m_i$ money. Xiao J suddenly takes a liking to certain shops and wants to spend at least $k_i$ money in each of these shops. Xiao L wants to know how many ways they can catch the dolls (they do not have to spend all their money), modulo $p$, where $p$ is either $998244353$ or $10^9+7$.

Two ways are considered different if and only if the number of dolls caught for at least one type of doll is different. The queries are independent, meaning the number of dolls in each machine resets to its initial state before each visit.

Input

The first line contains three integers $n, q, p$, representing the number of shops, the number of queries, and the modulus.

The next $n$ lines each start with an integer $a_i$, followed by $a_i$ pairs of integers $b_{ij}$ and $c_{ij}$ describing each claw machine.

The next $q$ lines each contain a binary string of length $n$ and two integers $m_i, k_i$. The $j$-th character of the string is '1' if Xiao J likes the $j$-th shop, and '0' otherwise.

Output

Output $q$ lines, each containing an integer representing the answer modulo $p$.

Constraints

For all data, $1\le n\le 15$, $1\le m_i, k_i, a_i, b_{ij}, c_{ij}\le 520$, $1\le q\le 52099$.

Examples

Input 1

4 6 998244353
1 2 1
2 3 4 5 6
2 2 2 1 3
2 9 9 13 14
0101 12 1
1010 4 1
1111 100 10
0000 5 500
0110 10 2
0101 200 40

Output 1

1
3
0
22
40
1950